Степен двојке

У математици, степен двојке означава број форме 2ⁿ где је n цео број, тј. резултат степеновања бројем два као базом и целим бројем n као експонентом.

За друге потребе, види Степен двојке (вишезначна одредница).

У контексту у ком се разматрају само цели бројеви, n је ограничен на не-негативне вредности,^[1] тако да имамо 1, 2, и 2 помножене самим собом одређени број пута.^[2]

Због тога што је два основа у систему бинарних бројева, степен двојке је чест у рачунарској науци. Записан у бинарном облику, степен двојке увек има форму 100…000 или 0.00…001, баш као и степен десетке у децималном систему.

Изрази и једначине уреди

Вербални изрази, математичке ознаке, и изрази рачунарског програмирања користе степен двојке или функцију укључујући:

2 на n

2 на степен n

2 степен n

степен(2, n)

ст(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

Рачунарска наука уреди

Два на степен n, написано као $2 n$ , је број начина на који се битови у бинарном систему дужине n могу организовати. Реч, тумачена као неозначен цео број, може бити представљена вредностима од 0 (000…000) до $2 n - 1$ (111…111) закључно. Одговарајућа целобројна вредност може бити позитивна, негативна или нула; види представе означених бројева. У сваком случају, један мање од степена двојке је често горња граница целих бројева код бинарних рачунара. Као последица, бројеви ове форме се често појављују у рачунарском софтверу. На пример, видео игрица покренута на 8-битном систему може ограничити резултат или број предмета које играч може ностити на 255— резултат коришћења бајта, који је дугачак 8 бита, да сачува број, дајући максималну вредност $28 - 1 = 255$ . На пример, у делу Легенда о Зелди, главни лик је ограничен да чува 255 рупија (валута у игрици) у било ком тренутку, док се видео игра Пек-Мен чувено гаси на нивоу 255.

Степен двојке се користи за мерење рачунарске меморије. Бајт сада садржи осам бита (октет, као резултат могућности 256 вредности (2⁸). (Израз бајт је некад значио (и у неким случајевима још увек значи) скуп битова, уобичајено 5 до 32 бита, пре него само 8-битних јединица.) Префикс кило, у вези са бајтом, може бити, и одувек је био, коришћен као 1,024 (2¹⁰). Међутим, уопште, израз кило је био коришћен у Међунардном систему јединица у значењу 1,000 (10³). Бинарни префикси су били стандардизовани, као што киби (Ki) значи 1,024. Скоро сви процесорски регистри имају величину степена двојке, 32 или 64 су најчешћи.

Степен двојке се појављује на другим местима такође. За многе дискове, барем једна величина сектора, број сектора по стази, и број стаза по површини диска је степен двојке. Величина логичког блока је скоро увек степен двојке.

Бројеви који нису степен двојке се појављују у многим ситуацијама, као што су видео резолуције, али су они често збир или производ само два или три степена двојке, или степен двојке минус један. На пример,

640 = 512 + 128 = 128 \times 5

, и

480 = 32 \times 15

. На други начин, они имају прилично уобичајене шаблоне битова.

Мерсенови прости бројеви уреди

Слично, прост број (као 257) који је за један већи од позитивног степена двојке се назива Фермаов прост број — сам експонент је степен двојке. Разломак који има степен двојке као делилац се назива двојни разломак. Бројеви који могу бити представљени као збирови узастопних позитивних целих бројева се називају углађени бројеви; они су заправо бројеви који нису степен двојке.

Прост број који је за један мањи од степена двојке се зове Мерсенов прост број. На пример, прост број 31 је Мерсенов прост број зато што је за 1 мањи од 32 (2⁵).

Еуклидови елементи, 9. књига уреди

Геометријска прогресија 1, 2, 4, 8, 16, 32, … (или, у бинарном бројевном систему 1, 10, 100, 1000, 10000, 100000, … ) је важна у теорији бројева. 9. књига, 36. предлог Елемената доказује да ако је сума првих n чланова ове прогресије прост број (значи, Мерсенов прост број поменут изнад), онда ова сума помножена n-тим чланом је савршен број. На пример, сума првих 5 чланова низа 1 + 2 + 4 + 8 + 16 = 31, који је прост број. Сума 31 помножена са 16 (5. члан низа) је једнака 496, који је савршен број.

9. књига, 35 Предлог, доказује да ако је у геометријском низу први члан одузет од другог и последњег члана низа, онда је вишак другог први—тако да је вишак последњег све оно пре њега. (Ово је преправка наше формуле за геометријски низ изнад.) Примењујући ово на геометријску прогресију 31, 62, 124, 248, 496 (која резултује од 1, 2, 4, 8, 16 множењем свих чланова до 31), видимо да 62 минус 31 је 31 као и 496 минус 31 је збир 31, 62, 124, 248. Стога, бројеви 1, 2, 4, 8, 16, 31, 62, 124 и 248 додати до 496 и даље су сви ови бројеви деле број 496. Под претпоставком да p дели број 496 и није међу овим бројевима. Претпоставимо да су $p q$ једнаки $16 \times 31$ , или да је 31 q, а p 16. Сада p не може да дели 16 или би било међу бројевима 1, 2, 4, 8 или 16. Стога, 31 не може да дели q. И како 31 не дели q и q је 496, основна теорема аритметике имплицира да q мора да дели 16 и да буде међу бројевима 1, 2, 4, 8 или 16. Нека q буде 4, онда p мора бити 124, што је немогуће с обзиром на то да хипотеза p није међу бројевима 1, 2, 4, 8, 16, 31, 62, 124 или 248.

Првих 96 степена двојке уреди

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

Може се видети да је почетак од 2 последње цифре периодичан са периодом 4, са циклусом 2–4–8–6–, а почетак са 4 последње цифре периодичан са периодом 20. Ови обрасци важе генерално за било који степен, у односу на било коју базу. Образац се наставља, наравно, где је полазна тачка сваког обрасца

2 k

, а период је мултипликативна група реда 2 модула

5 k

, што је

φ(5 k)

= 4 ×

5 k -1

(види Мултипликативна група целих бројева модула n).

Степен 1024 уреди

Првих неколико степена 2¹⁰ су мало виши од ових од 1000:

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

Види још ИEEE 1541-2002.

Степен двојке чији је експонент степен двојке уреди

Пошто су подаци (посебно цели бројеви) и адресе података складиштени у истом хардверу, а подаци су складиштени у једном или више октета (

23

), дупли експоненти двојке су чести. На пример,

2¹ = 2

2² = 4

2⁴ = 16

2⁸ = 256

2¹⁶ = 65536

2³² = 4,294,967,296

2⁶⁴ = 18,446,744,073,709,551,616 (20 цифара)

2¹²⁸ = 340,282,366,920,938,463,463,374,607,431,768,211,456 (39 цифара)

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 цифара)

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 цифара)

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

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

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

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

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

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

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

Неки од ових бројева представљају број вредности представљених коришћењем заједничких рачунарских врста података. На пример, 32-битна реч садржи 4 бита и може бити представљена

232

различитим вредностима које могу бити сматрани као само бит-образсци, или се чешће тумаче као неозначени бројеви од 0 до

232 - 1

, или као опсег означених бројева између

-2 31

и

231 - 1

. Види јоште тетратион и ниже хипероперације. За више детаља о означеним бројевима погледајте комплемент двојке.

У вези са нимберима ови бројеви се често називају Фермаови 2-степени бројеви.

Бројеви $2^{2^{n}}$ формирају ирационални низ: за сваки низ позитивних целих бројева, низ

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

конвергира до ирационалног броја. Упркос брзом порасту овог низа, он најспорије расте у ирационалност од свих познатих низова.^[3]

Неки одабрани степени двојке уреди

2⁸ = 256: Број вредности које су представљене 8 бита у бајту, прецизније се зове октет. (Термин бајт се често дефинише као скуп битова чешће него стриктна дефиниција 8-битне количине, као што је демонтрирано термином килобајт.)
2¹⁰ = 1,024: Бинарна апроксимација кило-, или множилац 1,000, који проузрокује промену префикса. На пример: 1,024 бајтова = 1 килобајт (или кибибајт).; Овај број нема специјална значај за рачунаре, али је значајан за људе зато што користимо степене десетке.
2¹² = 4,096: Величина стране хардвера код Интел x86 процесора.
2¹⁶ = 65,536: Број различитих вредности које се могу представити у једној речи 16-битног процесора, као што је оригиналан x86 процесор.^[4]; Највећи опсег променљиве кратког целог броја у C#, и Јава програмском језику. Највећи опсег Речи или Смалинт променљиве у Паскал програмском језику.
2²⁰ = 1,048,576: Бинарна апроксимација мега-, или множилац 1,000,000, који узрокује промену префикса. На пример: 1,048,576 бајтова = 1 мегабајт (или мебибајт).; Овај број нема специјална значај за рачунаре, али је значајан за људе зато што користимо степене десетке.
2²⁴ = 16,777,216: Број јединствених боја може бити представљен као стварним бојама, које се користе код обичних рачунарских монитора.; Овај број је резултат коришћења троканалног РГБ система, са 8 битова за сваки канал, или 24 бита укупно.
2³⁰ = 1,073,741,824: Бинарна апроксимација гига-, или множилац 1.000.000,000, који узрокује промену префикса. На пример, 1,073,741,824 бајтова = 1 гигабајт (или гибибајт).; Овај број нема специјална значај за рачунаре, али је значајан за људе зато што користимо степене десетке.
2³¹ = 2,147,483,648: Број не-негативних вредности за означени 32-битни цео број. Откако се Јуникс време мери секундама од 1. јануара 1970, истећи ће 2.147.483,647 секунди или 03:14:07 УТЦ у уторак 19. јануара 2038. на 32-битним рачунарима који користе Јуникс, проблем познат као проблем 2038. године.
2³² = 4,294,967,296: Број различитих речи које се могу представити једном речју на 32-битном процесору.^[5] Или, број вредности које се могу представити дуплом речју на 16-битном процесору, као што је оригиналан x86 процесор.^[4]; Опсег целобројне променљиве у Јава и C# програмским језицима.; Опсег Кардиналних или Целобројних променљивих у Паскал програмском језику.; Најмањи опсег променљиве дугог целог броја у C и C++ програмским језицима.; Укупан број ИП адреса под ИПв4.; Иако је ово наизглед велики број, исцрпљивање ИПв4 адреса је неизбежно.
2⁴⁰ = 1,099,511,627,776: Бинарсна апроксимација тера-, или множилац1,000,000,000,000, који проузрокује промену префикса. На пример, 1,099,511,627,776 бајтова = 1 терабајт (или тебибајт).; Овај број нема специјална значај за рачунаре, али је значајан за људе зато што користимо степене десетке.
2⁵⁰ = 1,125,899,906,842,624: Бинарна апроксимација пета-, или множилац 1.000.000,000,000,000. 1,125,899,906,842,624 бајтова = 1 петабајт (или пебибајт).
2⁶⁰ = 1,152,921,504,606,846,976: Бинарна апроксимација екса-, или множилац 1,000,000,000,000,000,000. 1,152,921,504,606,846,976 бајтова = 1 ексабајт (или ексбибајт).
2⁶⁴ = 18,446,744,073,709,551,616: Број различитих вредности које се могу представити једномречју на 64-битном процесору. Или, број вредности које се могу представити дуплом речју на 32-битном процесору. Или, број вредности које се могу представити квадречима на 16-битном процесору, као на оригиналном x86 процесору.^[4]; Распон дуге променљиве Јава и C# програмских језика..; Распон Инт64 или КуРеч променљивих у Паскал програмском језику.; Укупан број ИПв6 адреса генерално даје један ЛАН или подмрежу.; Један више од бројева зрна грашка на шаховској табли, у складу са старом причом, где први квадрат садржи једно зрно пиринча и сваки наредни квадрат дупло више од претходног квадрата. Из овог разлога број 2⁶⁴ – 1 је познат као "шаховски број".
2⁷⁰ = 1,180,591,620,717,411,303,424: Бинарна апроксимација јота-, или множилац 1.000.000,000,000,000,000,000, која узрокује промену префикса. На пример, 1,180,591,620,717,411,303,424 бајтова = 1 јотабајт (или јобибајт).
2⁸⁶ = 77,371,252,455,336,267,181,195,264: 2⁸⁶ претпостављено је да највећи степен двојке не садржи нулу.^[6]
2⁹⁶ = 79,228,162,514,264,337,593,543,950,336: Укупан број ИПв6 адреса генерално даје локални Интернет регистар. У ЦИДР нотацији, ИСП су дате као /32, што значи да је 128-32=96 битова слободно за адресе. (за разлику од означавања мреже). Дакле, 2⁹⁶ адресе.
2¹²⁸ = 340,282,366,920,938,463,463,374,607,431,768,211,456: Укупан број ИП адреса доступним под ИПв6. Такође, број различитих универзално јединствених идентификатора (УУИД).
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: Најмањи степен 2 већи од гугола (10¹⁰⁰).
2¹⁰²⁴ = 179,769,313,486,231,590,772,931,...,304,835,356,329,624,224,137,216: Максималан број који може да стане у ИЕЕЕ двоструку прецизност формата покретног зареза, а самим тим и број који се може представити многим програмима, као на пример Мајкрософт Ексел.
2^57,885,161 = 581,887,266,232,246,442,175,100,...,725,746,141,988,071,724,285,952: Један више од највећег познатог простог броја ажурирано: 2013.^{[ажурирање]}. Он има више од 17 милиона цифара.^[7]

Брзи алгоритам за проверу да ли је позитиван број степен двојке уреди

Бинарно представљање целих бројева омогућава брзу проверу ради утврђивања да ли је неки дати позитиван цео број x степен двојке:

позитиван број x је степен двојке ⇔

(x & (x - 1))

је еквивалентно нули.

где је & битовска логичка ЕНД операција. Приметимо да ако је x 0, ово погрешно указује на то да је 0 степен двојке, тако да ова провера важи само за $x > 0$ .

Примери:

−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

Доказ концепта:

Доказ користи технику контрадикторне изјаве.

Изјава С: Ако је x&(x-1) = 0 и x је цео број већи од нуле онда је x = 2^k (где је k цео број такав да је k>=0).

Контрадикторан концепт:

С1: P -> Q је исто као и С2: ~Q -> ~P У пређашњим изјавама С1 и С2 ове су контрадикторне у односу једна на другу. Тако да се изјава С може преправљати као испод С': Ако је x позитиван цео број и x ≠ 2^k (k iје неки не-негативни цео број) онда је x&(x-1) ≠ 0

Доказ:

Ако је x ≠ 2^k онда најмање два бита x-а су сетови. (Претоставимо да су m битови сет.) Сада, бит образац x - 1 се може добити инвертовањем свих битова x-а до првог сета бита х-а (почевши од НЗБ и настављајући ка НЗБ, овај сет инклузивног бита). Сада, претпоставимо да израз x & (x-1) има све нуле битова до првог сета х-а и како x & (x-1) има исто преосталих битова као x и x има најмање два сета битова отуда је исказ x & (x-1) ≠ 0 тачан.

Брзи логаритам за налажење модула броја степена двојке уреди

Као горе наведено уопптавање, бинарна представа целих бројева омогућава израчунавање модула не-негативног целог број (x) са степеном двојке (y) веома брзо:

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

.

где је & битовска логичка ЕНД операција. Ово заобилази потребу да се изврши скупоцена подела. Ово је корисно ако је модуо операције значајна део извршавања критичне путање, јер то може бити много брже од обичног модуо оператора.

Алгоритам за проналажење степена двојке најближег броју уреди

Следећа формула налази најближи степен двоке, на логаритамског скали, за дату вреност $x > 0$ :

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

Ово би требало да се разликује од најближег степена двојке на линеарној скали. На пример, 23 је ближе броју 16 од броја 32, али претходна формула заокружује на 32, одговарајући на чињеницу да је 23/16 = 1.4375, веће од 32/23 = 1.3913.

Ако је x целобројна вредност, следећи кораци се могу користити да проналажење најближе вредности (у односу на стварне вредности пре него на бинарни логаритам) у рачунарском програму:

Пронаћи најзначајнију битну позицију k, која је постављена (1) из бинарне презентације x- $а$ , када ${{{1}}}$ означава најмање значајан бит.
Онда, ако је бит $k - 1$ нула, резултат је $2 k$ . У супротном резултат је $2 k + 1$ .

Алгоритам за проналажење степена двојке већег или једнаког броју уреди

Понекад је потребно наћи последњи степен двојке који није мањи од конкретног целог броја, n. Псеудокод алгоритма за израчунавање следећег већег степена двојке је следећи. Ако је унос степен двојке, вратиће се непромењен.^[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;

Где је | бинарни или оператор, >> је бинарни оператор за померање удесно, а бит размак је величине (у битовима) целобројног размака представњеним n-ом. За много рачунарских архитектура, ова вредност је такође или 8, 16, 32 или 64. Овај оператор ради постављањем свих битова на десну страну најзначајнијег обеженог бита до 1, а затим се повећава целокупна вредност на крају тако да долази до ''превртања” до најближег степена двојке. Пример сваког корака овог алгоритма за број 2689 је следећи:

Бинарни запис	Децимални запис
`0101010000001`	2,689
`0101010000000`	2,688
`0111111000000`	4,032
`0111111110000`	4,080
`0111111111111`	4,095
`1000000000000`	4,096

Као што је горе приказано, алгоритам враћа тачну вредност 4,096. Најближи степен 2,689 је 2,048; међутим, алгоритам је креиран да даје само следећи највећи степен двоје датог броја, не најближи.

Други начин за добијање 'следећег највећег' степен двојке датог броја независног од дужине бит размака је следећи.

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;
}

Брзи алгоритам за заокруживање било ког целог броја до вишеструког датог степена двојке уреди

За било који цео број, x и интеграл степена двојке, y, ако је z = y - 1,

x И (НЕ z) заокружује доле,
(x + z) И (НЕ z) заокружује горе, и
(x + y / 2) И (НЕ z) заокружује најближу (позитивне вредности су тачно на половини заокружених вредности горе, док су негативне вредности тачно на половини заокружених вредности доле)

x до вишеструког y.

Друге особине уреди

Збир свих n-одабраних биномних коефицијената је једнак $2 n$ . Размотримо скуп свих бинарних целобројних n-цифара. Његова кардиналност је

2 n

. То је такође збир кардиналности одређених подскупова: подкуп целих бројева без јединица (који се састоје од само једно броја, написаног као n 0-е), подскуп са са само једном 1, поскуп са две 1-ице, и тако даље до подскупа са n 1-ица (који се састоји од броја написаног као n 1-јединица). Сваки од ових је једна биномном коефицијенту индексираном са n и број од 1-ица је размотрен (тј., постоји 10-избор-3 бинарних бројева са десет цифара који укључују тачно три 1-ице).

Број темена једног n-димензионалног хиперкуба је $2 n$ . Слично томе, број $(n - 1)$ -лица n-димензионалног унакрсног политопа је такође $2 n$ и формула за број x-лица n-димензионалног унакрсног политопа је $\scriptstyle 2^{x}{n \choose x}$ .

Збир реципрпчних бројева степена двојке је 2. Збир реципрочних бројева степена двојке на квадрат је 1/3.

Види још уреди

Референце уреди

^ Lipschutz 1982
^ Sewell, Michael J. (1997). Недостаје или је празан параметар |title= (помоћ)
^ Guy 2004, стр. 346.
^ ^а ^б ^в 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”. Архивирано из оригинала 12. 08. 2015. г. Приступљено 18. 01. 2016.
^ Weisstein, Eric W. "Zero."
^ „Largest prime number yet discovered – Light Years - CNN.com Blogs[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 03. 06. 2015. г. Приступљено 18. 01. 2016. Сукоб URL—викивеза (помоћ)
^ Warren Jr., Henry S. (2002). Недостаје или је празан параметар |title= (помоћ)

Литература уреди

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

Спољашње везе уреди

"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). Недостаје или је празан параметар |title= (помоћ)

[FOOTNOTEGuy2004346-3] Guy 2004, стр. 346.

[iword-4] а ^б ^в 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”. Архивирано из оригинала 12. 08. 2015. г. Приступљено 18. 01. 2016.

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

[7] „Largest prime number yet discovered – Light Years - CNN.com Blogs[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 03. 06. 2015. г. Приступљено 18. 01. 2016. Сукоб URL—викивеза (помоћ)

[8] Warren Jr., Henry S. (2002). Недостаје или је празан параметар |title= (помоћ)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]