C++
Bit-Manipulation

Bemerkungen

#include <bitset>

Ein bisschen einstellen

Bit-Manipulation im C-Stil

Ein Bit kann mit dem bitweisen OR-Operator ( | ) gesetzt werden.

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

Verwenden von std :: bitset

set(x) oder set(x,true) - setzt das Bit an Position x auf 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

Ein bisschen klären

Bit-Manipulation im C-Stil

Ein Bit kann mit dem bitweisen AND-Operator ( & ) gelöscht werden.

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

Verwenden von std :: bitset

reset(x) oder set(x,false) - löscht das Bit an Position 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

Ein bisschen umschalten

Bit-Manipulation im C-Stil

Ein Bit kann mit dem XOR-Operator ( ^ ) umgeschaltet werden.

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

Verwenden von 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)

Ein bisschen überprüfen

Bit-Manipulation im C-Stil

Der Wert des Bits kann erhalten werden, indem die Anzahl x mal nach rechts verschoben wird und dann bitweise UND ( & ) darauf ausgeführt wird:

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

Die Rechtsverschiebungsoperation kann entweder als arithmetische (vorzeichenbehaftete) Verschiebung oder als logische (vorzeichenlose) Verschiebung implementiert werden. Wenn number im Ausdruck number >> x einen vorzeichenbehafteten Typ und einen negativen Wert hat, ist der resultierende Wert durch die Implementierung definiert.

Wenn wir den Wert dieses Bits direkt an Ort und Stelle benötigen, können Sie stattdessen die Maske nach links verschieben:

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

Beides kann als Bedingung verwendet werden, da alle Werte ungleich Null als wahr betrachtet werden.

Verwenden von std :: bitset

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

Ändern des n-ten Bits in x

Bit-Manipulation im C-Stil

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

Verwenden von std :: bitset

set(n,val) - setzt Bit n auf den Wert val .

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

Setze alle Bits

Bit-Manipulation im C-Stil

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

^{( Hier erfahren Sie, warum dies funktioniert und tatsächlich der beste Ansatz ist.)}

Verwenden von std :: bitset

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

Das ganz rechts eingestellte Bit entfernen

Bit-Manipulation im C-Stil

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);
}

Erläuterung

• Wenn n Null ist, haben wir 0 & 0xFF..FF die Null ist
• ansonsten kann n 0bxxxxxx10..00 geschrieben 0bxxxxxx10..00 und n - 1 ist 0bxxxxxx011..11 , also ist n & (n - 1) 0bxxxxxx000..00 .

Gesetzte Bits zählen

Die Populationszählung einer Bitkette wird häufig in der Kryptographie und anderen Anwendungen benötigt, und das Problem wurde umfassend untersucht.

Der naive Weg erfordert eine Iteration pro 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;

Ein schöner Trick (basierend auf Remove-rechtem gesetztem Bit ) ist:

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

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

Es durchläuft so viele Iterationen, wie gesetzte Bits vorhanden sind. Es ist also gut, wenn erwartet wird, dass der value wenige Nicht-Null-Bits hat.

Die Methode wurde zuerst von Peter Wegner (in CACM 3/322 - 1960) vorgeschlagen und ist seit ihrer Veröffentlichung in der Programmiersprache C von Brian W. Kernighan und Dennis M. Ritchie bekannt.

Dies erfordert 12 arithmetische Operationen, von denen eine eine Multikation ist:

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) + ... 
}

Diese Art der Implementierung weist das beste Worst-Case-Verhalten auf (weitere Einzelheiten finden Sie unter Hamming-Gewicht ).

Viele CPUs verfügen über eine bestimmte Anweisung (z. B. popcnt x86), und der Compiler könnte eine spezifische ( nicht standardmäßige ) eingebaute Funktion bieten. ZB mit g ++ gibt es:

int __builtin_popcount (unsigned x);

Prüfen Sie, ob eine ganze Zahl eine Potenz von 2 ist

Der Trick n & (n - 1) (siehe rechtes gesetztes Bit ganz rechts entfernen ) ist auch nützlich, um zu bestimmen, ob eine Ganzzahl eine Potenz von 2 ist:

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

Beachten Sie, dass 0 ohne den ersten Teil der Prüfung ( n && ) fälschlicherweise als Potenz von 2 betrachtet wird.

Bit-Manipulationsanwendung: Klein- und Großbuchstabe

Eine von mehreren Anwendungen der Bitmanipulation ist das Konvertieren eines Buchstabens von klein nach groß oder umgekehrt, indem eine Maske und eine richtige Bitoperation ausgewählt werden . Zum Beispiel hat das Schreiben diese binäre Darstellung 01(1)00001 , während das Kapitalgegenstück 01(0)00001 , 01(0)00001 . Sie unterscheiden sich lediglich in den Bits in Klammern. In diesem Fall setzt das Konvertieren eines Buchstabens von klein nach groß das Bit in Klammern grundsätzlich auf eins. Dazu machen wir folgendes:

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

Der Code zum Konvertieren eines Briefs in einen Brief lautet

#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;
}

Das Ergebnis ist

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