2010-08-09 25 views
14

La funzione seguente è valutata per valutare se un numero è potenza intera di 4. Non capisco come funziona?valuta se un numero è potenza intera di 4

bool fn(unsigned int x) 
{ 
if (x == 0) return false; 
if (x & (x - 1)) return false; 
return x & 0x55555555; 
} 
+0

x & (x - 1) rimuove il 1 bit più basso da un numero. – starblue

risposta

36

la prima condizione esclude 0, che non è ovviamente una potenza di 4 ma sarebbe errato passare le due seguenti prove. (MODIFICA: No, non lo farebbe, come sottolineato. Il primo test è ridondante.)

Il prossimo è un bel trucco: ritorna vero se e solo se il numero è un potere di 2. Una potenza di due è caratterizzata dal fatto di avere solo un bit impostato. Un numero con un bit impostato meno uno produce un numero con tutti i bit precedenti a quel bit impostato (ad esempio 0x1000 meno uno è 0x0111). E quei due numeri, e ottieni 0. In ogni altro caso (cioè non la potenza di 2), ci sarà almeno un bit che si sovrappone.

Quindi a questo punto, sappiamo che è una potenza di 2.

x & 0x55555555 rendimenti non-zero (= true) se del caso, anche Bit è impostato (bit 0, bit 2, bit 4, bit 6, ecc). Ciò significa che è il potere di 4. (cioè 2 non passa, ma 4 passaggi, 8 non passa, 16 passaggi, ecc.).

+0

mi ha battuto di 2 secondi. –

+1

La prossima volta, John :) – EboMike

+2

L'ultimo controllo non renderebbe superfluo il primo controllo? '0 & 0x55555555' è' 0' per quanto mi ricordo. – strager

1

Ogni potenza di 4 deve essere in forma di 1 seguito da un numero pari di zeri (rappresentazione binaria): 100 ... 00:

100 = 4

10000 = 16

1000000 = 64

  1. La prima prova ("se") è evidente.

  2. Quando sottraendo 1 da un certo numero di forma XY100 ... 00 si ottiene XY011 ... 11. Quindi, il secondo test verifica se c'è più di un bit "1" nel numero (XY in questo esempio).

  3. L'ultimo test verifica se questo singolo "1" è nella posizione corretta, cioè bit # 2,4,6 ecc. In caso contrario, il mascheramento (&) restituirà un risultato diverso da zero.

Problemi correlati