La potenza più grande di 2 che è inferiore al numero fornito con Java

1. Panoramica

In questo articolo vedremo come trovare la potenza più grande di 2 inferiore al numero specificato.

Per i nostri esempi, prenderemo l'input di esempio 9. 20 è 1, l'input meno valido per il quale possiamo trovare la potenza di 2 inferiore all'input dato è 2. Quindi considereremo validi solo gli input maggiori di 1 .

2. Approccio ingenuo

Iniziamo con 20, che è 1, e continueremo a moltiplicare il numero per 2 fino a trovare un numero inferiore all'input :

public long findLargestPowerOf2LessThanTheGivenNumber(long input) { Assert.isTrue(input > 1, "Invalid input"); long firstPowerOf2 = 1; long nextPowerOf2 = 2; while (nextPowerOf2 < input) { firstPowerOf2 = nextPowerOf2; nextPowerOf2 = nextPowerOf2 * 2; } return firstPowerOf2; }

Comprendiamo il codice per l' input di esempio = 9.

Il valore iniziale di firstPowerOf2 è 1 e nextPowerOf2 è 2. Come possiamo vedere, 2 <9 è vero e entriamo nel ciclo while.

Per la prima iterazione, firstPowerOf2 è 2 e nextPowerOf2 è 2 * 2 = 4. Di nuovo 4 <9 quindi continuiamo il ciclo while.

Per la seconda iterazione, firstPowerOf2 è 4 e nextPowerOf2 è 4 * 2 = 8. Ora 8 <9, andiamo avanti.

Per la terza iterazione, firstPowerOf2 è 8 e nextPowerOf2 è 8 * 2 = 16. La condizione while 16 <9 è falsa, quindi interrompe il ciclo while. 8 è la potenza più grande di 2 che è inferiore a 9.

Eseguiamo alcuni test per convalidare il nostro codice:

assertEquals(8, findPowerOf2LessThanTheGivenNumber(9)); assertEquals(16, findPowerOf2LessThanTheGivenNumber(32)); 

La complessità temporale della nostra soluzione è O (log 2 (N)) . Nel nostro caso, abbiamo iterato log 2 (9) = 3 volte.

3. Utilizzo di Math.log

Log in base 2 darà quante volte possiamo dividere un numero per 2 ricorsivamente, in altre parole, log 2 di un numero dà la potenza di 2 . Diamo un'occhiata ad alcuni esempi per capirlo.

log 2 (8) = 3 e log 2 (16) = 4. In generale, possiamo vedere che y = log 2 x dove x = 2y.

Quindi, se troviamo un numero divisibile per 2, sottraiamo 1 da esso in modo da evitare uno scenario in cui il numero è una potenza perfetta di 2.

Math.log è il registro 10 . Per calcolare il log 2 (x), possiamo usare la formula log 2 (x) = log 10 (x) / log 10 (2)

Mettiamolo nel codice:

public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(long input) { Assert.isTrue(input > 1, "Invalid input"); long temp = input; if (input % 2 == 0) { temp = input - 1; } long power = (long) (Math.log(temp) / Math.log(2)); long result = (long) Math.pow(2, power); return result; }

Supponendo che il nostro input di esempio sia 9, il valore iniziale di temp è 9.

9% 2 è 1, quindi la nostra variabile temporanea è 9.Qui stiamo usando la divisione modulo, che darà il resto di 9/2.

Per trovare il log 2 (9), facciamo log 10 (9) / log 10 (2) = 0,95424 / 0,30103 ~ = 3.

Ora, il risultato è 23 che è 8.

Verifichiamo il nostro codice:

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(9)); assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2(32));

In realtà, Math.pow eseguirà la stessa iterazione che abbiamo fatto nell'approccio 1. Quindi possiamo dire che anche per questa soluzione, la complessità temporale è O (Log 2 (N)) .

4. Tecnica bit per bit

Per questo approccio, useremo la tecnica di spostamento bit per bit. Per prima cosa, diamo un'occhiata alle rappresentazioni binarie per la potenza di 2 considerando che abbiamo 4 bit per rappresentare il numero

20 1 0001
21 2 0010
22 4 0100
23 8 1000

Guardando da vicino, possiamo osservare che possiamo calcolare la potenza di 2 spostando a sinistra i byte per 1 . cioè. 22 è lasciato shift byte per 1 per 2 posti e così via.

Programmiamo usando la tecnica bitshift:

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(long input) { Assert.isTrue(input > 1, "Invalid input"); long result = 1; long powerOf2; for (long i = 0; i < Long.BYTES * 8; i++) { powerOf2 = 1 <= input) { break; } result = powerOf2; } return result; }

Nel codice sopra, stiamo usando long come il nostro tipo di dati, che utilizza 8 byte o 64 bit. Quindi calcoleremo la potenza di 2 fino a 264. Stiamo usando l'operatore di spostamento di bit << per trovare la potenza di 2. Per il nostro input di esempio 9, dopo la 4a iterazione, il valore di powerOf2 = 16 e risultato = 8 dove interrompiamo il ciclo come 16> 9 l' ingresso .

Controlliamo se il nostro codice funziona come previsto:

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(9)); assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach(32));

La complessità temporale nel caso peggiore per questo approccio è ancora O (log 2 (N)) , simile a quella che abbiamo visto per il primo approccio. Tuttavia, questo approccio è migliore in quanto un'operazione di spostamento di bit è più efficiente rispetto alla moltiplicazione .

5. AND bit per bit

Per il nostro prossimo approccio, useremo questa formula 2n AND 2n -1 = 0 .

Diamo un'occhiata ad alcuni esempi per capire come funziona.

La rappresentazione binaria di 4 è 0100 e 3 è 0011 .

Facciamo un'operazione AND bit per bit su questi due numeri. 0100 AND 0011 è 0000 . Possiamo dire lo stesso per qualsiasi potenza di 2 e un numero inferiore a esso. Prendiamo 16 (24) e 15 che è rappresentato rispettivamente come 1000 , 0111 . Di nuovo, vediamo che l'AND bit per bit su questi due risultati in 0. Possiamo anche dire che l'operazione AND su qualsiasi altro numero oltre a questi 2 non risulterà in uno 0.

Vediamo il codice per risolvere questo problema utilizzando AND bit per bit:

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(long input) { Assert.isTrue(input > 1, "Invalid input"); long result = 1; for (long i = input - 1; i > 1; i--) { if ((i & (i - 1)) == 0) { result = i; break; } } return result; }

Nel codice sopra, eseguiamo un ciclo su numeri inferiori al nostro input. Ogni volta che troviamo l'AND bit per bit di un numero e il numero 1 è zero, usciamo dal ciclo, poiché sappiamo che il numero sarà una potenza di 2. In questo caso per il nostro input campione 9, interrompiamo il ciclo quando i = 8 e i - 1 = 7.

Ora, verifichiamo un paio di scenari:

assertEquals(8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(9)); assertEquals(16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd(32));

La complessità temporale nel caso peggiore per questo approccio è O (N / 2) quando l'input è una potenza esatta 2. Come possiamo vedere, questa non è la soluzione più efficiente, ma è bene conoscere questa tecnica come potrebbe venire utile quando si affrontano problemi simili.

6. Conclusione

Abbiamo visto approcci diversi per trovare la potenza massima di 2 inferiore al numero dato. Abbiamo anche notato come le operazioni bit per bit possono semplificare i calcoli in alcuni casi.

Il codice sorgente completo con gli unit test per questo articolo può essere trovato su GitHub.