Степені 2

У математиці степінь двійки означає число виду 2n, де n є число, тобто внаслідок піднесення до степеня з числом два як основою і цілим числом n як показником.

Візуалізація степенів двійки від 1 до 1024 (20 до 210).

Якщо розглядати як результат піднесення до степеня лише цілі числа, то n обмежується невід'ємними значеннями,[1] тому ми маємо 1, 2 і 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), що на одиницю більше, ніж натуральна степінь двійки, називається числом Ферма; показник сам буде степенем двійки. Дріб, що має степінь двійки знаменником, називається двійково-раціональним. Числа, які можна подати у вигляді суми послідовних натуральних чисел, називаються послідовними числами; вони точно не є степенями двійки.

Елементи Евкліда, Книга 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=65,536 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=512 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=1024 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 × 5k1 (φ функція Ейлера, див. мультиплікативна група кільця лишків за модулем n).

Деякі обрані степені двійки

28 = 256
Кількість значень, представлених 8 біт в байт, а більш конкретно назвати як октет. (Термін байт часто визначається як колекція бітів, а не на основі суворого визначення 8-розрядну величину, як показали термін кілобайт.)
210 = 1,024
Двійкове наближення кіло-, або множник 1,000, що викликає зміну префікса. Наприклад: 1,024 байт = 1 кілобайт (або Кібібайт).
Це число не має особливого значення для комп'ютерів, але важливо для людини, тому що ми використовуємо степені десяти.
212 = 4,096
Розмір сторінки процесора Intel x86.
216 = 65,536
Число різних значень, які представлені у одному слові 16-бітного процесора, такому як оригінальні процесори x86.[3]
Максимальна дальність типу 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% відхилення)

Див. IEEE 1541-2002.

Степені двійки, чиї показники є степенями двійки

Оскільки дані (зокрема, цілі числа) та адреси даних зберігаються з використанням тих самих апаратних засобів, і дані зберігаються в одній або декількох октетах (23), подвійні степені двійки є поширеними. Наприклад, послідовність A001146 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

21 = 2
22 = 4
24 = 16
28 = 256
216 = 65,536
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 різних значень, які можна розглядати як бітові шаблони, aбо ж їх зазвичай інтерпретують як числа без знака від 0 до 232 − 1, або в діапазоні від числа зі знаком між −231 і 231 − 1. Також див. тетрація та гіпероператор. Для детальнішої інформації про представлення чисел зі знаком див. доповняльний код.

Цифри формують ірраціональну послідовність для будь-якої послідовності натуральних чисел, ряд

зводиться до ірраціональних чисел. Незважаючи на швидке зростання цієї послідовності, це є ірраціональною послідовністю з найповільнішими темпами зростання поміж усіх відомих.[4]

Швидкий алгоритм для перевірки чи є натуральне число степенем двійки

Бінарне представлення чисел дозволяє застосовувати дуже швидкий тест, щоб визначити, чи є дане натуральне число х степенем двійки:

натуральне x є степенем двійки ⇔ (x & (x − 1)) дорівнює нулю.

де & знаходить є побітовим логічним AND. Зауважимо, що якщо 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

Доказ концепції:
Доведення використовує техніку контрапозиції.

Твердження, 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 — ціле значення, наступні кроки можна зробити щоб знайти найближче значення (відносно фактичного значення, а не двійкового логарифму) в комп'ютерній програмі:

  1. Знайти найбільш значущий розряд k, тобто встановити (1) з двійкового представлення x, коли {{{1}}} означає, молодший біт
  2. Тоді, якщо біт k − 1 дорівнює нулю, то результатом буде 2k. В іншому випадку результат дорівнює 2k + 1

Алгоритм для округлення до степені двійки

Іноді потрібно знайти найменшу степінь двійки, яка є не меншою за певне ціле n. Псевдокод алгоритму для обчислення наступної вищої степені двійки полягає в наступному: якщо вхідні дані є степенем двійки, вони повертаються без змін.[5]

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-мірного кроссполітопа є .

Сума зворотних ступенів двійки: 2. Сума зворотних квадратів ступенів двійки є 1⅓.

Див. також

Посилання

  1. Lipschutz, Seymour (1982). Schaum's Outline of Theory and Problems of Essential Computer Mathematics. New York: McGraw-Hill. с. 3. ISBN 0-07-037990-4.
  2. Sewell, Michael J. (1997). Mathematics Masterclasses. Oxford: Oxford University Press. с. 78. ISBN 0-19-851494-8.
  3. Хоча вони розрізняються за розміром словом, всі процесори x86 використовувати термін «слово» для позначення 16 біт; Таким чином, 32-бітний процесор x86 ставиться до своєї рідної розмір слова в подвійне слово
  4. Guy, Richard K. (2004). E24 Irrationality sequences. Unsolved problems in number theory (вид. 3rd). Springer-Verlag. с. 346. ISBN 0-387-20860-7. Zbl 1058.11001..
  5. Warren Jr., Henry S. (2002). Hacker's Delight. Addison Wesley. с. 48. ISBN 978-0-201-91465-8.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.