Potenza di 2
Lezione 9 di 17 del corso Manipolazione dei bit di Coddy.
Se hai giocato abbastanza con i numeri binari, ormai ti sarai reso conto che tutte le potenze di 2 includono solo 1 bit impostato (bit impostato si riferisce a «1»). Per esempio: (2)10 = (10)2 , (4)10 = (100)2 , (8)10 = (1000)2 e così via.
In questa lezione parleremo del problema seguente:
Determinare se un numero dato è o meno una potenza di 2 usando la manipolazione dei bit.
Va bene! In che modo l'osservazione precedente ci sarà utile? Scopriamolo.
- Supponiamo che ci venga dato (8)10 e sappiamo che è una potenza di 2.
- Sottraendo 1 otteniamo (7)10, che equivale a (0111)2.
- Se eseguiamo l'operazione AND ( & ) su 7 e 8, otteniamo 0.
- Interessante, vero? Verifichiamolo con un altro numero che è anch'esso una potenza di 2. Prendiamo (32)10, che equivale a (100000)2, e sottraiamo 1: otteniamo (31)10 = (011111)2. Otteniamo di nuovo 0!
- Quindi, per generalizzare, possiamo dire che, affinché il numero, chiamiamolo x, sia una potenza di 2, ( x & (x-1) ) sarà sempre «0»?
Usando questa osservazione possiamo risolvere facilmente il problema senza dover usare una libreria matematica e la sua funzione di potenza, né un ciclo: lo abbiamo risolto con una complessità temporale O(1)! Non è fantastico? È così che la manipolazione dei bit può aiutarci a ottimizzare i nostri programmi e a rendere il codice meno complicato.
Sfida
FacileDato un numero, determina se è pari o meno usando la manipolazione dei bit.
Provalo tu
#include <iostream>
using namespace std;
bool IsPowerOf2(int num) {
// Scrivi il codice qui
}Tutte le lezioni di Manipolazione dei bit
Esercitati da solo: Compilatore C++ online