C++
Bitmanipulatie

Opmerkingen

#include <bitset>

Een beetje instellen

Bitmanipulatie in C-stijl

Een bit kan worden ingesteld met de operator bitwise OR ( | ).

// Bit x will be set
number |= 1LL << x; 

Met behulp van std :: bitset

set(x) of set(x,true) - stelt bit op positie x op 1 .

std::bitset<5> num(std::string("01100"));
num.set(0);      // num is now 01101
num.set(2);      // num is still 01101
num.set(4,true); // num is now 11110

Een beetje opruimen

Bit-manipulatie in C-stijl

Een bit kan worden gewist met de operator bitwise AND ( & ).

// Bit x will be cleared
number &= ~(1LL << x);

Met behulp van std :: bitset

reset(x) of set(x,false) - wist het bit op positie x .

std::bitset<5> num(std::string("01100"));
num.reset(2);     // num is now 01000
num.reset(0);     // num is still 01000
num.set(3,false); // num is now 00000

Een beetje schakelen

Bit-manipulatie in C-stijl

Een beetje kan worden omgeschakeld met de XOR-operator ( ^ ).

// Bit x will be the opposite value of what it is currently
number ^= 1LL << x;

Met behulp van std :: bitset

std::bitset<4> num(std::string("0100"));
num.flip(2); // num is now 0000
num.flip(0); // num is now 0001
num.flip();  // num is now 1110 (flips all bits)

Een beetje aan het controleren

Bit-manipulatie in C-stijl

De waarde van de bit kan worden verkregen door het nummer x keer naar rechts te verschuiven en er vervolgens bitmatig EN ( & ) op uit te voeren:

(number >> x) & 1LL;  // 1 if the 'x'th bit of 'number' is set, 0 otherwise

De bewerking naar rechts verschuiven kan worden geïmplementeerd als een rekenkundige (ondertekende) dienst of een logische (niet-ondertekende) dienst. Als number in de uitdrukking number >> x een ondertekend type en een negatieve waarde heeft, is de resulterende waarde door de implementatie gedefinieerd.

Als we de waarde van dat bit direct op zijn plaats nodig hebben, kunnen we in plaats daarvan het masker links verschuiven:

(number & (1LL << x));  // (1 << x) if the 'x'th bit of 'number' is set, 0 otherwise

Beide kunnen als voorwaardelijk worden gebruikt, omdat alle niet-nulwaarden als waar worden beschouwd.

Met behulp van std :: bitset

std::bitset<4> num(std::string("0010"));
bool bit_val = num.test(1);  // bit_val value is set to true;

Het derde bit veranderen in x

Bit-manipulatie in C-stijl

// Bit n will be set if x is 1 and cleared if x is 0.
number ^= (-x ^ number) & (1LL << n);

Met behulp van std :: bitset

set(n,val) - stelt bit n op de waarde val .

std::bitset<5> num(std::string("00100"));
num.set(0,true);  // num is now 00101
num.set(2,false); // num is now 00001

Stel alle bits in

Bit-manipulatie in C-stijl

x = -1; // -1 == 1111 1111 ... 1111b

^{(Zie hier voor een uitleg waarom dit werkt en eigenlijk de beste aanpak is.)}

Met behulp van std :: bitset

std::bitset<10> x;
x.set(); // Sets all bits to '1'

Verwijder het meest rechtse bit

Bit-manipulatie in C-stijl

template <typename T>
T rightmostSetBitRemoved(T n)
{
    // static_assert(std::is_integral<T>::value && !std::is_signed<T>::value, "type should be unsigned"); // For c++11 and later
    return n & (n - 1);
}

Uitleg

• als n nul is, hebben we 0 & 0xFF..FF die nul is
• anders kan n worden geschreven 0bxxxxxx10..00 en n - 1 is 0bxxxxxx011..11 , dus n & (n - 1) is 0bxxxxxx000..00 .

Tellen bits ingesteld

Het aantal populaties van een bitstring is vaak nodig in cryptografie en andere toepassingen en het probleem is uitgebreid bestudeerd.

De naïeve manier vereist één iteratie per bit:

unsigned value = 1234;
unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (bits = 0; value; value >>= 1)
  bits += value & 1;

Een leuke truc (gebaseerd op het meest rechtse bit verwijderen ) is:

unsigned bits = 0;  // accumulates the total number of bits set in `n`

for (; value; ++bits)
  value &= value - 1;

Het doorloopt evenveel herhalingen als er ingestelde bits zijn, dus het is goed als verwacht wordt dat de value weinig bits van nul zal hebben.

De methode werd voor het eerst voorgesteld door Peter Wegner (in CACM 3/322 - 1960) en is bekend omdat deze wordt weergegeven in C Programming Language door Brian W. Kernighan en Dennis M. Ritchie.

Dit vereist 12 rekenkundige bewerkingen, waaronder een multicatie:

unsigned popcount(std::uint64_t x)
{
  const std::uint64_t m1  = 0x5555555555555555;  // binary: 0101...
  const std::uint64_t m2  = 0x3333333333333333;  // binary: 00110011..
  const std::uint64_t m4  = 0x0f0f0f0f0f0f0f0f;  // binary: 0000111100001111

  x -= (x >> 1) & m1;             // put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); // put count of each 4 bits into those 4 bits 
  x = (x + (x >> 4)) & m4;        // put count of each 8 bits into those 8 bits 
  return (x * h01) >> 56;  // left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

Dit soort implementatie heeft het beste worst-case gedrag (zie Hamming-gewicht voor meer informatie).

Veel CPU's hebben een specifieke instructie (zoals x86's popcnt ) en de compiler kan een specifieke ( niet-standaard ) ingebouwde functie bieden. Bijv. Met g ++ is er:

int __builtin_popcount (unsigned x);

Controleer of een geheel getal een macht van 2 is

De truc n & (n - 1) (zie De meest rechtse bit verwijderen ) is ook handig om te bepalen of een geheel getal een macht van 2 is:

bool power_of_2 = n && !(n & (n - 1));

Merk op dat zonder het eerste deel van de controle ( n && ) 0 onrechte als een macht van 2 wordt beschouwd.

Bit Manipulation Application: Small to Capital Letter

Een van de vele toepassingen van bitmanipulatie is het omzetten van een letter van klein naar hoofdletter of vice versa door een masker en een juiste bitbewerking te kiezen . Bijvoorbeeld, de brief heeft dit binaire representatie 01(1)00001 , terwijl de hoofdstad tegenhanger heeft 01(0)00001 . Ze verschillen alleen in het bit tussen haakjes. In dit geval is het omzetten van de een brief van klein tot kapitaal is in principe het instellen van het bit tussen haakjes één. Om dit te doen, doen we het volgende:

/****************************************
convert small letter to captial letter.
========================================
     a: 01100001
  mask: 11011111  <-- (0xDF)  11(0)11111
      :---------
a&mask: 01000001  <-- A letter
*****************************************/

De code voor het omzetten van een letter in een letter is

#include <cstdio>

int main()
{
    char op1 = 'a';  // "a" letter (i.e. small case)
    int mask = 0xDF; // choosing a proper mask

    printf("a (AND) mask = A\n");
    printf("%c   &   0xDF = %c\n", op1, op1 & mask);
    
    return 0;
}

Het resultaat is

$ g++ main.cpp -o test1
$ ./test1
a (AND) mask = A
a   &   0xDF = A