streamalism.org

1. Pregled

U ovom ćemo članku vidjeti kako pronaći najveću snagu 2 koja je manja od zadanog broja.

Za naše primjere uzet ćemo uzorak unosa 9. 20 je 1, najmanje valjani ulaz za koji možemo pronaći snagu za 2 manju od zadane vrijednosti 2. Stoga ćemo ulaze veće od 1 smatrati valjanima .

2. Naivni pristup

Počnimo s 20, što je 1, pa ćemo množite broj sa 2 dok ne nađemo broj koji je manji od unosa:

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

Razumijemo kod za uzorak ulazni = 9.

Početna vrijednost za firstPowerOf2 je 1 i nextPowerOf2 je 2. Kao što vidimo, 2 <9 je istina i ulazimo u while petlju.

Za prvu iteraciju, firstPowerOf2 je 2 i nextPowerOf2 je 2 * 2 = 4. Opet 4 <9, tako da nastavljamo while petlju.

Za drugu iteraciju, firstPowerOf2 je 4 i nextPowerOf2 je 4 * 2 = 8. Sad 8 <9, idemo dalje.

Za treću iteraciju, firstPowerOf2 je 8 i nextPowerOf2 je 8 * 2 = 16. Dok je uvjet 16 <9 netačan, pa izbija iz while petlje. 8 je najveća snaga 2 koja je manja od 9.

Pokrenimo nekoliko testova za provjeru valjanosti našeg koda:

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

Složenost vremena našeg rješenja je O (log₂(N)). U našem smo slučaju ponavljali zapisnik₂(9) = 3 puta.

3. Korištenje Matematika.log

Dnevnik baza 2 dat će koliko puta možemo rekurzivno podijeliti broj sa 2 drugim riječima, zapisnik₂ broja daje snagu 2. Pogledajmo neke primjere kako bismo to razumjeli.

zapisnik₂(8) = 3 i log₂(16) = 4. Općenito možemo vidjeti da je y = log₂x gdje je x = 2y.

Stoga, ako nađemo broj koji je djeljiv sa 2, od njega oduzmemo 1 tako da izbjegnemo scenarij u kojem je broj savršena stepenica 2.

Matematika.log je zapisnik₁₀. Za izračunavanje dnevnika₂(x), možemo koristiti formulu log₂(x) = zapisnik₁₀(x) / zapisnik₁₀(2)

Stavimo to u kod:

javni long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2 (dugi ulaz) {Assert.isTrue (input> 1, "Invalid input"); duga temp = unos; if (input% 2 == 0) {temp = input - 1; } duga snaga = (duga) (Math.log (temp) / Math.log (2)); dugi rezultat = (dugački) Math.pow (2, snaga); povratni rezultat; }

Pretpostavljajući da je naš uzorak unosa 9, početna vrijednost temp je 9.

9% 2 je 1, dakle naš temp varijabla je 9.Ovdje koristimo modularnu podjelu, koja će dati ostatak od 9/2.

Da biste pronašli zapisnik₂(9), bilježimo₁₀(9) / zapisnik₁₀(2) = 0.95424 / 0.30103 ~= 3.

Sada, proizlaziti je 23 što je 8.

Provjerimo naš kôd:

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

U stvarnosti, Matematika.pow radit ćemo istu ponavljanje kao i mi u pristupu 1. Stoga možemo reći da i za ovo rješenje, složenost vremena je O (Log₂(N)).

4. Bitovna tehnika

Za ovaj pristup koristit ćemo tehniku ​​pomicanja u bitovima. Prvo, pogledajmo binarne prikaze snage 2 s obzirom da imamo 4 bita za predstavljanje broja

Promatrajući izbliza, možemo primijetiti da možemo izračunajte snagu 2 pomicanjem bajtova ulijevo za 1. tj. 22 su lijevi bajtovi smjene za 1 sa 2 mjesta i tako dalje.

Kodirajmo tehnikom bitshift:

javni long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach (dugi ulaz) {Assert.isTrue (input> 1, "Invalid input"); dugi rezultat = 1; duga snagaO2; for (long i = 0; i <Long.BYTES * 8; i ++) {powerOf2 = 1 <= input) {break; } rezultat = snagaO2; } vratiti rezultat; }

U gornjem kodu koristimo dugo kao naš tip podataka koji koristi 8 bajtova ili 64 bita. Tako ćemo izračunati snagu od 2 do 264. Koristimo operator pomaka bitova << za pronalaženje snage 2. Za naš uzorak uzorka 9, nakon 4. iteracije, vrijednost powerOf2 = 16 i proizlaziti = 8 gdje izbijamo iz petlje kao 16> 9 the ulazni.

Provjerimo radi li naš kod prema očekivanjima:

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

The najgora vremenska složenost za ovaj pristup je opet O (log₂(N)), slično onome što smo vidjeli za prvi pristup. Međutim, ovaj je pristup bolji kao rad pomaka bita učinkovitiji je u usporedbi s množenjem.

5. Bitno I

Za sljedeći pristup koristit ćemo ovu formulu 2n I 2n -1 = 0.

Pogledajmo nekoliko primjera kako bismo shvatili kako to funkcionira.

Binarni prikaz 4 je 0100, a 3 je 0011.

Napravimo bitnu I operaciju na ova dva broja. 0100 I 0011 je 0000. To možemo reći za bilo koju snagu 2 i broj manji od nje. Uzmimo 16 (24) i 15 koji je predstavljen kao 1000, 0111 odnosno. Opet vidimo da bitni AND na ove dvije rezultira 0. Možemo također reći da operacija AND na bilo kojem drugom broju osim ova dva neće rezultirati 0.

Pogledajmo kod za rješavanje ovog problema pomoću bitnog I:

javni long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd (dugi ulaz) {Assert.isTrue (input> 1, "Invalid input"); dugi rezultat = 1; for (long i = input - 1; i> 1; i--) {if ((i & (i - 1)) == 0) {result = i; pauza; }} vratiti rezultat; }

U gornjem kodu petljamo brojeve manje od našeg unosa. Kad god pronađemo bitni AND broja i broja-1 je nula, mi prekinemo petlju, jer znamo da će broj biti stepen 2. U ovom slučaju za naš uzorak ulazni 9, izbijamo iz petlje kada ja = 8 i ja – 1 = 7.

Sada, provjerimo nekoliko scenarija:

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

Najgori slučaj vremenska složenost za ovaj pristup je O (N / 2) kada je ulaz točna snaga 2. Kao što vidimo, ovo nije najučinkovitije rješenje, ali dobro je poznavati ovu tehniku ​​jer bi mogla doći u obzir pri rješavanju sličnih problema.

6. Zaključak

Vidjeli smo različite pristupe za pronalaženje najveće snage 2 koja je manja od zadanog broja. Također smo primijetili kako postupci u bitovima mogu pojednostaviti izračunavanje u nekim slučajevima.

Kompletni izvorni kod s jediničnim testovima za ovaj članak možete pronaći na GitHubu.