Stepen dvojke

Za druge potrebe, vidi Stepen dvojke (višeznačna odrednica).

U matematici, stepen dvojke označava broj forme 2ⁿ gde je n ceo broj, tj. rezultat stepenovanja brojem dva kao bazom i celim brojem n kao eksponentom.

U kontekstu u kom se razmatraju samo celi brojevi, n je ograničen na ne-negativne vrednosti,^[1] tako da imamo 1, 2, i 2 pomnožene samim sobom određeni broj puta.^[2]

Zbog toga što je dva osnova u sistemu binarnih brojeva, stepen dvojke je čest u računarskoj nauci. Zapisan u binarnom obliku, stepen dvojke uvek ima formu 100…000 ili 0.00…001, baš kao i stepen desetke u decimalnom sistemu.

Izrazi i jednačine [uredi | uredi izvor]

Verbalni izrazi, matematičke oznake, i izrazi računarskog programiranja koriste stepen dvojke ili funkciju uključujući:

2 na n

2 na stepen n

2 stepen n

stepen(2, n)

st(2, n)

2ⁿ

1 << n

2 ^ n

2 ** n

2 [3] n

2 ↑ n

A(n - 3, 3) + 3

H_{3}(2,n)

2\to n

2\to n\to 1

Računarska nauka[uredi | uredi izvor]

Dva na stepen n, napisano kao $2 n$ , je broj načina na koji se bitovi u binarnom sistemu dužine n mogu organizovati. Reč, tumačena kao neoznačen ceo broj, može biti predstavljena vrednostima od 0 (000…000) do $2 n - 1$ (111…111) zaključno. Odgovarajuća celobrojna vrednost može biti pozitivna, negativna ili nula; vidi predstave označenih brojeva. U svakom slučaju, jedan manje od stepena dvojke je često gornja granica celih brojeva kod binarnih računara. Kao posledica, brojevi ove forme se često pojavljuju u računarskom softveru. Na primer, video igrica pokrenuta na 8-bitnom sistemu može ograničiti rezultat ili broj predmeta koje igrač može nostiti na 255— rezultat korišćenja bajta, koji je dugačak 8 bita, da sačuva broj, dajući maksimalnu vrednost $28 - 1 = 255$ . Na primer, u delu Legenda o Zeldi, glavni lik je ograničen da čuva 255 rupija (valuta u igrici) u bilo kom trenutku, dok se video igra Pek-Men čuveno gasi na nivou 255.

Stepen dvojke se koristi za merenje računarske memorije. Bajt sada sadrži osam bita (oktet, kao rezultat mogućnosti 256 vrednosti (2⁸). (Izraz bajt je nekad značio (i u nekim slučajevima još uvek znači) skup bitova, uobičajeno 5 do 32 bita, pre nego samo 8-bitnih jedinica.) Prefiks kilo, u vezi sa bajtom, može biti, i oduvek je bio, korišćen kao 1,024 (2¹⁰). Međutim, uopšte, izraz kilo je bio korišćen u Međunardnom sistemu jedinica u značenju 1,000 (10³). Binarni prefiksi su bili standardizovani, kao što kibi (Ki) znači 1,024. Skoro svi procesorski registri imaju veličinu stepena dvojke, 32 ili 64 su najčešći.

Stepen dvojke se pojavljuje na drugim mestima takođe. Za mnoge diskove, barem jedna veličina sektora, broj sektora po stazi, i broj staza po površini diska je stepen dvojke. Veličina logičkog bloka je skoro uvek stepen dvojke.

Brojevi koji nisu stepen dvojke se pojavljuju u mnogim situacijama, kao što su video rezolucije, ali su oni često zbir ili proizvod samo dva ili tri stepena dvojke, ili stepen dvojke minus jedan. Na primer,

640 = 512 + 128 = 128 \times 5

, i

480 = 32 \times 15

. Na drugi način, oni imaju prilično uobičajene šablone bitova.

Mersenovi prosti brojevi[uredi | uredi izvor]

Slično, prost broj (kao 257) koji je za jedan veći od pozitivnog stepena dvojke se naziva Fermaov prost broj — sam eksponent je stepen dvojke. Razlomak koji ima stepen dvojke kao delilac se naziva dvojni razlomak. Brojevi koji mogu biti predstavljeni kao zbirovi uzastopnih pozitivnih celih brojeva se nazivaju uglađeni brojevi; oni su zapravo brojevi koji nisu stepen dvojke.

Prost broj koji je za jedan manji od stepena dvojke se zove Mersenov prost broj. Na primer, prost broj 31 je Mersenov prost broj zato što je za 1 manji od 32 (2⁵).

Euklidovi elementi, 9. knjiga[uredi | uredi izvor]

Geometrijska progresija 1, 2, 4, 8, 16, 32, … (ili, u binarnom brojevnom sistemu 1, 10, 100, 1000, 10000, 100000, … ) je važna u teoriji brojeva. 9. knjiga, 36. predlog Elemenata dokazuje da ako je suma prvih n članova ove progresije prost broj (znači, Mersenov prost broj pomenut iznad), onda ova suma pomnožena n-tim članom je savršen broj. Na primer, suma prvih 5 članova niza 1 + 2 + 4 + 8 + 16 = 31, koji je prost broj. Suma 31 pomnožena sa 16 (5. član niza) je jednaka 496, koji je savršen broj.

9. knjiga, 35 Predlog, dokazuje da ako je u geometrijskom nizu prvi član oduzet od drugog i poslednjeg člana niza, onda je višak drugog prvi—tako da je višak poslednjeg sve ono pre njega. (Ovo je prepravka naše formule za geometrijski niz iznad.) Primenjujući ovo na geometrijsku progresiju 31, 62, 124, 248, 496 (koja rezultuje od 1, 2, 4, 8, 16 množenjem svih članova do 31), vidimo da 62 minus 31 je 31 kao i 496 minus 31 je zbir 31, 62, 124, 248. Stoga, brojevi 1, 2, 4, 8, 16, 31, 62, 124 i 248 dodati do 496 i dalje su svi ovi brojevi dele broj 496. Pod pretpostavkom da p deli broj 496 i nije među ovim brojevima. Pretpostavimo da su $p q$ jednaki $16 \times 31$ , ili da je 31 q, a p 16. Sada p ne može da deli 16 ili bi bilo među brojevima 1, 2, 4, 8 ili 16. Stoga, 31 ne može da deli q. I kako 31 ne deli q i q je 496, osnovna teorema aritmetike implicira da q mora da deli 16 i da bude među brojevima 1, 2, 4, 8 ili 16. Neka q bude 4, onda p mora biti 124, što je nemoguće s obzirom na to da hipoteza p nije među brojevima 1, 2, 4, 8, 16, 31, 62, 124 ili 248.

Prvih 96 stepena dvojke[uredi | uredi izvor]

2⁰	=	1	2¹⁶	=	65,536	2³²	=	4,294,967,296	2⁴⁸	=	281,474,976,710,656	2⁶⁴	=	18,446,744,073,709,551,616	2⁸⁰	=	1,208,925,819,614,629,174,706,176
2¹	=	2	2¹⁷	=	131,072	2³³	=	8,589,934,592	2⁴⁹	=	562,949,953,421,312	2⁶⁵	=	36,893,488,147,419,103,232	2⁸¹	=	2,417,851,639,229,258,349,412,352
2²	=	4	2¹⁸	=	262,144	2³⁴	=	17,179,869,184	2⁵⁰	=	1,125,899,906,842,624	2⁶⁶	=	73,786,976,294,838,206,464	2⁸²	=	4,835,703,278,458,516,698,824,704
2³	=	8	2¹⁹	=	524,288	2³⁵	=	34,359,738,368	2⁵¹	=	2,251,799,813,685,248	2⁶⁷	=	147,573,952,589,676,412,928	2⁸³	=	9,671,406,556,917,033,397,649,408
2⁴	=	16	2²⁰	=	1,048,576	2³⁶	=	68,719,476,736	2⁵²	=	4,503,599,627,370,496	2⁶⁸	=	295,147,905,179,352,825,856	2⁸⁴	=	19,342,813,113,834,066,795,298,816
2⁵	=	32	2²¹	=	2,097,152	2³⁷	=	137,438,953,472	2⁵³	=	9,007,199,254,740,992	2⁶⁹	=	590,295,810,358,705,651,712	2⁸⁵	=	38,685,626,227,668,133,590,597,632
2⁶	=	64	2²²	=	4,194,304	2³⁸	=	274,877,906,944	2⁵⁴	=	18,014,398,509,481,984	2⁷⁰	=	1,180,591,620,717,411,303,424	2⁸⁶	=	77,371,252,455,336,267,181,195,264
2⁷	=	128	2²³	=	8,388,608	2³⁹	=	549,755,813,888	2⁵⁵	=	36,028,797,018,963,968	2⁷¹	=	2,361,183,241,434,822,606,848	2⁸⁷	=	154,742,504,910,672,534,362,390,528
2⁸	=	256	2²⁴	=	16,777,216	2⁴⁰	=	1,099,511,627,776	2⁵⁶	=	72,057,594,037,927,936	2⁷²	=	4,722,366,482,869,645,213,696	2⁸⁸	=	309,485,009,821,345,068,724,781,056
2⁹	=	512	2²⁵	=	33,554,432	2⁴¹	=	2,199,023,255,552	2⁵⁷	=	144,115,188,075,855,872	2⁷³	=	9,444,732,965,739,290,427,392	2⁸⁹	=	618,970,019,642,690,137,449,562,112
2¹⁰	=	1024	2²⁶	=	67,108,864	2⁴²	=	4,398,046,511,104	2⁵⁸	=	288,230,376,151,711,744	2⁷⁴	=	18,889,465,931,478,580,854,784	2⁹⁰	=	1,237,940,039,285,380,274,899,124,224
2¹¹	=	2,048	2²⁷	=	134,217,728	2⁴³	=	8,796,093,022,208	2⁵⁹	=	576,460,752,303,423,488	2⁷⁵	=	37,778,931,862,957,161,709,568	2⁹¹	=	2,475,880,078,570,760,549,798,248,448
2¹²	=	4,096	2²⁸	=	268,435,456	2⁴⁴	=	17,592,186,044,416	2⁶⁰	=	1,152,921,504,606,846,976	2⁷⁶	=	75,557,863,725,914,323,419,136	2⁹²	=	4,951,760,157,141,521,099,596,496,896
2¹³	=	8,192	2²⁹	=	536,870,912	2⁴⁵	=	35,184,372,088,832	2⁶¹	=	2,305,843,009,213,693,952	2⁷⁷	=	151,115,727,451,828,646,838,272	2⁹³	=	9,903,520,314,283,042,199,192,993,792
2¹⁴	=	16,384	2³⁰	=	1,073,741,824	2⁴⁶	=	70,368,744,177,664	2⁶²	=	4,611,686,018,427,387,904	2⁷⁸	=	302,231,454,903,657,293,676,544	2⁹⁴	=	19,807,040,628,566,084,398,385,987,584
2¹⁵	=	32,768	2³¹	=	2,147,483,648	2⁴⁷	=	140,737,488,355,328	2⁶³	=	9,223,372,036,854,775,808	2⁷⁹	=	604,462,909,807,314,587,353,088	2⁹⁵	=	39,614,081,257,132,168,796,771,975,168

Može se videti da je početak od 2 poslednje cifre periodičan sa periodom 4, sa ciklusom 2–4–8–6–, a početak sa 4 poslednje cifre periodičan sa periodom 20. Ovi obrasci važe generalno za bilo koji stepen, u odnosu na bilo koju bazu. Obrazac se nastavlja, naravno, gde je polazna tačka svakog obrasca

2 k

, a period je multiplikativna grupa reda 2 modula

5 k

, što je

φ(5 k)

= 4 ×

5 k -1

(vidi Multiplikativna grupa celih brojeva modula n).

Stepen 1024[uredi | uredi izvor]

Prvih nekoliko stepena 2¹⁰ su malo viši od ovih od 1000:

2⁰	=	1	= 1000⁰	(0% odstupanja)
2¹⁰	=	1 024	≈ 1000¹	(2.4% odstupanja)
2²⁰	=	1 048 576	≈ 1000²	(4.9% odstupanja)
2³⁰	=	1 073 741 824	≈ 1000³	(7.4% odstupanja)
2⁴⁰	=	1 099 511 627 776	≈ 1000⁴	(10% odstupanja)
2⁵⁰	=	1 125 899 906 842 624	≈ 1000⁵	(12.6% odstupanja)
2⁶⁰	=	1 152 921 504 606 846 976	≈ 1000⁶	(15.3% odstupanja)
2⁷⁰	=	1 180 591 620 717 411 303 424	≈ 1000⁷	(18.1% odstupanja)
2⁸⁰	=	1 208 925 819 614 629 174 706 176	≈ 1000⁸	(20.9% odstupanja)
2⁹⁰	=	1 237 940 039 285 380 274 899 124 224	≈ 1000⁹	(23.8% odstupanja)
2¹⁰⁰	=	1 267 650 600 228 229 401 496 703 205 376	≈ 1000¹⁰	(26.8% odstupanja)
2¹¹⁰	=	1 298 074 214 633 706 907 132 624 082 305 024	≈ 1000¹¹	(29.8% odstupanja)
2¹²⁰	=	1 329 227 995 784 915 872 903 807 060 280 344 576	≈ 1000¹²	(32.9% odstupanja)

Vidi još IEEE 1541-2002.

Stepen dvojke čiji je eksponent stepen dvojke[uredi | uredi izvor]

Pošto su podaci (posebno celi brojevi) i adrese podataka skladišteni u istom hardveru, a podaci su skladišteni u jednom ili više okteta (

23

), dupli eksponenti dvojke su česti. Na primer,

2¹ = 2

2² = 4

2⁴ = 16

2⁸ = 256

2¹⁶ = 65536

2³² = 4,294,967,296

2⁶⁴ = 18,446,744,073,709,551,616 (20 cifara)

2¹²⁸ = 340,282,366,920,938,463,463,374,607,431,768,211,456 (39 cifara)

2²⁵⁶ =
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,
639,936 (78 cifara)

2⁵¹² =
13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,
030,073,546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,
649,006,084,096 (155 cifara)

2^1,024 = 179,769,313,486,231,590,772,931,...,304,835,356,329,624,224,137,216 (309 cifara)

2^2,048 = 323,170,060,713,110,073,007,148,...,193,555,853,611,059,596,230,656 (617 cifara)

2^4,096 = 104,438,888,141,315,250,669,175,...,243,804,708,340,403,154,190,336 (1,234 cifara)

2^8,192 = 109,074,813,561,941,592,946,298,...,997,186,505,665,475,715,792,896 (2,467 cifara)

2^16,384 = 118,973,149,535,723,176,508,576,...,460,447,027,290,669,964,066,816 (4,933 cifara)

2^32,768 = 141,546,103,104,495,478,900,155,...,541,122,668,104,633,712,377,856 (9,865 cifara)

2^65,536 = 200,352,993,040,684,646,497,907,...,339,445,587,895,905,719,156,736 (19,729 cifara)

Neki od ovih brojeva predstavljaju broj vrednosti predstavljenih korišćenjem zajedničkih računarskih vrsta podataka. Na primer, 32-bitna reč sadrži 4 bita i može biti predstavljena

232

različitim vrednostima koje mogu biti smatrani kao samo bit-obrazsci, ili se češće tumače kao neoznačeni brojevi od 0 do

232 - 1

, ili kao opseg označenih brojeva između

-2 31

i

231 - 1

. Vidi jošte tetration i niže hiperoperacije. Za više detalja o označenim brojevima pogledajte komplement dvojke.

U vezi sa nimberima ovi brojevi se često nazivaju Fermaovi 2-stepeni brojevi.

Brojevi $2^{2^{n}}$ formiraju iracionalni niz: za svaki niz pozitivnih celih brojeva, niz

\sum _{i=0}^{\infty }{\frac {1}{2^{2^{i}}x_{i}}}={\frac {1}{2x_{0}}}+{\frac {1}{4x_{1}}}+{\frac {1}{16x_{2}}}+\cdots

konvergira do iracionalnog broja. Uprkos brzom porastu ovog niza, on najsporije raste u iracionalnost od svih poznatih nizova.^[3]

Neki odabrani stepeni dvojke[uredi | uredi izvor]

2⁸ = 256: Broj vrednosti koje su predstavljene 8 bita u bajtu, preciznije se zove oktet. (Termin bajt se često definiše kao skup bitova češće nego striktna definicija 8-bitne količine, kao što je demontrirano terminom kilobajt.)
2¹⁰ = 1,024: Binarna aproksimacija kilo-, ili množilac 1,000, koji prouzrokuje promenu prefiksa. Na primer: 1,024 bajtova = 1 kilobajt (ili kibibajt).; Ovaj broj nema specijalna značaj za računare, ali je značajan za ljude zato što koristimo stepene desetke.
2¹² = 4,096: Veličina strane hardvera kod Intel x86 procesora.
2¹⁶ = 65,536: Broj različitih vrednosti koje se mogu predstaviti u jednoj reči 16-bitnog procesora, kao što je originalan x86 procesor.^[4]; Najveći opseg promenljive kratkog celog broja u C#, i Java programskom jeziku. Najveći opseg Reči ili Smalint promenljive u Paskal programskom jeziku.
2²⁰ = 1,048,576: Binarna aproksimacija mega-, ili množilac 1,000,000, koji uzrokuje promenu prefiksa. Na primer: 1,048,576 bajtova = 1 megabajt (ili mebibajt).; Ovaj broj nema specijalna značaj za računare, ali je značajan za ljude zato što koristimo stepene desetke.
2²⁴ = 16,777,216: Broj jedinstvenih boja može biti predstavljen kao stvarnim bojama, koje se koriste kod običnih računarskih monitora.; Ovaj broj je rezultat korišćenja trokanalnog RGB sistema, sa 8 bitova za svaki kanal, ili 24 bita ukupno.
2³⁰ = 1,073,741,824: Binarna aproksimacija giga-, ili množilac 1.000.000,000, koji uzrokuje promenu prefiksa. Na primer, 1,073,741,824 bajtova = 1 gigabajt (ili gibibajt).; Ovaj broj nema specijalna značaj za računare, ali je značajan za ljude zato što koristimo stepene desetke.
2³¹ = 2,147,483,648: Broj ne-negativnih vrednosti za označeni 32-bitni ceo broj. Otkako se Juniks vreme meri sekundama od 1. januara 1970, isteći će 2.147.483,647 sekundi ili 03:14:07 UTC u utorak 19. januara 2038. na 32-bitnim računarima koji koriste Juniks, problem poznat kao problem 2038. godine.
2³² = 4,294,967,296: Broj različitih reči koje se mogu predstaviti jednom rečju na 32-bitnom procesoru.^[5] Ili, broj vrednosti koje se mogu predstaviti duplom rečju na 16-bitnom procesoru, kao što je originalan x86 procesor.^[4]; Opseg celobrojne promenljive u Java i C# programskim jezicima.; Opseg Kardinalnih ili Celobrojnih promenljivih u Paskal programskom jeziku.; Najmanji opseg promenljive dugog celog broja u C i C++ programskim jezicima.; Ukupan broj IP adresa pod IPv4.; Iako je ovo naizgled veliki broj, iscrpljivanje IPv4 adresa je neizbežno.
2⁴⁰ = 1,099,511,627,776: Binarsna aproksimacija tera-, ili množilac1,000,000,000,000, koji prouzrokuje promenu prefiksa. Na primer, 1,099,511,627,776 bajtova = 1 terabajt (ili tebibajt).; Ovaj broj nema specijalna značaj za računare, ali je značajan za ljude zato što koristimo stepene desetke.
2⁵⁰ = 1,125,899,906,842,624: Binarna aproksimacija peta-, ili množilac 1.000.000,000,000,000. 1,125,899,906,842,624 bajtova = 1 petabajt (ili pebibajt).
2⁶⁰ = 1,152,921,504,606,846,976: Binarna aproksimacija eksa-, ili množilac 1,000,000,000,000,000,000. 1,152,921,504,606,846,976 bajtova = 1 eksabajt (ili eksbibajt).
2⁶⁴ = 18,446,744,073,709,551,616: Broj različitih vrednosti koje se mogu predstaviti jednomrečju na 64-bitnom procesoru. Ili, broj vrednosti koje se mogu predstaviti duplom rečju na 32-bitnom procesoru. Ili, broj vrednosti koje se mogu predstaviti kvadrečima na 16-bitnom procesoru, kao na originalnom x86 procesoru.^[4]; Raspon duge promenljive Java i C# programskih jezika..; Raspon Int64 ili KuReč promenljivih u Paskal programskom jeziku.; Ukupan broj IPv6 adresa generalno daje jedan LAN ili podmrežu.; Jedan više od brojeva zrna graška na šahovskoj tabli, u skladu sa starom pričom, gde prvi kvadrat sadrži jedno zrno pirinča i svaki naredni kvadrat duplo više od prethodnog kvadrata. Iz ovog razloga broj 2⁶⁴ – 1 je poznat kao "šahovski broj".
2⁷⁰ = 1,180,591,620,717,411,303,424: Binarna aproksimacija jota-, ili množilac 1.000.000,000,000,000,000,000, koja uzrokuje promenu prefiksa. Na primer, 1,180,591,620,717,411,303,424 bajtova = 1 jotabajt (ili jobibajt).
2⁸⁶ = 77,371,252,455,336,267,181,195,264: 2⁸⁶ pretpostavljeno je da najveći stepen dvojke ne sadrži nulu.^[6]
2⁹⁶ = 79,228,162,514,264,337,593,543,950,336: Ukupan broj IPv6 adresa generalno daje lokalni Internet registar. U CIDR notaciji, ISP su date kao /32, što znači da je 128-32=96 bitova slobodno za adrese. (za razliku od označavanja mreže). Dakle, 2⁹⁶ adrese.
2¹²⁸ = 340,282,366,920,938,463,463,374,607,431,768,211,456: Ukupan broj IP adresa dostupnim pod IPv6. Takođe, broj različitih univerzalno jedinstvenih identifikatora (UUID).
2³³³ = 17,498,005,798,264,095,394,980,017,816,940,970,922,825,355,447,145,699,491,406,164,851,279,623, 993,595,007,385,788,105,416,184,430,592: Najmanji stepen 2 veći od gugola (10¹⁰⁰).
2¹⁰²⁴ = 179,769,313,486,231,590,772,931,...,304,835,356,329,624,224,137,216: Maksimalan broj koji može da stane u IEEE dvostruku preciznost formata pokretnog zareza, a samim tim i broj koji se može predstaviti mnogim programima, kao na primer Majkrosoft Eksel.
2^57,885,161 = 581,887,266,232,246,442,175,100,...,725,746,141,988,071,724,285,952: Jedan više od najvećeg poznatog prostog broja ažurirano: 2013.^{[ažuriranje]}. On ima više od 17 miliona cifara.^[7]

Brzi algoritam za proveru da li je pozitivan broj stepen dvojke[uredi | uredi izvor]

Binarno predstavljanje celih brojeva omogućava brzu proveru radi utvrđivanja da li je neki dati pozitivan ceo broj x stepen dvojke:

pozitivan broj x je stepen dvojke ⇔

(x & (x - 1))

je ekvivalentno nuli.

gde je & bitovska logička END operacija. Primetimo da ako je x 0, ovo pogrešno ukazuje na to da je 0 stepen dvojke, tako da ova provera važi samo za $x > 0$ .

Primeri:

−1	=	1…111…1	−1	=	1…111…111…1
x	=	0…010…0	y	=	0…010…010…0
x − 1	=	0…001…1	y−1	=	0…010…001…1
x & (x − 1)	=	0…000…0	y & (y − 1)	=	0…010…000…0

Dokaz koncepta:

Dokaz koristi tehniku kontradiktorne izjave.

Izjava S: Ako je x&(x-1) = 0 i x je ceo broj veći od nule onda je x = 2^k (gde je k ceo broj takav da je k>=0).

Kontradiktoran koncept:

S1: P -> Q je isto kao i S2: ~Q -> ~P U pređašnjim izjavama S1 i S2 ove su kontradiktorne u odnosu jedna na drugu. Tako da se izjava S može prepravljati kao ispod S': Ako je x pozitivan ceo broj i x ≠ 2^k (k ije neki ne-negativni ceo broj) onda je x&(x-1) ≠ 0

Dokaz:

Ako je x ≠ 2^k onda najmanje dva bita x-a su setovi. (Pretostavimo da su m bitovi set.) Sada, bit obrazac x - 1 se može dobiti invertovanjem svih bitova x-a do prvog seta bita h-a (počevši od NZB i nastavljajući ka NZB, ovaj set inkluzivnog bita). Sada, pretpostavimo da izraz x & (x-1) ima sve nule bitova do prvog seta h-a i kako x & (x-1) ima isto preostalih bitova kao x i x ima najmanje dva seta bitova otuda je iskaz x & (x-1) ≠ 0 tačan.

Brzi logaritam za nalaženje modula broja stepena dvojke[uredi | uredi izvor]

Kao gore navedeno uopptavanje, binarna predstava celih brojeva omogućava izračunavanje modula ne-negativnog celog broj (x) sa stepenom dvojke (y) veoma brzo:

x mod y = (x & (y - 1))

.

gde je & bitovska logička END operacija. Ovo zaobilazi potrebu da se izvrši skupocena podela. Ovo je korisno ako je moduo operacije značajna deo izvršavanja kritične putanje, jer to može biti mnogo brže od običnog moduo operatora.

Algoritam za pronalaženje stepena dvojke najbližeg broju[uredi | uredi izvor]

Sledeća formula nalazi najbliži stepen dvoke, na logaritamskog skali, za datu vrenost $x > 0$ :

2^{\mathrm {round} [\log _{2}(x)]}

Ovo bi trebalo da se razlikuje od najbližeg stepena dvojke na linearnoj skali. Na primer, 23 je bliže broju 16 od broja 32, ali prethodna formula zaokružuje na 32, odgovarajući na činjenicu da je 23/16 = 1.4375, veće od 32/23 = 1.3913.

Ako je x celobrojna vrednost, sledeći koraci se mogu koristiti da pronalaženje najbliže vrednosti (u odnosu na stvarne vrednosti pre nego na binarni logaritam) u računarskom programu:

Pronaći najznačajniju bitnu poziciju k, koja je postavljena (1) iz binarne prezentacije x- $a$ , kada ${{{1}}}$ označava najmanje značajan bit.
Onda, ako je bit $k - 1$ nula, rezultat je $2 k$ . U suprotnom rezultat je $2 k + 1$ .

Algoritam za pronalaženje stepena dvojke većeg ili jednakog broju[uredi | uredi izvor]

Ponekad je potrebno naći poslednji stepen dvojke koji nije manji od konkretnog celog broja, n. Pseudokod algoritma za izračunavanje sledećeg većeg stepena dvojke je sledeći. Ako je unos stepen dvojke, vratiće se nepromenjen.^[8]

n = n - 1;
n = n | (n >> 1);
n = n | (n >> 2);
n = n | (n >> 4);
n = n | (n >> 8);
n = n | (n >> 16);
...
n = n | (n >> (bitspace / 2));
n = n + 1;

Gde je | binarni ili operator, >> je binarni operator za pomeranje udesno, a bit razmak je veličine (u bitovima) celobrojnog razmaka predstavnjenim n-om. Za mnogo računarskih arhitektura, ova vrednost je takođe ili 8, 16, 32 ili 64. Ovaj operator radi postavljanjem svih bitova na desnu stranu najznačajnijeg obeženog bita do 1, a zatim se povećava celokupna vrednost na kraju tako da dolazi do ''prevrtanja” do najbližeg stepena dvojke. Primer svakog koraka ovog algoritma za broj 2689 je sledeći:

Binarni zapis	Decimalni zapis
`0101010000001`	2,689
`0101010000000`	2,688
`0111111000000`	4,032
`0111111110000`	4,080
`0111111111111`	4,095
`1000000000000`	4,096

Kao što je gore prikazano, algoritam vraća tačnu vrednost 4,096. Najbliži stepen 2,689 je 2,048; međutim, algoritam je kreiran da daje samo sledeći najveći stepen dvoje datog broja, ne najbliži.

Drugi način za dobijanje 'sledećeg najvećeg' stepen dvojke datog broja nezavisnog od dužine bit razmaka je sledeći.

unsigned int get_nextpowerof2(unsigned int n)
{
 /*
  * Below indicates passed no is a power of 2, so return the same.
  */
 if (!(n & (n-1))) {
     return (n);
 }

 while (n & (n-1)) {
    n = n & (n-1);
 }

 n = n << 1;
 return n;
}

Brzi algoritam za zaokruživanje bilo kog celog broja do višestrukog datog stepena dvojke[uredi | uredi izvor]

Za bilo koji ceo broj, x i integral stepena dvojke, y, ako je z = y - 1,

x I (NE z) zaokružuje dole,
(x + z) I (NE z) zaokružuje gore, i
(x + y / 2) I (NE z) zaokružuje najbližu (pozitivne vrednosti su tačno na polovini zaokruženih vrednosti gore, dok su negativne vrednosti tačno na polovini zaokruženih vrednosti dole)

x do višestrukog y.

Druge osobine[uredi | uredi izvor]

Zbir svih n-odabranih binomnih koeficijenata je jednak $2 n$ . Razmotrimo skup svih binarnih celobrojnih n-cifara. Njegova kardinalnost je

2 n

. To je takođe zbir kardinalnosti određenih podskupova: podkup celih brojeva bez jedinica (koji se sastoje od samo jedno broja, napisanog kao n 0-e), podskup sa sa samo jednom 1, poskup sa dve 1-ice, i tako dalje do podskupa sa n 1-ica (koji se sastoji od broja napisanog kao n 1-jedinica). Svaki od ovih je jedna binomnom koeficijentu indeksiranom sa n i broj od 1-ica je razmotren (tj., postoji 10-izbor-3 binarnih brojeva sa deset cifara koji uključuju tačno tri 1-ice).

Broj temena jednog n-dimenzionalnog hiperkuba je $2 n$ . Slično tome, broj $(n - 1)$ -lica n-dimenzionalnog unakrsnog politopa je takođe $2 n$ i formula za broj x-lica n-dimenzionalnog unakrsnog politopa je $\scriptstyle 2^{x}{n \choose x}$ .

Zbir reciprpčnih brojeva stepena dvojke je 2. Zbir recipročnih brojeva stepena dvojke na kvadrat je 1/3.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

^ Lipschutz 1982
^ Sewell, Michael J. (1997). Nedostaje ili je prazan parametar |title= (pomoć)
^ Guy 2004, str. 346.
^ ^a ^b ^v Though they vary in word size, all x86 processors use the term "word" to mean 16 bits; thus, a 32-bit x86 processor refers to its native wordsize as a dword
^ „Powers of 2 by Vaughn Aubuchon”. Arhivirano iz originala 12. 08. 2015. g. Pristupljeno 18. 01. 2016.
^ Weisstein, Eric W. "Zero."
^ „Largest prime number yet discovered – Light Years - CNN.com Blogs[[Kategorija:Botovski naslovi]]”. Arhivirano iz originala 03. 06. 2015. g. Pristupljeno 18. 01. 2016. Sukob URL—vikiveza (pomoć)
^ Warren Jr., Henry S. (2002). Nedostaje ili je prazan parametar |title= (pomoć)

Literatura[uredi | uredi izvor]

Guy, Richard (2004). Unsolved Problems in Number Theory. Springer Science & Business Media. str. 346. ISBN 978-0-387-20860-2.

Spoljašnje veze[uredi | uredi izvor]

"Sloane's A000079 : <meta />2ⁿ", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. (Powers of two)
- "Sloane's A001146 : <meta />2^(2ⁿ)", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. (Powers of two whose exponents are powers of two)

[1] Lipschutz 1982

[2] Sewell, Michael J. (1997). Nedostaje ili je prazan parametar |title= (pomoć)

[FOOTNOTEGuy2004346-3] Guy 2004, str. 346.

[iword-4] v Though they vary in word size, all x86 processors use the term "word" to mean 16 bits; thus, a 32-bit x86 processor refers to its native wordsize as a dword

[5] „Powers of 2 by Vaughn Aubuchon”. Arhivirano iz originala 12. 08. 2015. g. Pristupljeno 18. 01. 2016.

[6] Weisstein, Eric W. "Zero."

[7] „Largest prime number yet discovered – Light Years - CNN.com Blogs[[Kategorija:Botovski naslovi]]”. Arhivirano iz originala 03. 06. 2015. g. Pristupljeno 18. 01. 2016. Sukob URL—vikiveza (pomoć)

[8] Warren Jr., Henry S. (2002). Nedostaje ili je prazan parametar |title= (pomoć)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]