streamalism.org

1. Oversikt

I denne artikkelen ser vi hvordan vi finner den største effekten på 2 som er mindre enn det gitte tallet.

For eksemplene våre tar vi prøveinngangen 9. 20 er 1, den minst gyldige inngangen som vi kan finne effekten av 2 mindre enn den gitte inngangen er 2. Derfor vil vi bare betrakte innganger større enn 1 som gyldige .

2. Naiv tilnærming

La oss starte med 20, som er 1, og vi vil fortsett å multiplisere tallet med 2 til vi finner et tall som er mindre enn inngangen:

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

La oss forstå koden for eksempel inngang = 9.

Startverdien for firstPowerOf2 er 1 og nextPowerOf2 er 2. Som vi kan se, er 2 <9 sant, og vi kommer inn i mens løkken.

For den første iterasjonen, firstPowerOf2 er 2 og nextPowerOf2 er 2 * 2 = 4. Igjen 4 <9 så la oss fortsette mens løkken.

For den andre iterasjonen, firstPowerOf2 er 4 og nextPowerOf2 er 4 * 2 = 8. Nå 8 <9, la oss fortsette.

For den tredje iterasjonen, firstPowerOf2 er 8 og nextPowerOf2 er 8 * 2 = 16. Mens tilstand 16 <9 er falsk, så den bryter ut av mens løkken. 8 er den største kraften på 2 som er mindre enn 9.

La oss kjøre noen tester for å validere koden vår:

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

Tidskompleksiteten til løsningen vår er O (log₂(N)). I vårt tilfelle gjentok vi loggen₂(9) = 3 ganger.

3. Bruke Math.log

Loggbase 2 vil gi hvor mange ganger vi kan dele et tall med 2 rekursivt med andre ord, Logg₂ av et tall gir kraften til 2. La oss se på noen eksempler for å forstå dette.

Logg₂(8) = 3 og logg₂(16) = 4. Generelt kan vi se at y = logg₂x hvor x = 2y.

Derfor, hvis vi finner et tall som kan deles med 2, trekker vi 1 fra det slik at vi unngår et scenario der tallet er en perfekt styrke på 2.

Math.log er logg₁₀. Å beregne logg₂(x), kan vi bruke formelloggen₂(x) = logg₁₀(x) / logg₁₀(2)

La oss sette det i kode:

public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2 (long input) {Assert.isTrue (input> 1, "Invalid input"); lang temp = inngang; hvis (input% 2 == 0) {temp = input - 1; } lang kraft = (lang) (Math.log (temp) / Math.log (2)); langt resultat = (langt) Math.pow (2, kraft); returresultat; }

Forutsatt at prøveinngangen vår er 9, startverdien av temp er 9.

9% 2 er 1, så vår temp variabel er 9.Her bruker vi modulo divisjon, som vil gi resten av 9/2.

For å finne loggen₂(9), logger vi oss₁₀(9) / logg₁₀(2) = 0.95424 / 0.30103 ~= 3.

Nå, den resultat er 23 som er 8.

La oss bekrefte koden vår:

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

I virkeligheten, Math.pow vil gjøre den samme iterasjonen som vi gjorde i tilnærming 1. Derfor kan vi si at for denne løsningen også tidskompleksiteten er O (Log₂(N)).

4. Bitvis teknikk

For denne tilnærmingen bruker vi bitvis skiftteknikk. La oss først se på de binære representasjonene for kraften til 2 med tanke på at vi har 4 biter som representerer tallet

Når vi ser nøye på, kan vi observere at vi kan beregne kraften til 2 ved å venstre bytte bytene for 1. dvs. 22 er venstre skiftbyte for 1 av 2 steder og så videre.

La oss kode ved hjelp av bitshift-teknikken:

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach (long input) {Assert.isTrue (input> 1, "Invalid input"); langt resultat = 1; lang effektOf2; for (lang i = 0; i <Lang.BYTES * 8; i ++) {powerOf2 = 1 <= inngang) {pause; } resultat = powerOf2; } returnere resultat; }

I koden ovenfor bruker vi lang som vår datatype, som bruker 8 byte eller 64 bits. Så vi beregner kraften fra 2 til 264. Vi bruker bitshiftoperatøren << for å finne kraften til 2. For vår inngang 9, etter 4. iterasjon, verdien av powerOf2 = 16 og resultat = 8 hvor vi bryter ut av løkken som 16> 9 den inngang.

La oss sjekke om koden vår fungerer som forventet:

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

De worst-case tidskompleksitet for denne tilnærmingen er igjen O (logg₂(N)), lik det vi så for den første tilnærmingen. Denne tilnærmingen er imidlertid bedre som en bit shift drift er mer effektiv sammenlignet med multiplikasjon.

5. Bitvis OG

For vår neste tilnærming bruker vi denne formelen 2n OG 2n -1 = 0.

La oss se på noen eksempler for å forstå hvordan det fungerer.

Den binære representasjonen av 4 er 0100, og 3 er 0011.

La oss gjøre en bitvis OG operere på disse to tallene. 0100 OG 0011 er 0000. Vi kan si det samme for hvilken som helst kraft på 2 og et tall mindre enn det. La oss ta 16 (24) og 15 som er representert som 1000, 0111 henholdsvis. Igjen ser vi at bitvis OG på disse to resulterer i 0. Vi kan også si at OG-operasjonen på et hvilket som helst annet tall bortsett fra disse 2 ikke vil resultere i et 0.

La oss se koden for å løse dette problemet ved hjelp av bitvis AND:

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd (long input) {Assert.isTrue (input> 1, "Invalid input"); langt resultat = 1; for (lang i = inngang - 1; i> 1; i--) {hvis ((i & (i - 1)) == 0) {resultat = i; gå i stykker; }} returner resultat; }

I koden ovenfor sløyfer vi over tall mindre enn inngangen vår. Hver gang vi finner bitvis OG av et tall og nummer-1 er null, bryter vi ut av sløyfen, ettersom vi vet at tallet vil være en styrke på 2. I dette tilfellet for vårt utvalg inngang 9, bryter vi ut av løkken når Jeg = 8 og Jeg – 1 = 7.

La oss nå bekrefte et par scenarier:

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

I verste fall tidskompleksitet for denne tilnærmingen er O (N / 2) når inngangen har en nøyaktig effekt 2. Som vi kan se, er dette ikke den mest effektive løsningen, men det er godt å kjenne denne teknikken, da den kan komme til nytte når man takler lignende problemer.

6. Konklusjon

Vi har sett forskjellige tilnærminger for å finne den største effekten av 2 som er mindre enn det gitte tallet. Vi la også merke til hvordan bitvis operasjoner i noen tilfeller kan forenkle beregninger.

Den komplette kildekoden med enhetstester for denne artikkelen finner du på GitHub.