Бит-реверсирование

Бит-реверси́рование ${\displaystyle (br_{k})}$, взаимно однозначное преобразование множества целых чисел от ${\displaystyle 0}$ до ${\displaystyle 2^{k}-1}$, переводящее число ${\displaystyle i}$ с двоичной записью ${\displaystyle b_{0}b_{1}\ldots b_{k-2}b_{k-1}}$ длины ${\displaystyle k}$ (разрешены нулевые старшие разряды) в число с двоичной записью ${\displaystyle b_{k-1}b_{k-2}\ldots b_{1}b_{0}}$.

Пример:

${\displaystyle i}$	${\displaystyle b_{0}b_{1}b_{2}}$	${\displaystyle b_{2}b_{1}b_{0}}$	${\displaystyle br_{3}(i)}$
${\displaystyle 0}$	0 0 0	0 0 0	${\displaystyle 0}$
${\displaystyle 1}$	0 0 1	1 0 0	${\displaystyle 4}$
${\displaystyle 2}$	0 1 0	0 1 0	${\displaystyle 2}$
${\displaystyle 3}$	0 1 1	1 1 0	${\displaystyle 6}$
${\displaystyle 4}$	1 0 0	0 0 1	${\displaystyle 1}$
${\displaystyle 5}$	1 0 1	1 0 1	${\displaystyle 5}$
${\displaystyle 6}$	1 1 0	0 1 1	${\displaystyle 3}$
${\displaystyle 7}$	1 1 1	1 1 1	${\displaystyle 7}$

Бит-реверсной перестановкой одномерного массива с ${\displaystyle n=2^{k}}$ элементами ${\displaystyle x_{0},x_{1},x_{2},\ldots ,x_{n-2},x_{n-1}}$ называется результат замены каждого элемента массива на элемент того же массива с бит-реверсированным индексом, т. е. массив с элементами ${\displaystyle x_{br_{k}(0)},x_{br_{k}(1)},x_{br_{k}(2)},\ldots ,x_{br_{k}(n-2)},x_{br_{k}(n-1)}}$.

Бит-реверсная перестановка элементов входного массива используется в алгоритмах быстрого преобразования Фурье.