Significato di bit a bit e (&) di un numero positivo e negativo?

Question

Qualcuno può aiutare che cosa significa n&-n ?? E qual è il significato di esso.

Answer 1

Credo che sia un trucco capire se n è una potenza di 2. (n == (n & -n)) IFF n è una potenza di 2 (1,2,4,8).

Answer 2

In quasi tutti i sistemi a cui la maggior parte della gente interessa, offre la massima potenza di 2 che è uniformemente divisibile per.

Answer 3

È solo un bit per bit e del numero. I numeri negativi sono rappresentati come two's complement.

Così, per esempio, bit per bit e del 7 & (-7) è x00000111 & x11111001 = x00000001 = 1

Answer 4

E 'un vecchio trucco che dà un numero con un singolo bit in esso, il bit di fondo che è stato impostato in n. Almeno in due complemento dell'aritmetica, che è quasi universale in questi giorni.

Il motivo per cui funziona: il numero negativo di un numero viene prodotto invertendo il numero, quindi aggiungendo 1 (questa è la definizione del complemento a due). Quando aggiungi 1, ogni bit che inizia nella parte inferiore che è impostata, si riverserà nel bit successivo più alto; questo si ferma una volta raggiunto un bit zero. Quei bit overflow saranno tutti zero, e i bit sopra l'ultimo influenzati saranno l'uno inverso l'uno dell'altro, quindi l'unico bit rimasto è quello che ha fermato la cascata - quello che è iniziato come 1 ed è stato invertito a 0.

PS Se siete preoccupati che attraversa un complemento aritmetica ecco una versione che funziona sia con:

n & (~n + 1) 

Answer 5

Come @aestrivex ha detto, è un modo di scrivere 1.Even ho incontrato questo

for (int y = x; y > 0; y -= y & -y) 

e significa solo y = y-1 perché
(-7) è x00000111 & x11111001 = x00000001 = 1

Answer 6

avrei aggiungere un esempio autoesplicativo al 0.123.457 La meravigliosa esposizione di.

010010000 | +144 ~ 
----------|------- 
101101111 | -145 + 
     1 | 
----------|------- 
101110000 | -144 

101110000 | -144 & 
010010000 | +144 
----------|------- 
000010000 | 16` 

Answer 7

Perché x & -x = {0, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32} per x da 0 a 32. E 'usato per jumpy in per le sequenze per alcune applicazioni. Le applicazioni possono essere per memorizzare record accumulati.

for(;x < N;x += x&-x) { 
    // do something here 
    ++tr[x]; 
} 

Il ciclo attraversa molto velocemente perché cerca la potenza successiva di due per saltare.