Utilizzando manipolazione dei bit di dire se un intero senza segno può essere espresso nella forma 2^n-1

Question

per verificare se un numero intero senza segno è nella forma 2^n-1 usiamo:

x&(x+1) 

cosa dovrebbe alla parità ? Cioè,

x&(x+1) == ? 

Answer 1

A complemento delle risposte esistenti, ecco un breve spiegazione del perché i numeri x che non sono della forma 0b00000 (zero) o 0b0111..11 (tutte le cifre più basse impostati, questi sono tutti i numeri 2^n-1 per n > 0) non hanno la proprietà x&(x+1) == 0.

Per un numero x della forma 0b????1000..00, x+1 ha le stesse cifre di x eccezione del bit meno significativo, così x & (x+1) ha almeno un bit impostato, il bit che è stato visualizzato come messe in x. In via più breve spiegazione:

x  0b????1000..00 
x+1  0b????1000..01 
x&(x+1) 0b????10000000 

Per un numero x della forma 0b????10111..11:

x  0b????10111..11 
x+1  0b????110000000 
x&(x+1) 0b????10000..00 

In conclusione, se x non è zero o scritto in binario con tutte le cifre più basse impostati, allora x&(x+1) non è zero.

Answer 2

Un certo numero di forma 2^n-1 avrà tutti i bit fino al bit set esimo. Ad esempio, 2^3-1 (7) è:

0b0111 

Se aggiungiamo un per questo, otteniamo 8:

0b1000 

Poi, l'esecuzione di un bit a bit e, vediamo che otteniamo zero, perché non il bit è impostato su entrambi i numeri. Se iniziamo con un numero non del formato 2^n+1, il risultato sarà diverso da zero.

Answer 3

Zero. Se X è 2^N-1, è una stringa ininterrotta di 1 in binario. Uno più di quello è un 1 seguito da una stringa di zero della stessa lunghezza di X, quindi i due numeri non hanno 1 bit in comune in nessuna posizione, quindi l'AND dei due è zero.