Nella programmazione, possiamo lavorare con i bit in modo efficace. Per prima cosa, vediamo le definizioni di ogni operazione sui bit e poi passiamo a diverse tecniche per risolvere i problemi. Fondamentalmente, ci sono sei operatori che ogni linguaggio supporta per la manipolazione dei bit: &(AND), |(OR), ^(XOR), <<(shift-sinistra), >>(shift-destra) e ~(complemento).

Fatti sulla programmazione bit a bit

AND bit a bit

L'AND bit per bit verifica due numeri binari e restituisce valori di bit pari a 1 per le posizioni in cui entrambi i numeri hanno uno e valori di bit pari a 0 dove entrambi i numeri non ne avevano uno.

// a = 10 (in binary)
var a = 2
// b = 11 (in binary)
var b = 3
// a & b = 10 & 11 = 10 (in binary) = 2 (in decimal)
a & b
<< 2

L'OR bit per bit verifica due numeri binari e restituisce valori di bit pari a 1 per le posizioni in cui uno o entrambi i bit sono uno, il risultato di 0 si verifica solo quando entrambi i bit sono 0.

// a | b = 10 | 11 = 11 (in binary) = 3(in decimal)
a | b
<< 3

Lo XOR bit per bit verifica due numeri binari e restituisce valori di bit pari a 1 per posizioni in cui entrambi i bit sono diversi; se sono uguali il risultato è 0.

// a ^ b = 10 ^ 11 = 01 (in binay) = 1 (in decimal)
a ^ b
<< 1

Lo spostamento a sinistra bit per bit sposta tutti i bit nel numero a sinistra e riempie le posizioni di bit vuote con 0 (spostamento a sinistra) o 1 (spostamento a sinistra senza segno).

// c = 0101 (in binary)
var c = 5
// bitwise left shift: c << 1 = 1010 (in binary) = 10 (in decimal)
c << 1
<< 1

Lo spostamento a destra bit per bit sposta tutti i bit nel numero a destra.

// c >> 1 = 010 (in binary) = 2 (in decimal)
c >> 1
<< 2

Il complemento bit per bit inverte i bit in un singolo numero binario.

// ~c -> 1010 (in binary) -> 10 (in decimal), 2’s compliment of 10 will be -6.
~c
<< -6

Verifica se il numero è Potenza di 2 o meno

Dato numero n, per verificare se il numero è in 2^nforma per not, possiamo usare l'espressione: if(n & n — 1 == 0).

// n = 10000
var n = 16 // 2⁴
// n — 1 = 15 (in decimal) = 01111
// n & (n — 1) = 10000 & 01111 = 0
n & (n — 1)
<< 0

Per un dato numero n, per moltiplicare il numero con 2^kpossiamo usare l'espressione: n ≪ k.

var n = 16
// 16*(2^1) = 32
n << 1
<< 32

Per un dato numero n, per dividere il numero con 2^kpossiamo usare l'espressione: n ≫ k.

var n = 16
// 16/(2²) = 4
n >> 2
<< 4

C'è un algoritmo di bit-twiddling da sostituire mid = (low + high) / 2(usato in Binary Search e Merge Sort) con qualcosa di molto più veloce?

Possiamo usare mid = (low + high) >> 1.

Trovare il Modulo di un dato numero

Per un dato numero n, per trovare il %8possiamo usare l'espressione: n & 0x7. Allo stesso modo, per trovare %32, usa l'espressione: n & 0x1F.

var n = 20
// 20%8 = 4
n & 0x7
<< 4

Verifica se il bit K-esimo è impostato o meno

Supponiamo che il numero dato sia n. Quindi per controllare il K-thbit possiamo usare l'espressione: n & (1 ≪ K 1). Se l'espressione è vera, allora possiamo dire che il K-th bit è impostato (cioè impostato a 1).

// n = 01001011 (in binary)
var n = 75
var k = 4
// 1 << k — 1 = 00001000 (in binary)
// n & (1 << k — 1) = 01001011 & 00001000 = 00001000 = 8 (in decimal)
n & (1 << k — 1)
<< 8

Per un dato numero n, per impostare il K-thbit possiamo usare l'espressione: n | 1 ≪ (K — 1). Supponiamo di dover impostare il 3° bit di n.

// n = 01001011 (in binary)
var n = 75
var k = 3
// 1 << k — 1 = 00000100 (in binary)
// n | (1 << k — 1) = 01001011 | 00000100 = 01001111 (in binary) = 79 (in decimal)
n | (1 << k — 1)
<< 79

Per cancellare K-thbit di un dato numero n, possiamo usare l'espressione: n & ~(1 ≪ K — 1).

// n = 01001011 (in binary)
var n = 75
var k = 3
// 1 << k — 1 = 00000100 (in binary)
// n & (1 << k — 1) = 01001011 & 00000100 = 0 (in binary) = 0 (in decimal)
n & (1 << k — 1)
<< 0

Per un dato numero n, se k-thbit è 0, attivalo su 1e, in caso 1affermativo, impostalo su 0. Possiamo usare l'espressione: n ^(1 ≪ k –1).

// n = 01001011 (in binary) -> toggle(n, k) = 01001111
var n = 75
var k = 3
// 1 << k — 1 = 00000100 (in binary)
// n ^ (1 << k — 1) = 01001011 ^ 00000100 = 01001111 (in binary) = 79 (in decimal)
n ^ (1 << k — 1)
<< 79

Per un dato numero n, per commutare un bit più a destra possiamo usare l'espressione: n & n — 1.

// n = 01001011 (in binary)
var n = 75
// n — 1 = 74 = 01001010
// n & n — 1 = 01001011 & 01001010 = 01001010 = 74
n & n — 1
<< 74