Степень двойки

Визуализация степеней двойки

Степень двойки — натуральное число, равное числу $2$, умноженному на себя некоторое количество раз. $2^{n}$ — обозначение таких чисел, где $n$ — целое неотрицательное число.

Ряд степеней двойки: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536... (последовательность A000079 в OEIS)

В математике

• $2^{n}$ — количество подмножеств $n$-элементного множества.
• Сумма чисел n-й строки треугольника Паскаля равна $2^{n}$.
• Число Мерсенна имеет вид $M_{n}=2^{n}-1$.
• Число Ферма имеет вид $F_{n}=2^{2^{n}}+1$, где $n\geqslant 0$.
• $2^{64}-1$ — ответ на задачу о зёрнах на шахматной доске.

В информатике

Полупроводниковая логика работает с двумя состояниями (условно «есть напряжение — нет напряжения»), и степени двойки важны в компьютерном деле — как важны в ручном счёте степени десятки.

С помощью $n$-проводной шины можно адресовать $2^{n}$ ячеек памяти, и потому установленная ёмкость полупроводниковой памяти — всегда степень двойки. Отсюда же понятие «двоичный килобайт» или «кибибайт», 1024 байта. Объекты, не являющиеся полупроводниковой памятью (жёсткие диски, скорость передачи данных), или отвязанные от установленной ёмкости (твердотельные накопители) часто измеряют в десятичных или двоично-десятичных единицах.

$n$-битная ячейка памяти хранит одно из $2^{n}$ разных значений, от 0 до $2^{n}-1$. Например, один байт (8 бит) может принимать значения от 0 до 255 ($2^{8}-1$), поэтому игра Pac-Man имеет 255 действующих уровней и непроходимый 256-й, а в первой The Legend of Zelda кошелёк персонажа ограничен 255 монетами. В оцифровке графики и звука распространены $n$-битные семплы, и цветовые каналы RGB традиционно записываются числами от 0 до 255.

При умножении числа на $2^{n}$ его нужно просто сдвинуть на $n$ битов. Для ускорения расчётов типа index = y*width + x используют элементы, чей размер — или степень двойки (примеры: знакоместо ZX-Spectrum 8×8 пикселей; сектор диска 512 или 4096 байт), или сумма/разность небольшого количества таковых (пример: разрешение VGA 640 = 512 + 128, 480 = 512 − 32). На 2023 формула y·640 всё ещё оптимизируется через сумму сдвигов, а y·641 — уже нет (GCC 13.2 x64).

Существуют алгоритмы типа «разделяй и властвуй», которые работают на объектах, чей размер — степень двойки (возможно, ±1), а если нет — либо расширяют объект, либо используют дополнительные ветки. Быстрое преобразование Фурье крайне редко пишут для массивов, чей размер — не степень двойки. Задача синхронизации стрелков в общем случае решается шестью состояниями автомата, но для степеней двойки плюс-минус один — четырьмя.

В теории музыки

В нотной записи длительности нот имеют продолжительность, равную целой ноте, деленной на степень двойки; например, половинная нота (1/2), четвертная нота (1/4), восьмая нота (1/8) и шестнадцатая нота (1/16). Ноты с точкой или иным образом измененные имеют другую длительность. В тактовых размерах нижняя цифра, единица ударов, которую можно рассматривать как знаменатель дроби, почти всегда является степенью двойки.

Если отношение частот двух нот равно степени двойки, то интервал между этими нотами равен полной октаве. В этом случае соответствующие ноты имеют одно и то же название.