C++
Manipolazione bit

Osservazioni

#include <bitset>

Impostazione un po '

Manipolazione bit in stile C.

Un bit può essere impostato usando l'operatore OR bit a bit ( | ).

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

Utilizzando std :: bitset

set(x) o set(x,true) - imposta il bit in posizione x su 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

Schiarirsi un po '

Manipolazione bit in stile C.

Un bit può essere cancellato usando l'operatore AND bit per bit ( & ).

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

Utilizzando std :: bitset

reset(x) o set(x,false) - cancella il bit in posizione 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

Toggling un po '

Manipolazione bit in stile C.

Un bit può essere commutato usando l'operatore XOR ( ^ ).

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

Utilizzando 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)

Controllando un po '

Manipolazione bit in stile C.

Il valore del bit può essere ottenuto spostando il numero a x volte di destra e quindi eseguendo il bit AND ( & ) su di esso:

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

L'operazione di spostamento a destra può essere implementata come uno spostamento aritmetico (firmato) o uno spostamento logico (senza segno). Se il number nel number dell'espressione number >> x ha un tipo firmato e un valore negativo, il valore risultante è definito dall'implementazione.

Se abbiamo bisogno del valore di quel bit direttamente sul posto, potremmo invece spostare la maschera:

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

Entrambi possono essere usati come condizionali, poiché tutti i valori diversi da zero sono considerati veri.

Utilizzando std :: bitset

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

Cambiare l'ennesimo bit in x

Manipolazione bit in stile C.

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

Utilizzando std :: bitset

set(n,val) - imposta il bit n sul valore val .

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

Imposta tutti i bit

Manipolazione bit in stile C.

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

^{(Vedi qui per una spiegazione del perché questo funziona ed è in realtà l'approccio migliore).}

Utilizzando std :: bitset

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

Rimuovi il bit impostato più a destra

Manipolazione bit in stile C.

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

Spiegazione

• se n è zero, abbiamo 0 & 0xFF..FF che è zero
• else n può essere scritto 0bxxxxxx10..00 e n - 1 è 0bxxxxxx011..11 , quindi n & (n - 1) è 0bxxxxxx000..00 .

Set di bit di conteggio

Il conteggio della popolazione di un bitstring è spesso necessario in crittografia e altre applicazioni e il problema è stato ampiamente studiato.

Il modo ingenuo richiede un'iterazione 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;

Un bel trucco (basato su Rimuovi bit più a destra ) è:

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

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

Passa attraverso tante iterazioni quanti sono i bit impostati, quindi è buono quando si prevede che il value abbia pochi bit diversi da zero.

Il metodo fu proposto per la prima volta da Peter Wegner (in CACM 3/322 - 1960) ed è ben noto poiché compare in C Programming Language di Brian W. Kernighan e Dennis M. Ritchie.

Ciò richiede 12 operazioni aritmetiche, una delle quali è una multicrizione:

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

Questo tipo di implementazione ha il miglior comportamento nel caso peggiore (vedi il peso di Hamming per ulteriori dettagli).

Molte CPU hanno un'istruzione specifica (come il popcnt di x86) e il compilatore può offrire una funzione specifica ( non standard ) incorporata. Ad esempio con g ++ c'è:

int __builtin_popcount (unsigned x);

Controlla se un numero intero è una potenza di 2

Il trucco n & (n - 1) (vedi Rimuovi il bit più a destra ) è anche utile per determinare se un intero è una potenza di 2:

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

Si noti che senza la prima parte del controllo ( n && ), 0 viene erroneamente considerato una potenza di 2.

Applicazione di manipolazione di bit: lettera da piccola a maiuscola

Una delle numerose applicazioni di manipolazione di bit è la conversione di una lettera da piccola a maiuscola o viceversa scegliendo una maschera e un'operazione bit appropriata. Ad esempio, la lettera ha questa rappresentazione binaria 01(1)00001 mentre la sua controparte capitale ha 01(0)00001 . Si differenziano unicamente tra parentesi nel bit. In questo caso, la conversione di una lettera da piccola a maiuscola è fondamentalmente l'impostazione del bit tra parentesi a uno. Per fare ciò, facciamo quanto segue:

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

Il codice per convertire una lettera in una lettera è

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

Il risultato è

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