Биты, байты и трюки ушами

46 минут назад Прокомментировать Просмотры: 0

Небольшое вступление

С момента предыдущей публикации прошло немало времени, и за это время у меня появилась идея для ещё одной небольшой статьи.

Здесь мы рассмотрим, как с помощью побитовых операций выполнять сложение и получать противоположное число.

Числа и вычеты

Особенность представления чисел в компьютере

Во многих языках программирования, например C, C++, Java и C#, используются целочисленные типы данных с фиксированной разрядностью.

У таких типов есть особенность, которая существенно отличает их от привычных целых и натуральных чисел.

Чтобы разобраться в ней, рассмотрим два восьмибитных числа, записанных в двоичной системе:

Число A:

1	1	1	1	1	1	1	1

Число B:

0	0	0	0	0	0	0	1

Если рассматривать эти числа как беззнаковые, A равно 255, а B — 1. Обычная сумма составляет 256, но при сохранении результата в восьми битах перенос за пределы старшего разряда отбрасывается. Поэтому :

Перенос	1	1	1	1	1	1	1	0
+	1	1	1	1	1	1	1	1
+	0	0	0	0	0	0	0	1
Результат	0	0	0	0	0	0	0	0

Никакого парадокса здесь нет: мы выполняем арифметику по модулю 256.

В общем случае для k бит по модулю 2^k справедливо:

${ 2^k=\underbrace{{111\ldots1}_2}_{k\mbox{ раз}}+1_2=0 , }$

Здесь ${ 1_2 }$ и ${ {111\ldots1}_2 }$ — двоичные записи чисел. Это соотношение позволяет найти противоположное число :

${b:=-a = 0-a = \underbrace{{111\ldots1}_2}_{k\mbox{ раз}}+1_2 + (-a) = \underbrace{{111\ldots1}_2}_{k\mbox{ раз}} - a + 1_2 .}$

При записи числа в k бит выражение

${ \underbrace{{111\ldots1}_2}_{k\mbox{ раз}} - a }$

соответствует побитово инвертированной записи числа . Иными словами, нужно представить в двоичном виде и заменить каждый ноль единицей, а каждую единицу — нулём.

Затем остаётся прибавить единицу.

Таким образом, особенность представления чисел фиксированной разрядности позволяет найти элемент, обратный данному относительно сложения.

Побитовые логические операции и сложение

При сложении двоичных чисел в столбик перенос от двух цифр одного разряда возникает, когда обе они равны единице. Это подсказывает, что для выявления таких переносов можно использовать побитовое «логическое И».

Рассмотрим два восьмибитных числа. Для k бит рассуждение будет аналогичным:

${a=\overline{a_7 a_6 a_5 a_4 a_3 a_2 a_1 a_0},}$
${b=\overline{b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0},}$
$a_i , b_j \in \{0,1\},$
${a\&b = c=\overline{c_7 c_6 c_5 c_4 c_3 c_2 c_1 c_0}, \ c_i = a_i \land b_i}$

Значение показывает, в каких разрядах возникли переносы. Чтобы переместить их в следующие разряды, используем сдвиг влево на один бит: каждый бит переходит на позицию левее, а младший разряд заполняется нулём. При фиксированной разрядности бит, вышедший за пределы старшего разряда, отбрасывается. Такая операция соответствует умножению на два по модулю 2^k. Сдвиг влево обозначается так:

${\alpha << \beta,}$

Здесь $\alpha$ — сдвигаемое число, а $\beta$ — количество позиций сдвига. В нашем случае оно равно единице:

${с:=(a\&b)<<1.}$

Чтобы получить сумму цифр каждого разряда без учёта переносов, нужен ноль, если обе цифры одинаковы, и единица, если они различаются. Для этого подходит операция «исключающее ИЛИ», обозначаемая XOR или ${\oplus}$ .

Применим её к исходным числам:

${d:=a\oplus b.}$

Если , переносов больше нет и содержит искомую сумму. Если же $c\ne 0$ , необходимо сложить . Для этого выполним присваивания:

$a:=c; \ \ b:=d,$

Затем повторим вычисление и продолжим, пока переносы не исчезнут.

В виде блок-схемы алгоритм выглядит следующим образом:

Как выполнить вычитание?

С помощью побитовых операций можно описать и алгоритм получения противоположного числа (ссылка на SVG):

Объединив алгоритмы получения противоположного числа и сложения, можно вычислять выражения вида:

При этом важно помнить: числа фиксированной разрядности в рассматриваемой модели являются элементами кольца вычетов, поэтому не во всех случаях ведут себя как обычные целые числа.

Важное замечание. Именно подобные логические операции позволяют реализовать сложение и вычитание на уровне логических элементов процессора или другой цифровой системы.

Промежуточные итоги

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

Маски

Что такое маска

В этой статье маской называется число, которое при побитовом «И» позволяет выделить нужные биты значения переменной.

Рассмотрим простой пример:

«Логическое И»	1	0	1	1	1	1	1	1
«Логическое И»	1	1	0	0	0	0	0	1
Результат	1	0	0	0	0	0	0	1

В первой строке записано исходное значение, во второй — маска, которая выделяет два старших и один младший бит. Результат в таблице равен 10000001₂. На следующем изображении формулы приведена запись с лишними нулями: ${1000000001}_2$ . Разберём результат по разрядам:

Старший бит исходного числа равен единице, поэтому в результате он также равен единице.
Следующий бит исходного числа равен нулю. Хотя в маске на этой позиции стоит единица, результат равен нулю.
Остальные промежуточные биты обнуляются, поскольку соответствующие биты маски равны нулю.
Младший бит маски равен единице, поэтому в результат попадает младший бит исходного числа — единица.

Таким образом, маска позволяет извлечь нужные биты. Этот приём используется, например, при работе с битовыми флагами и оптимизации программ.

Где это применяется?

Битовые маски открывают возможности для работы с двоичным представлением данных, в том числе:

Разворот порядка битов числа;
Построение кодов Мортона и соответствующих кривых;
Работа с XOR-списками.

Далее рассмотрим разворот порядка битов. Если статья вызовет интерес, к двум остальным темам можно будет вернуться отдельно.

Пусть переменная a занимает один байт и содержит следующие биты:

Сначала поменяем местами старшие и младшие четыре бита:

Выделим маской старшие четыре бита и сдвинем их вправо на четыре позиции. В старшей половине результата окажутся нули.
Выделим младшие четыре бита и сдвинем их влево на четыре позиции. Нулями заполнится младшая половина результата.
Объединим полученные значения побитовой операцией «логическое ИЛИ».

Последовательность действий можно записать так:

${t_1 := a \& {11110000}_2 = \overline{a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8} \& {11110000}_2 = \overline{ a_1 a_2 a_3 a_4 0 0 0 0};}$
${t_2: = a \& {00001111}_2 = \overline{ a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8} \& {00001111}_2 = \overline{0 0 0 0 a_5 a_6 a_7 a_8 }; }$
${t_2 := t_2 << 4 = \overline{a_5 a_6 a_7 a_8 0 0 0 0 };}$
$a:= t_1 {|} t_2 ;$

Символ обозначает побитовое «логическое ИЛИ».

Половины байта поменялись местами, но порядок битов пока не стал полностью обратным:

${a=\overline{a_5 a_6 a_7 a_8 a_1 a_2 a_3 a_4}.}$

Теперь поменяем местами пары a5–a6 и a7–a8, а также a1–a2 и a3–a4:

${t_1 := a\&{11001100}_2 =\overline{a_5 a_6 0 0 a_1 a_2 0 0};}$
${t_2 := a\&{00110011}_2 =\overline{ 0 0 a_7 a_8 0 0 a_3 a_4 };}$
${t_1 := t_1 << 2 = \overline{ a_7 a_8 0 0 a_3 a_4 0 0} ;}$
${ a:=t_1 {|} t_2 = \overline{ a_7 a_8 a_5 a_6 a_3 a_4 a_1 a_2} ;}$

В четвёртой формуле допущена опечатка: сдвиг влево следует применять к t₂, а не к t₁.

Осталось поменять местами биты внутри каждой пары: a7 и a8, a5 и a6, a3 и a4, a1 и a2:

${ t_1 := a\&{ 1 0 1 0 1 0 1 0 }_2 = \overline{ a_7 0 a_5 0 a_3 0 a_1 0} ;}$
${ t_2 := a\&{ 0 1 0 1 0 1 0 1 }_2 = \overline{ 0 a_8 0 a_6 0 a_4 0 a_2 } ;}$
${t_2 := t_2 << 1 = \overline{ a_8 0 a_6 0 a_4 0 a_2 0 } ;}$
$a:=t_1{|} t_2 = \overline{ a_8 a_7 a_6 a_5 a_4 a_3 a_2 a_1} ;$

Так можно развернуть порядок битов в одном байте. Аналогичный подход применим к числам длиной 2, 4 или 8 байт, но потребует других масок и дополнительных шагов: например, обмена групп по 8 бит для 16-битного числа и групп по 16 бит для 32-битного.

Если хочется самостоятельно поэкспериментировать с подобными операциями, можно воспользоваться этим самодельным калькулятором.

А пока я выбираю тему для следующей статьи. Есть несколько вариантов: