У математиці степінь двійки означає число виду 2n, де n є ціле число, тобто внаслідок піднесення до степеня з числом два як основою і цілим числом n як показником.
Якщо розглядати як результат піднесення до степеня лише цілі числа, то n обмежується невід'ємними значеннями, тому ми маємо 1, 2 і 2 помножені самі на себе певну кількість разів.
Через те, що два є основою двійкової системи числення, степені двійки є поширеними в інформатиці. Таке число записане в двійковій системі, є степенем двох, яка має вигляд 100…000 або 0.00… 001, так само, як і степені десяти в десятковій системі.
Вирази та позначення
Вербальні вирази, математичні позначення та вирази комп'ютерного програмування з використанням оператора степені або функції включають в себе:
- 2 в n
- 2 в степені n
- 2 степінь n
- power(2, n): pow(2, n)
- 2n
- 1 << n
- 2 ^ n
- 2 ** n
- 2 [3] n
- 2 ↑ n
- A(n — 3, 3) + 3
Інформатика
Два в степені n, записується у вигляді 2n, є кількістю способів як можуть бути організовані біти в двійковому слові довжини n. Як беззнакові цілі ці способи представляють числа від 0 (000…000) 2n − 1 (111…111) включно. Відповідні цілі числа є додатні, від'ємні числа та нуль; див. (прямий код). У будь-якому разі, на один менше, ніж степінь двійки, часто є верхньою межею цілого числа в двійковому лічильнику. Як наслідок, номери цієї форми часто з'являються в програмному забезпеченні комп'ютера. Як приклад, відеогра, що працює на 8-бітній системі може обмежити рахунок або кількість елементів, гравець може зберігати до 255 — в результаті використання байта, довжиною 8 біт, щоб зберегти номер, даючи максимальне значення 28 − 1 = 255. Наприклад, в грі Legend of Zelda головний герой був обмежений носінням 255 рупій (валюта гри) в будь-який момент часу, і відеогра Pac-Man хвацько вимикається якщо кількість рупій рівна 255.
Степені двійки часто використовується для вимірювання пам'яті комп'ютера. Байт в даний час містить вісім біт (октет, в результаті чого можливо 256 значень (28). (Термін байт використовувався, а в деяких випадках і продовжує бути колекцією бітів, зазвичай від 5 до 32 біт, а не тільки 8-бітовим блоком.) Префікс кіло, в поєднанні з байт, може бути, і традиційно, використовується, щоб позначати 1,024 (210). Однак, загалом, термін кіло використовувався в Міжнародній системі одиниць для позначення 1,000 (103). Бінарні префікси були стандартизовані, наприклад, кібі (Кі), що означає 1,024. Майже всі регістри процесора мають розміри, які є степенем двійки, наприклад, 32 або 64 є найбільш поширеними.
Степені двійки з'являються в інших місцях. Для багатьох дисків, принаймні один з розмірів сектора, кількість секторів на доріжці і кількість треків на поверхні є степінню двійки. Розмір логічного блоку майже завжди є степінню двійки.
Числа, які не є степенями двійки зустрічаються в ряді ситуацій, таких як роздільна здатність дисплея, але вони часто є сумою або добутком тільки двійки в другому, або третьому, або двійки в мінус першій степені. Наприклад, 640 = 512 + 128 = 128 × 5 і 480 = 32 × 15. Іншими словами, вони мають досить регулярні бітові комбінації.
Прості числа Мерсенна
Просте число, що на одиницю менше, ніж степінь двійки, називається числом Мерсенна. Наприклад, просте число 31 буде числом Мерсенна, оскільки воно на одиницю менше, ніж 32 (25). Аналогічно, просте число (наприклад, 257), що на одиницю більше, ніж натуральний степінь двійки, називається числом Ферма; показник сам буде степенем двійки. Дріб, що має степінь двійки знаменником, називається двійково-раціональним. Числа, які можна подати у вигляді суми послідовних натуральних чисел, називаються [en]; вони точно не є степенями двійки.
Елементи Евкліда, Книга IX
Геометрична прогресія 1, 2, 4, 8, 16, 32, … (або, в двійковій системі числення, 1, 10, 100, 1000, 10000, 100000, …) відіграє важливу роль в теорії чисел. Книга IX, Теорема 36 Елементів доводить, що якщо сума перших n членів цієї прогресії є простим числом (про числа Мерсенна йшлося вище), то якраз ця сума помножена на n-й член — досконале число. Наприклад, сума перших 5 членів ряду 1 + 2 + 4 + 8 + 16 = 31, є простим числом. Сума 31 множиться на 16 (п'ятий член ряду) дорівнює 496, що є досконалим числом.
Книга IX, Теорема 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 × 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 степенів двійки
послідовність A000079 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
20 | = | 1 | 216 | = | [en] | 232 | = | 4,294,967,296 | 248 | = | 281,474,976,710,656 | 264 | = | 18,446,744,073,709,551,616 | 280 | = | 1,208,925,819,614,629,174,706,176 | |||||
21 | = | 2 | 217 | = | 131,072 | 233 | = | 8,589,934,592 | 249 | = | 562,949,953,421,312 | 265 | = | 36,893,488,147,419,103,232 | 281 | = | 2,417,851,639,229,258,349,412,352 | |||||
22 | = | 4 | 218 | = | 262,144 | 234 | = | 17,179,869,184 | 250 | = | 1,125,899,906,842,624 | 266 | = | 73,786,976,294,838,206,464 | 282 | = | 4,835,703,278,458,516,698,824,704 | |||||
23 | = | 8 | 219 | = | 524,288 | 235 | = | 34,359,738,368 | 251 | = | 2,251,799,813,685,248 | 267 | = | 147,573,952,589,676,412,928 | 283 | = | 9,671,406,556,917,033,397,649,408 | |||||
24 | = | 16 | 220 | = | 1,048,576 | 236 | = | 68,719,476,736 | 252 | = | 4,503,599,627,370,496 | 268 | = | 295,147,905,179,352,825,856 | 284 | = | 19,342,813,113,834,066,795,298,816 | |||||
25 | = | 32 | 221 | = | 2,097,152 | 237 | = | 137,438,953,472 | 253 | = | 9,007,199,254,740,992 | 269 | = | 590,295,810,358,705,651,712 | 285 | = | 38,685,626,227,668,133,590,597,632 | |||||
26 | = | 64 | 222 | = | 4,194,304 | 238 | = | 274,877,906,944 | 254 | = | 18,014,398,509,481,984 | 270 | = | 1,180,591,620,717,411,303,424 | 286 | = | 77,371,252,455,336,267,181,195,264 | |||||
27 | = | 128 | 223 | = | 8,388,608 | 239 | = | 549,755,813,888 | 255 | = | 36,028,797,018,963,968 | 271 | = | 2,361,183,241,434,822,606,848 | 287 | = | 154,742,504,910,672,534,362,390,528 | |||||
28 | = | 256 | 224 | = | 16,777,216 | 240 | = | 1,099,511,627,776 | 256 | = | 72,057,594,037,927,936 | 272 | = | 4,722,366,482,869,645,213,696 | 288 | = | 309,485,009,821,345,068,724,781,056 | |||||
29 | = | [en] | 225 | = | 33,554,432 | 241 | = | 2,199,023,255,552 | 257 | = | 144,115,188,075,855,872 | 273 | = | 9,444,732,965,739,290,427,392 | 289 | = | 618,970,019,642,690,137,449,562,112 | |||||
210 | = | [en] | 226 | = | 67,108,864 | 242 | = | 4,398,046,511,104 | 258 | = | 288,230,376,151,711,744 | 274 | = | 18,889,465,931,478,580,854,784 | 290 | = | 1,237,940,039,285,380,274,899,124,224 | |||||
211 | = | 2,048 | 227 | = | 134,217,728 | 243 | = | 8,796,093,022,208 | 259 | = | 576,460,752,303,423,488 | 275 | = | 37,778,931,862,957,161,709,568 | 291 | = | 2,475,880,078,570,760,549,798,248,448 | |||||
212 | = | 4,096 | 228 | = | 268,435,456 | 244 | = | 17,592,186,044,416 | 260 | = | 1,152,921,504,606,846,976 | 276 | = | 75,557,863,725,914,323,419,136 | 292 | = | 4,951,760,157,141,521,099,596,496,896 | |||||
213 | = | 8,192 | 229 | = | 536,870,912 | 245 | = | 35,184,372,088,832 | 261 | = | 2,305,843,009,213,693,952 | 277 | = | 151,115,727,451,828,646,838,272 | 293 | = | 9,903,520,314,283,042,199,192,993,792 | |||||
214 | = | 16,384 | 230 | = | 1,073,741,824 | 246 | = | 70,368,744,177,664 | 262 | = | 4,611,686,018,427,387,904 | 278 | = | 302,231,454,903,657,293,676,544 | 294 | = | 19,807,040,628,566,084,398,385,987,584 | |||||
215 | = | 32,768 | 231 | = | 2,147,483,648 | 247 | = | 140,737,488,355,328 | 263 | = | 9,223,372,036,854,775,808 | 279 | = | 604,462,909,807,314,587,353,088 | 295 | = | 39,614,081,257,132,168,796,771,975,168 |
Можна побачити, що, починаючи з 2 остання цифра є періодичною з періодом 4, з циклом 2-4-8-6- і, починаючи з 4, дві останні цифри є періодичними з періодом 20. Ці моделі, зазвичай, правильні для будь-якій степені, та будь-яких . Модель, звісно, продовжується у випадках, коли кожна структура бере свій початок з 2k і період є мультиплікативним порядком числа 2 по модулю 5k, де φ(5k) = 4 × 5k−1 (φ — функція Ейлера, див. мультиплікативна група кільця лишків за модулем n).
Деякі обрані степені двійки
- 28 = 256
- Кількість значень, представлених 8 біт в байт, а більш конкретно назвати як октет. (Термін байт часто визначається як ( колекція бітів), а не на основі суворого визначення 8-розрядну величину, як показали термін кілобайт.)
- 210 = 1,024
- Двійкове наближення кіло-, або множник 1,000, що викликає зміну префікса. Наприклад: 1,024 байт = 1 кілобайт (або Кібібайт).
- Це число не має особливого значення для комп'ютерів, але важливо для людини, тому що ми використовуємо степені десяти.
- 212 = 4,096
- Розмір сторінки процесора Intel x86.
- 216 = 65,536
- Число різних значень, які представлені у одному слові 16-бітного процесора, такому як оригінальні процесори x86.
- Максимальна дальність типу short integer в мовах програмування C # і Java. Максимальна дальність типу Word або SmallInt в мові програмуванняPascal.
- 220 = 1,048,576
- Двійкове наближення мега-, або множник 1,000,000, що викликає зміну префікса. Наприклад: 1,048,576 байт = 1 мегабайт (або мегабайт).
- Це число не має особливого значення для комп'ютерів, але важливо для людини, тому що ми використовуємо степені десяти.
- 224 = 16,777,216
- Кількість унікальних Кольорів, які можуть бути відображені в ( true color), що використовується у звичайному моніторі комп'ютера.
- Це число є результатом використання трьохканальної RGB системи, з 8 бітами для кожного каналу, або 24 бітами взагалі.
- 230 = 1,073,741,824
- Двійкове наближення гіга-, або множник 1,000,000,000, який викликає зміну префікса. Наприклад, 1,073,741,824 байт = 1 гігабайт (або Гібібайт).
- Це число не має особливого значення для комп'ютерів, але важливо для людини, тому що ми використовуємо степені десяти.
- 231 = 2,147,483,648
- Кількість невід'ємних значень для знакового 32-бітового цілого числа. Так як час Unix вимірюється в секундах з 1 січня 1970 вона буде працювати до 2,147,483,647 секунд або 3:14:07 UTC на вівторок, 19 січня 2038 на 32-розрядних комп'ютерах, що працюють під управлінням Unix, з'явиться проблема, відома як проблема 2038 року.
Степені 1024
послідовність A140300 з Онлайн енциклопедії послідовностей цілих чисел, OEIS Перші кілька степенів 210 є трохи більшими, ніж у 1000:
20 | = | 1 | ≈ 10000 | (0% відхилення) |
210 | = | 1024 | ≈ 10001 | (2.4% відхилення) |
220 | = | 1 048 576 | ≈ 10002 | (4.9% відхилення) |
230 | = | 1 073 741 824 | ≈ 10003 | (7.4% відхилення) |
240 | = | 1 099 511 627 776 | ≈ 10004 | (10% відхилення) |
250 | = | 1 125 899 906 842 624 | ≈ 10005 | (12.6% відхилення) |
260 | = | 1 152 921 504 606 846 976 | ≈ 10006 | (15.3% відхилення) |
270 | = | 1 180 591 620 717 411 303 424 | ≈ 10007 | (18.1% відхилення) |
280 | = | 1 208 925 819 614 629 174 706 176 | ≈ 10008 | (20.9% відхилення) |
290 | = | 1 237 940 039 285 380 274 899 124 224 | ≈ 10009 | (23.8% відхилення) |
2100 | = | 1 267 650 600 228 229 401 496 703 205 376 | ≈ 100010 | (26.8% відхилення) |
2110 | = | 1 298 074 214 633 706 907 132 624 082 305 024 | ≈ 100011 | (29.8% відхилення) |
2120 | = | 1 329 227 995 784 915 872 903 807 060 280 344 576 | ≈ 100012 | (32.9% відхилення) |
Див. [ru].
Степені двійки, чиї показники є степенями двійки
Оскільки дані (зокрема, цілі числа) та адреси даних зберігаються з використанням тих самих апаратних засобів, і дані зберігаються в одній або декількох октетах (23), [en] двійки є поширеними. Наприклад, послідовність A001146 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
- 21 = 2
- 22 = 4
- 24 = 16
- 28 = 256
- 216 = [en]
- 232 = 4,294,967,296
- 264 = 18,446,744,073,709,551,616 (20 цифр)
- 2128 = 340,282,366,920,938,463,463,374,607,431,768,211,456 (39 цифр)
- 2256 =
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 цифр) - 2512 =
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 цифр) - 21,024 = 179,769,313,486,231,590,772,931,…,304,835,356,329,624,224,137,216 (309 цифр)
- 22,048 = 323,170,060,713,110,073,007,148,…,193,555,853,611,059,596,230,656 (617 цифр)
- 24,096 = 104,438,888,141,315,250,669,175,…,243,804,708,340,403,154,190,336 (1,234 цифр)
- 28,192 = 109,074,813,561,941,592,946,298,…,997,186,505,665,475,715,792,896 (2,467 цифр)
- 216,384 = 118,973,149,535,723,176,508,576,…,460,447,027,290,669,964,066,816 (4,933 цифр)
- 232,768 = 141,546,103,104,495,478,900,155,…,541,122,668,104,633,712,377,856 (9,865 цифр)
- 265,536 = 200,352,993,040,684,646,497,907,…,339,445,587,895,905,719,156,736 (19,729 цифр)
- 2131,072 = 4,014,132,182,036,063,039,166,...,850,665,812,318,570,934,173,696 (39,457 цифр)
Деякі з цих чисел виражають кількість значень, яку можна представити за допомогою загальних комп'ютерних типів даних. Наприклад, 32-бітове слово, що складається з 4 байтів може виражати 232 різних значень, які можна розглядати як бітові шаблони, або ж їх зазвичай інтерпретують як числа без знака від 0 до 232 − 1, або в діапазоні від числа зі знаком між −231 і 231 − 1. Також див. тетрація та гіпероператор. Для детальнішої інформації про представлення чисел зі знаком див. доповняльний код.
Цифри формують [ru] для будь-якої послідовності натуральних чисел, ряд
зводиться до ірраціональних чисел. Незважаючи на швидке зростання цієї послідовності, це є ірраціональною послідовністю з найповільнішими темпами зростання поміж усіх відомих.
Швидкий алгоритм для перевірки чи є натуральне число степенем двійки
Бінарне представлення чисел дозволяє застосовувати дуже швидкий тест, щоб визначити, чи є дане натуральне число х степенем двійки:
- натуральне x є степенем двійки ⇔ (x & (x − 1)) дорівнює нулю.
де & знаходить є побітовим логічним AND. Зауважимо, що якщо x = 0, це неправильно вказує 0 степінь двійки, так що це перевірка працює тільки якщо x > 0.
Приклади:
1…111…1 | 1…111…111…1 | |||||
0…010…0 | 0…010…010…0 | |||||
0…001…1 | 0…010…001…1 | |||||
0…000…0 | 0…010…000…0 |
Доказ концепції:
Доведення використовує техніку контрапозиції.
Твердження, S: Якщо x&(x-1) = 0 і х ціле число більше нуля, то x = 2k (де k — ціле число, таке, що k>=0).
Концепція контрапозиції:
S1: P -> Q такий же, як S2: ~ Q -> ~ P
У звіті вище S1 і S2 мають контрапозиції один одного.
Так звітності можуть бути перераховані, як показано нижче
S': Якщо х — натуральне число, x ≠ 2k (k деяке невід'ємне ціле число), то х&(х-1) ≠ 0
Доведення:
Якщо x ≠ 2k, то хоча б 2 біти х є встановленими (давайте вважати, що m бітів встановлено).
Тепер, бітовий образ х — 1 може бути отриманий шляхом інвертування всіх бітів х до першого набору бітів х (від МЗР до СБ, включно з цим набором бітів).
Тепер ми бачимо, що вираз х & (х-1) має всі нульові біти до першого заданого біта х і з х & (х-1) має інші біти ті ж, як х, і х має принаймні два набори бітів, отже, предикат х і (х-1) ≠ 0 є вірним.
Швидкий алгоритм, щоб знайти число по модулю степенів двійки
Як узагальнення того, що написано вище, бінарне представлення цілих чисел дозволяє розрахувати модуль додатнього цілого числа (х) зі степенем двійки (y) дуже швидко:
- x mod y = (x & (y − 1)).
де & оператор побітового логічного AND . Це обходить необхідність виконання дорогого поділу. Це корисно, якщо операція по модулю є важливою частиною критичного шляху продуктивності, так як це може бути набагато швидше, ніж звичайний оператор модуля.
Алгоритм для перетворення будь-якого числа в найближчу степінь двійки
Наступна формула знаходить найближчу степінь двійки, за логарифмічною шкалою, заданого значення x > 0:
Це повинно відрізнятися від найближчої степені двійки за лінійною шкалою. Наприклад, 23 ближче до 16, ніж до 32, але попередня формула округлює його до 32, що відповідає тому, що 23/16 = 1,4375, більше, ніж 32/23 = 1,3913.
Якщо x — ціле значення, наступні кроки можна зробити щоб знайти найближче значення (відносно фактичного значення, а не двійкового логарифму) в комп'ютерній програмі:
- Знайти найбільш значущий розряд k, тобто встановити (1) з двійкового представлення x, коли {{{1}}} означає, молодший біт
- Тоді, якщо біт k − 1 дорівнює нулю, то результатом буде 2k. В іншому випадку результат дорівнює 2k + 1
Алгоритм для округлення до степені двійки
Іноді потрібно знайти найменшу степінь двійки, яка є не меншою за певне ціле n. Псевдокод алгоритму для обчислення наступної вищої степені двійки полягає в наступному: якщо вхідні дані є степенем двійки, вони повертаються без змін.
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;
Де | являє собою бінарний оператор «або», >> оператор двійковий зміщення праворуч, і «bitspace» — розмір (в бітах) цілого простору, виділеного n. Для більшості комп'ютерних архітектур, це значення є 8, 16, 32 або 64. Цей оператор працює, встановивши всі біти на правій стороні з найбільш значущих FLAGGED біт в 1, а потім збільшуючи загальне значення у кінці, так це «зашкалює» в найближчій степені двійки. Приклад кожного кроку цього алгоритму для числа 2689 має такий вигляд:
Двійковий вигляд | Десятковий вигляд |
---|---|
0101010000001 | 2,689 |
0101010000000 | 2,688 |
0111111000000 | 4,032 |
0111111110000 | 4,080 |
0111111111111 | 4,095 |
1000000000000 | 4,096 |
Як було показано вище, алгоритм дає правильне значення 4096. Найближчим степенем 2689, є 2048; Однак, цей алгоритм призначений тільки дати наступну, більш високу, степінь двійки до заданого числа, не найближчу. Інший спосіб отримання 'наступного за величиною' степеня двійки до заданого числа, що не залежить від довжини bitspace полягає в наступному.
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, if z = y — 1,
- x AND (NOT z) округлити до меншого,
- (x + z) AND (NOT z) округлити до вищого, і
- (x + y / 2) AND (NOT z) округлити до найближчого (додатні значення точно посередині округлюються до вищого, в той час як від'ємні значення точно посередині округлюються до нижчого)
x до кратному y.
Інші властивості
Сума всіх n-обраних біноміальних коефіцієнтів дорівнює 2n. Розглянемо множину всіх n- розрядних двійкових чисел. Її потужність буде 2n. Вона також буде сумою потужностей певних підмножин: підмножина цілих чисел без будь-яких 1s (що складаються з одного числа, записується у вигляді n 0s), підмножина з одного 1, підмножина з двома 1s, і так далі до підмножини з n 1s (що складається з ряду записаного у вигляді n 1s). Кожен з них, у свою чергу дорівнює біноміальному коефіцієнту індексованого n та кількість 1s, що розглядається (наприклад, є 10-обране-3 двійкові числа з десяти цифр, які включають в себе рівно три 1s).
Числом n-мірного гіперкуба є 2n. Крім того, число (n − 1) граней конфігурації n-мірного гіпероктаедра також 2n і формула для числа x-гранного n-мірного кроссполітопа є .
[en]: 2. [en] є 1⅓.
Див. також
- Двійкове число
- Геометрична прогресія
- [en]
- [en]
Посилання
- Lipschutz, Seymour (1982). Schaum's Outline of Theory and Problems of Essential Computer Mathematics. New York: McGraw-Hill. с. 3. ISBN .
- Sewell, Michael J. (1997). Mathematics Masterclasses. Oxford: Oxford University Press. с. 78. ISBN .
- Хоча вони розрізняються за розміром словом, всі процесори x86 використовувати термін «слово» для позначення 16 біт; Таким чином, 32-бітний процесор x86 ставиться до своєї рідної розмір слова в подвійне слово
- Guy, Richard K. (2004), E24 Irrationality sequences, Unsolved problems in number theory (вид. 3rd), Springer-Verlag, с. 346, ISBN , Zbl 1058.11001.
- Warren Jr., Henry S. (2002). Hacker's Delight. Addison Wesley. с. 48. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U matematici stepin dvijki oznachaye chislo vidu 2n de n ye cile chislo tobto vnaslidok pidnesennya do stepenya z chislom dva yak osnovoyu i cilim chislom n yak pokaznikom Vizualizaciya stepeniv dvijki vid 1 do 1024 20 do 210 Yaksho rozglyadati yak rezultat pidnesennya do stepenya lishe cili chisla to n obmezhuyetsya nevid yemnimi znachennyami tomu mi mayemo 1 2 i 2 pomnozheni sami na sebe pevnu kilkist raziv Cherez te sho dva ye osnovoyu dvijkovoyi sistemi chislennya stepeni dvijki ye poshirenimi v informatici Take chislo zapisane v dvijkovij sistemi ye stepenem dvoh yaka maye viglyad 100 000 abo 0 00 001 tak samo yak i stepeni desyati v desyatkovij sistemi Virazi ta poznachennyaVerbalni virazi matematichni poznachennya ta virazi komp yuternogo programuvannya z vikoristannyam operatora stepeni abo funkciyi vklyuchayut v sebe 2 v n 2 v stepeni n 2 stepin n power 2 n pow 2 n 2n 1 lt lt n 2 n 2 n 2 3 n 2 n A n 3 3 3 H 3 2 n displaystyle H 3 2 n 2 n displaystyle 2 to n 2 n 1 displaystyle 2 to n to 1 InformatikaDva v stepeni n zapisuyetsya u viglyadi 2n ye kilkistyu sposobiv yak mozhut buti organizovani biti v dvijkovomu slovi dovzhini n Yak bezznakovi cili ci sposobi predstavlyayut chisla vid 0 000 000 2n 1 111 111 vklyuchno Vidpovidni cili chisla ye dodatni vid yemni chisla ta nul div pryamij kod U bud yakomu razi na odin menshe nizh stepin dvijki chasto ye verhnoyu mezheyu cilogo chisla v dvijkovomu lichilniku Yak naslidok nomeri ciyeyi formi chasto z yavlyayutsya v programnomu zabezpechenni komp yutera Yak priklad videogra sho pracyuye na 8 bitnij sistemi mozhe obmezhiti rahunok abo kilkist elementiv gravec mozhe zberigati do 255 v rezultati vikoristannya bajta dovzhinoyu 8 bit shob zberegti nomer dayuchi maksimalne znachennya 28 1 255 Napriklad v gri Legend of Zelda golovnij geroj buv obmezhenij nosinnyam 255 rupij valyuta gri v bud yakij moment chasu i videogra Pac Man hvacko vimikayetsya yaksho kilkist rupij rivna 255 Stepeni dvijki chasto vikoristovuyetsya dlya vimiryuvannya pam yati komp yutera Bajt v danij chas mistit visim bit oktet v rezultati chogo mozhlivo 256 znachen 28 Termin bajt vikoristovuvavsya a v deyakih vipadkah i prodovzhuye buti kolekciyeyu bitiv zazvichaj vid 5 do 32 bit a ne tilki 8 bitovim blokom Prefiks kilo v poyednanni z bajt mozhe buti i tradicijno vikoristovuyetsya shob poznachati 1 024 210 Odnak zagalom termin kilo vikoristovuvavsya v Mizhnarodnij sistemi odinic dlya poznachennya 1 000 103 Binarni prefiksi buli standartizovani napriklad kibi Ki sho oznachaye 1 024 Majzhe vsi registri procesora mayut rozmiri yaki ye stepenem dvijki napriklad 32 abo 64 ye najbilsh poshirenimi Stepeni dvijki z yavlyayutsya v inshih miscyah Dlya bagatoh diskiv prinajmni odin z rozmiriv sektora kilkist sektoriv na dorizhci i kilkist trekiv na poverhni ye stepinnyu dvijki Rozmir logichnogo bloku majzhe zavzhdi ye stepinnyu dvijki Chisla yaki ne ye stepenyami dvijki zustrichayutsya v ryadi situacij takih yak rozdilna zdatnist displeya ale voni chasto ye sumoyu abo dobutkom tilki dvijki v drugomu abo tretomu abo dvijki v minus pershij stepeni Napriklad 640 512 128 128 5 i 480 32 15 Inshimi slovami voni mayut dosit regulyarni bitovi kombinaciyi Prosti chisla MersennaProste chislo sho na odinicyu menshe nizh stepin dvijki nazivayetsya chislom Mersenna Napriklad proste chislo 31 bude chislom Mersenna oskilki vono na odinicyu menshe nizh 32 25 Analogichno proste chislo napriklad 257 sho na odinicyu bilshe nizh naturalnij stepin dvijki nazivayetsya chislom Ferma pokaznik sam bude stepenem dvijki Drib sho maye stepin dvijki znamennikom nazivayetsya dvijkovo racionalnim Chisla yaki mozhna podati u viglyadi sumi poslidovnih naturalnih chisel nazivayutsya en voni tochno ne ye stepenyami dvijki Elementi Evklida Kniga IXGeometrichna progresiya 1 2 4 8 16 32 abo v dvijkovij sistemi chislennya 1 10 100 1000 10000 100000 vidigraye vazhlivu rol v teoriyi chisel Kniga IX Teorema 36 Elementiv dovodit sho yaksho suma pershih n chleniv ciyeyi progresiyi ye prostim chislom pro chisla Mersenna jshlosya vishe to yakraz cya suma pomnozhena na n j chlen doskonale chislo Napriklad suma pershih 5 chleniv ryadu 1 2 4 8 16 31 ye prostim chislom Suma 31 mnozhitsya na 16 p yatij chlen ryadu dorivnyuye 496 sho ye doskonalim chislom Kniga IX Teorema 35 dovodit sho v geometrichnij progresiyi yaksho pershij chlen vidnimayetsya vid drugogo i ostannogo v poslidovnosti todi yak ostacha drugogo vidnositsya do pershogo tak ostacha ostannogo bude vidnositisya do vsih pered nim Ce pereformulyuvannya nashoyi formuli dlya ranishe zgadanoyi geometrichnoyi progresiyi Zastosovuyuchi ce do geometrichnoyi progresiyi 31 62 124 248 496 v rezultati peretvorennya z 1 2 4 8 16 pomnozhivshi vsi elementi na 31 mi bachimo sho 62 minus 31 dorivnyuye 31 todi yak 496 minus 31 ye sumoyu 31 62 124 248 Tomu chislo 1 2 4 8 16 31 62 124 i 248 ye sumoyu 496 i dali chisla sho ye dilnikami 496 Dijsno nehaj p ye dilnikom 496 i ne ye odnim z cih chisel Pripustimo p q dorivnyuye 16 31 abo 31 ye q todi yak p ye 16 Teper p mozhe ne mozhe buti dilnikom 16 abo vono bulo b sered chisel 1 2 4 8 abo 16 Tomu 31 ne mozhe buti dilnikom q A tak yak 31 dilit q i q vimiryuye 496 z osnovnoyi teoremi arifmetiki viplivaye sho q povinno buti dilnikom 16 i buti sered chisel 1 2 4 8 abo 16 Nehaj q bude 4 todi p povinno buti 124 sho nemozhlivo tak yak za umovoyu p ne mozhe znahoditisya sered chisel 1 2 4 8 16 31 62 124 abo 248 Pershi 96 stepeniv dvijkiposlidovnist A000079 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS 20 1 216 en 232 4 294 967 296 248 281 474 976 710 656 264 18 446 744 073 709 551 616 280 1 208 925 819 614 629 174 706 176 21 2 217 131 072 233 8 589 934 592 249 562 949 953 421 312 265 36 893 488 147 419 103 232 281 2 417 851 639 229 258 349 412 352 22 4 218 262 144 234 17 179 869 184 250 1 125 899 906 842 624 266 73 786 976 294 838 206 464 282 4 835 703 278 458 516 698 824 704 23 8 219 524 288 235 34 359 738 368 251 2 251 799 813 685 248 267 147 573 952 589 676 412 928 283 9 671 406 556 917 033 397 649 408 24 16 220 1 048 576 236 68 719 476 736 252 4 503 599 627 370 496 268 295 147 905 179 352 825 856 284 19 342 813 113 834 066 795 298 816 25 32 221 2 097 152 237 137 438 953 472 253 9 007 199 254 740 992 269 590 295 810 358 705 651 712 285 38 685 626 227 668 133 590 597 632 26 64 222 4 194 304 238 274 877 906 944 254 18 014 398 509 481 984 270 1 180 591 620 717 411 303 424 286 77 371 252 455 336 267 181 195 264 27 128 223 8 388 608 239 549 755 813 888 255 36 028 797 018 963 968 271 2 361 183 241 434 822 606 848 287 154 742 504 910 672 534 362 390 528 28 256 224 16 777 216 240 1 099 511 627 776 256 72 057 594 037 927 936 272 4 722 366 482 869 645 213 696 288 309 485 009 821 345 068 724 781 056 29 en 225 33 554 432 241 2 199 023 255 552 257 144 115 188 075 855 872 273 9 444 732 965 739 290 427 392 289 618 970 019 642 690 137 449 562 112 210 en 226 67 108 864 242 4 398 046 511 104 258 288 230 376 151 711 744 274 18 889 465 931 478 580 854 784 290 1 237 940 039 285 380 274 899 124 224 211 2 048 227 134 217 728 243 8 796 093 022 208 259 576 460 752 303 423 488 275 37 778 931 862 957 161 709 568 291 2 475 880 078 570 760 549 798 248 448 212 4 096 228 268 435 456 244 17 592 186 044 416 260 1 152 921 504 606 846 976 276 75 557 863 725 914 323 419 136 292 4 951 760 157 141 521 099 596 496 896 213 8 192 229 536 870 912 245 35 184 372 088 832 261 2 305 843 009 213 693 952 277 151 115 727 451 828 646 838 272 293 9 903 520 314 283 042 199 192 993 792 214 16 384 230 1 073 741 824 246 70 368 744 177 664 262 4 611 686 018 427 387 904 278 302 231 454 903 657 293 676 544 294 19 807 040 628 566 084 398 385 987 584 215 32 768 231 2 147 483 648 247 140 737 488 355 328 263 9 223 372 036 854 775 808 279 604 462 909 807 314 587 353 088 295 39 614 081 257 132 168 796 771 975 168 Mozhna pobachiti sho pochinayuchi z 2 ostannya cifra ye periodichnoyu z periodom 4 z ciklom 2 4 8 6 i pochinayuchi z 4 dvi ostanni cifri ye periodichnimi z periodom 20 Ci modeli zazvichaj pravilni dlya bud yakij stepeni ta bud yakih Model zvisno prodovzhuyetsya u vipadkah koli kozhna struktura bere svij pochatok z 2k i period ye multiplikativnim poryadkom chisla 2 po modulyu 5k de f 5k 4 5k 1 f funkciya Ejlera div multiplikativna grupa kilcya lishkiv za modulem n Deyaki obrani stepeni dvijki28 256 Kilkist znachen predstavlenih 8 bit v bajt a bilsh konkretno nazvati yak oktet Termin bajt chasto viznachayetsya yak kolekciya bitiv a ne na osnovi suvorogo viznachennya 8 rozryadnu velichinu yak pokazali termin kilobajt 210 1 024 Dvijkove nablizhennya kilo abo mnozhnik 1 000 sho viklikaye zminu prefiksa Napriklad 1 024 bajt 1 kilobajt abo Kibibajt Ce chislo ne maye osoblivogo znachennya dlya komp yuteriv ale vazhlivo dlya lyudini tomu sho mi vikoristovuyemo stepeni desyati 212 4 096 Rozmir storinki procesora Intel x86 216 65 536 Chislo riznih znachen yaki predstavleni u odnomu slovi 16 bitnogo procesora takomu yak originalni procesori x86 Maksimalna dalnist tipu short integer v movah programuvannyaC i Java Maksimalna dalnist tipu Word abo SmallInt v movi programuvannyaPascal 220 1 048 576 Dvijkove nablizhennya mega abo mnozhnik 1 000 000 sho viklikaye zminu prefiksa Napriklad 1 048 576 bajt 1 megabajt abo megabajt Ce chislo ne maye osoblivogo znachennya dlya komp yuteriv ale vazhlivo dlya lyudini tomu sho mi vikoristovuyemo stepeni desyati 224 16 777 216 Kilkist unikalnih Koloriv yaki mozhut buti vidobrazheni v true color sho vikoristovuyetsya u zvichajnomu monitori komp yutera Ce chislo ye rezultatom vikoristannya trohkanalnoyi RGB sistemi z 8 bitami dlya kozhnogo kanalu abo 24 bitami vzagali 230 1 073 741 824 Dvijkove nablizhennya giga abo mnozhnik 1 000 000 000 yakij viklikaye zminu prefiksa Napriklad 1 073 741 824 bajt 1 gigabajt abo Gibibajt Ce chislo ne maye osoblivogo znachennya dlya komp yuteriv ale vazhlivo dlya lyudini tomu sho mi vikoristovuyemo stepeni desyati 231 2 147 483 648 Kilkist nevid yemnih znachen dlya znakovogo 32 bitovogo cilogo chisla Tak yak chas Unix vimiryuyetsya v sekundah z 1 sichnya 1970 vona bude pracyuvati do 2 147 483 647 sekund abo 3 14 07 UTC na vivtorok 19 sichnya 2038 na 32 rozryadnih komp yuterah sho pracyuyut pid upravlinnyam Unix z yavitsya problema vidoma yak problema 2038 roku Stepeni 1024poslidovnist A140300 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Pershi kilka stepeniv 210 ye trohi bilshimi nizh u 1000 20 1 10000 0 vidhilennya 210 1024 10001 2 4 vidhilennya 220 1 048 576 10002 4 9 vidhilennya 230 1 073 741 824 10003 7 4 vidhilennya 240 1 099 511 627 776 10004 10 vidhilennya 250 1 125 899 906 842 624 10005 12 6 vidhilennya 260 1 152 921 504 606 846 976 10006 15 3 vidhilennya 270 1 180 591 620 717 411 303 424 10007 18 1 vidhilennya 280 1 208 925 819 614 629 174 706 176 10008 20 9 vidhilennya 290 1 237 940 039 285 380 274 899 124 224 10009 23 8 vidhilennya 2100 1 267 650 600 228 229 401 496 703 205 376 100010 26 8 vidhilennya 2110 1 298 074 214 633 706 907 132 624 082 305 024 100011 29 8 vidhilennya 2120 1 329 227 995 784 915 872 903 807 060 280 344 576 100012 32 9 vidhilennya Div ru Stepeni dvijki chiyi pokazniki ye stepenyami dvijkiOskilki dani zokrema cili chisla ta adresi danih zberigayutsya z vikoristannyam tih samih aparatnih zasobiv i dani zberigayutsya v odnij abo dekilkoh oktetah 23 en dvijki ye poshirenimi Napriklad poslidovnist A001146 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS 21 2 22 4 24 16 28 256 216 en 232 4 294 967 296 264 18 446 744 073 709 551 616 20 cifr 2128 340 282 366 920 938 463 463 374 607 431 768 211 456 39 cifr 2256 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 cifr 2512 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 cifr 21 024 179 769 313 486 231 590 772 931 304 835 356 329 624 224 137 216 309 cifr 22 048 323 170 060 713 110 073 007 148 193 555 853 611 059 596 230 656 617 cifr 24 096 104 438 888 141 315 250 669 175 243 804 708 340 403 154 190 336 1 234 cifr 28 192 109 074 813 561 941 592 946 298 997 186 505 665 475 715 792 896 2 467 cifr 216 384 118 973 149 535 723 176 508 576 460 447 027 290 669 964 066 816 4 933 cifr 232 768 141 546 103 104 495 478 900 155 541 122 668 104 633 712 377 856 9 865 cifr 265 536 200 352 993 040 684 646 497 907 339 445 587 895 905 719 156 736 19 729 cifr 2131 072 4 014 132 182 036 063 039 166 850 665 812 318 570 934 173 696 39 457 cifr Deyaki z cih chisel virazhayut kilkist znachen yaku mozhna predstaviti za dopomogoyu zagalnih komp yuternih tipiv danih Napriklad 32 bitove slovo sho skladayetsya z 4 bajtiv mozhe virazhati 232 riznih znachen yaki mozhna rozglyadati yak bitovi shabloni abo zh yih zazvichaj interpretuyut yak chisla bez znaka vid 0 do 232 1 abo v diapazoni vid chisla zi znakom mizh 231 i 231 1 Takozh div tetraciya ta giperoperator Dlya detalnishoyi informaciyi pro predstavlennya chisel zi znakom div dopovnyalnij kod Cifri 2 2 n displaystyle 2 2 n formuyut ru dlya bud yakoyi poslidovnosti naturalnih chisel ryad i 0 1 2 2 i x i 1 2 x 0 1 4 x 1 1 16 x 2 displaystyle sum i 0 infty frac 1 2 2 i x i frac 1 2x 0 frac 1 4x 1 frac 1 16x 2 cdots zvoditsya do irracionalnih chisel Nezvazhayuchi na shvidke zrostannya ciyeyi poslidovnosti ce ye irracionalnoyu poslidovnistyu z najpovilnishimi tempami zrostannya pomizh usih vidomih Shvidkij algoritm dlya perevirki chi ye naturalne chislo stepenem dvijkiBinarne predstavlennya chisel dozvolyaye zastosovuvati duzhe shvidkij test shob viznachiti chi ye dane naturalne chislo h stepenem dvijki naturalne x ye stepenem dvijki x amp x 1 dorivnyuye nulyu de amp znahodit ye pobitovim logichnim AND Zauvazhimo sho yaksho x 0 ce nepravilno vkazuye 0 stepin dvijki tak sho ce perevirka pracyuye tilki yaksho x gt 0 Prikladi 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 amp x 1 0 000 0 y amp y 1 0 010 000 0 Dokaz koncepciyi Dovedennya vikoristovuye tehniku kontrapoziciyi Tverdzhennya S Yaksho x amp x 1 0 i h cile chislo bilshe nulya to x 2k de k cile chislo take sho k gt 0 Koncepciya kontrapoziciyi S1 P gt Q takij zhe yak S2 Q gt P U zviti vishe S1 i S2 mayut kontrapoziciyi odin odnogo Tak zvitnosti mozhut buti pererahovani yak pokazano nizhche S Yaksho h naturalne chislo x 2k k deyake nevid yemne cile chislo to h amp h 1 0 Dovedennya Yaksho x 2k to hocha b 2 biti h ye vstanovlenimi davajte vvazhati sho m bitiv vstanovleno Teper bitovij obraz h 1 mozhe buti otrimanij shlyahom invertuvannya vsih bitiv h do pershogo naboru bitiv h vid MZR do SB vklyuchno z cim naborom bitiv Teper mi bachimo sho viraz h amp h 1 maye vsi nulovi biti do pershogo zadanogo bita h i z h amp h 1 maye inshi biti ti zh yak h i h maye prinajmni dva nabori bitiv otzhe predikat h i h 1 0 ye virnim Shvidkij algoritm shob znajti chislo po modulyu stepeniv dvijki Yak uzagalnennya togo sho napisano vishe binarne predstavlennya cilih chisel dozvolyaye rozrahuvati modul dodatnogo cilogo chisla h zi stepenem dvijki y duzhe shvidko x mod y x amp y 1 de amp operator pobitovogo logichnogo AND Ce obhodit neobhidnist vikonannya dorogogo podilu Ce korisno yaksho operaciya po modulyu ye vazhlivoyu chastinoyu kritichnogo shlyahu produktivnosti tak yak ce mozhe buti nabagato shvidshe nizh zvichajnij operator modulya Algoritm dlya peretvorennya bud yakogo chisla v najblizhchu stepin dvijkiNastupna formula znahodit najblizhchu stepin dvijki za logarifmichnoyu shkaloyu zadanogo znachennya x gt 0 2 r o u n d log 2 x displaystyle 2 mathrm round log 2 x Ce povinno vidriznyatisya vid najblizhchoyi stepeni dvijki za linijnoyu shkaloyu Napriklad 23 blizhche do 16 nizh do 32 ale poperednya formula okruglyuye jogo do 32 sho vidpovidaye tomu sho 23 16 1 4375 bilshe nizh 32 23 1 3913 Yaksho x cile znachennya nastupni kroki mozhna zrobiti shob znajti najblizhche znachennya vidnosno faktichnogo znachennya a ne dvijkovogo logarifmu v komp yuternij programi Znajti najbilsh znachushij rozryad k tobto vstanoviti 1 z dvijkovogo predstavlennya x koli 1 oznachaye molodshij bit Todi yaksho bit k 1 dorivnyuye nulyu to rezultatom bude 2k V inshomu vipadku rezultat dorivnyuye 2k 1Algoritm dlya okruglennya do stepeni dvijkiInodi potribno znajti najmenshu stepin dvijki yaka ye ne menshoyu za pevne cile n Psevdokod algoritmu dlya obchislennya nastupnoyi vishoyi stepeni dvijki polyagaye v nastupnomu yaksho vhidni dani ye stepenem dvijki voni povertayutsya bez zmin n n 1 n n n gt gt 1 n n n gt gt 2 n n n gt gt 4 n n n gt gt 8 n n n gt gt 16 n n n gt gt bitspace 2 n n 1 De yavlyaye soboyu binarnij operator abo gt gt operator dvijkovij zmishennya pravoruch i bitspace rozmir v bitah cilogo prostoru vidilenogo n Dlya bilshosti komp yuternih arhitektur ce znachennya ye 8 16 32 abo 64 Cej operator pracyuye vstanovivshi vsi biti na pravij storoni z najbilsh znachushih FLAGGED bit v 1 a potim zbilshuyuchi zagalne znachennya u kinci tak ce zashkalyuye v najblizhchij stepeni dvijki Priklad kozhnogo kroku cogo algoritmu dlya chisla 2689 maye takij viglyad Dvijkovij viglyad Desyatkovij viglyad 0101010000001 2 689 0101010000000 2 688 0111111000000 4 032 0111111110000 4 080 0111111111111 4 095 1000000000000 4 096 Yak bulo pokazano vishe algoritm daye pravilne znachennya 4096 Najblizhchim stepenem 2689 ye 2048 Odnak cej algoritm priznachenij tilki dati nastupnu bilsh visoku stepin dvijki do zadanogo chisla ne najblizhchu Inshij sposib otrimannya nastupnogo za velichinoyu stepenya dvijki do zadanogo chisla sho ne zalezhit vid dovzhini bitspace polyagaye v nastupnomu unsigned int get nextpowerof2 unsigned int n Below indicates passed no is a power of 2 so return the same if n amp n 1 return n while n amp n 1 n n amp n 1 n n lt lt 1 return n Shvidki algoritmi shob okrugliti bud yake cile chislo do kratnogo zadanoyi stepeni dvohDlya bud yakogo cilogo x i nevid yemnoyi stepeni dvijki y if z y 1 x AND NOT z okrugliti do menshogo x z AND NOT z okrugliti do vishogo i x y 2 AND NOT z okrugliti do najblizhchogo dodatni znachennya tochno poseredini okruglyuyutsya do vishogo v toj chas yak vid yemni znachennya tochno poseredini okruglyuyutsya do nizhchogo x do kratnomu y Inshi vlastivostiSuma vsih n obranih binomialnih koeficiyentiv dorivnyuye 2n Rozglyanemo mnozhinu vsih n rozryadnih dvijkovih chisel Yiyi potuzhnist bude 2n Vona takozh bude sumoyu potuzhnostej pevnih pidmnozhin pidmnozhina cilih chisel bez bud yakih 1s sho skladayutsya z odnogo chisla zapisuyetsya u viglyadi n 0s pidmnozhina z odnogo 1 pidmnozhina z dvoma 1s i tak dali do pidmnozhini z n 1s sho skladayetsya z ryadu zapisanogo u viglyadi n 1s Kozhen z nih u svoyu chergu dorivnyuye binomialnomu koeficiyentu indeksovanogo n ta kilkist 1s sho rozglyadayetsya napriklad ye 10 obrane 3 dvijkovi chisla z desyati cifr yaki vklyuchayut v sebe rivno tri 1s Chislom n mirnogo giperkuba ye 2n Krim togo chislo n 1 granej konfiguraciyi n mirnogo giperoktaedra takozh 2n i formula dlya chisla x grannogo n mirnogo krosspolitopa ye 2 x n x displaystyle scriptstyle 2 x n choose x en 2 en ye 1 Div takozhDvijkove chislo Geometrichna progresiya en en PosilannyaLipschutz Seymour 1982 Schaum s Outline of Theory and Problems of Essential Computer Mathematics New York McGraw Hill s 3 ISBN 0 07 037990 4 Sewell Michael J 1997 Mathematics Masterclasses Oxford Oxford University Press s 78 ISBN 0 19 851494 8 Hocha voni rozriznyayutsya za rozmirom slovom vsi procesori x86 vikoristovuvati termin slovo dlya poznachennya 16 bit Takim chinom 32 bitnij procesor x86 stavitsya do svoyeyi ridnoyi rozmir slova v podvijne slovo Guy Richard K 2004 E24 Irrationality sequences Unsolved problems in number theory vid 3rd Springer Verlag s 346 ISBN 0 387 20860 7 Zbl 1058 11001 Warren Jr Henry S 2002 Hacker s Delight Addison Wesley s 48 ISBN 978 0 201 91465 8