5
Qualcuno può aiutare che cosa significa n&-n ?? E qual è il significato di esso.Significato di bit a bit e (&) di un numero positivo e negativo?
A
risposta
0
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).
+1
Beh, questo non funziona del tutto, poiché restituirebbe true per zero, che generalmente non è considerato una potenza di due. E il trucco è più utile di quello - vedi le altre risposte. – JasonD
+0
'(n & (n-1)) == 0' sarebbe stato più semplice. –
3
In quasi tutti i sistemi a cui la maggior parte della gente interessa, offre la massima potenza di 2 che è uniformemente divisibile per.
+0
ma attenzione che dipende dal comportamento definito dall'implementazione, quindi non è tecnico. – tletnes
+3
@ tletnes La portabilità è un termine relativo. Non è portatile per quanto riguarda lo standard C++, è vero. Ma è probabilmente portabile su più sistemi che persino con un compilatore C++ conforme o quasi conforme. –
1
È 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
14
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)
+0
Sì, e questo è utile se ad es. si vuole eseguire una rapida iterazione su tutti i bit impostati in n; 'per (; j = n &(-n); n^= j)' –
-2
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
0
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`
0
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.
Può causare un comportamento indefinito o semplicemente generare un valore definito e/o di implementazione definito a seconda del valore di 'n' e della rappresentazione di numeri negativi (complemento di esempio 1 e complemento a 2). Sono sicuro che è qualcosa che non vuoi usare/incontrare. –
Non ho mai visto un vero complemento a 1. –
@ Cthulhu, ho ma è stato tanto tempo fa. Il C++ non era ancora stato inventato. –