Хабр·Russia·Monday, November 2, 2026 at 05:31 PM UTC

Биты, байты и финты ушами

Translate

Dahnny_14213 минут назад

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

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

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

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

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

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

Чтобы понять, о какой особенности идёт речь, достаточно рассмотреть два числа(пусть их длина будет равна 8 битам), которые далее записываются через двоичную систему счисления:

Число 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=\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 }$

будет равно тому значению, которое представляет из себя инвертированное двоичное представление числа . Т.е. нужно лишь взять число , перевести его в двоичную запись и инвертировать — заменить 0 на 1, а 1 на 0.

После того, как сделано инвертирование, нужно лишь прибавить 1.

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

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

Если складывать два числа, переведённых в двоичную систему счисления, с применением метода “сложение столбиком”, то можно заметить, что при на следующий разряд для двух двоичных цифр идёт единица лишь в том случае, когда складываемые цифры одного разряда равны 1. Это наводит на мысль, что для переноса единицы на следующий разряд, достаточно применить побитовую логическую операцию “логическое И”.

Таким образом для определения переносов между двумя числами(пусть их длина будет 8 бит, но для 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(не забывайте, что в рамках двоичной системы счисления умножение на 2 даёт просто приписывание справа нуля в двоичной записи, однако из-за ограничения на длину записи числа(k бит в общем случае и 8 бит в нашем случае) возникает такой момент, что изначальное значение старшего бита “уходит в никуда”. Для обозначения операции сдвига влево можно применить обозначение

${\alpha << \beta,}$

где $\alpha$ есть сдвигаемое число, а $\beta$ то число, на сколько надо сделать сдвиг(в рамках данного случая это 1). Тогда нужно после побитовой операции “логическое И” применить сдвиг:

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

Вам разряд записывается 0, если изначальные цифры равны 1 или 0, и 1, если одновременно они не равны ни 1, ни 0. Автор данной статьи предполагает, что читатель уже догадался, что для такого чуда нужно применить операцию “логическое ИСКЛЮЧАЮЩЕЕ-ИЛИ”, которая в дальнейшем обозначается или как XOR, или как ${\oplus}$ .

Т.е. таким образом для получения значений в разрядах(пока без переноса) нужно применить ранее описанную операцию:

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

Если окажется, что , то тогда переносы осуществлять нет нужды, а потому в уже хранится вся искомая сумма. Если же $c\ne 0$ , то нужно теперь сложить , а потому можно сделать такой шаг

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

а потом снова делать те операции, для вычисления .

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

А как вычитать?

Подобно тому, как была описана операция сложения двух чисел, может быть и описана(через побитовые операции) операция нахождения обратного по сложению числа (ссылка на svg):

Применяя алгоритмы нахождения числа, обратного к данному по отношению к операции сложения, и сложения, можно вычислять выражения следующего вида:

Однако важно понимать, что числа конечной длины - это лишь элементы кольца вычетов, а потому применять их всюду как целые не получится.

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

Краткое подведение итогов

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

Маски

Под маской в рамках данной статьи, как и в рамках написания кодов на C/C++, понимаются числа, которые при применении побитовой операции “логическое И” позволяет получить значения битов в той или иной переменной.

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

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

Из примеры выше(таблицы) первая строка – это какое-либо заданное число(значение переменной), а вторая строка - это уже маска, которая смотрит старшие два бита и младший из битов. Получается число, которое в двоичной записи записывается как ${1000000001}_2$ :

Старший бит равен 1, а потому в ответ в старшем бите равен 1;
Второй по старшинству бит равен 0, но в маске такой бит равен 1, из-за чего этот бит равен 0 в ответе;
все биты до младшего в ответе(результате) равны 0 по той причине, что в маске на соответствующих позициях стоят 0;
Младший бит маски равен 1. Из-за этого записывается в ответ значение бита из верхней строки(а там 1).

Таким образом, как не трудно догадаться, маска позволяет “достать” нужные значения из битов, что применяется в битовых флагах(но это уже не тема статьи. Однако такое применяется при оптимизации тех или иных программ).

А как такое можно применять?

В подпараграфе выше указано, что битовые маски можно применять для работы с битами, что открывает уникальные возможности в применении:

Инверсия чисел(обратная побитовая запись);
Коды Мортона(создание кривой);
XOR-списки.

Далее описывается применение битовых масок для инверсии чисел(инверсии обратной побитовой записи). Если данная статья вызовет интерес, то будут описаны и другие два пункта из списка выше.

Пусть имеется некоторое число, записанное в переменную с длиной в 1 байт(пусть переменная обозначается за a):

Для начала нужно менять старшие 4 бита и младшие 4 бита местами. Для такого нужно:

Применяя маску, достать старшие 4 бита и посредством сдвига на 4 бита вправо получить число, состоящее из нулей в старших 4 битах и из старших четырёх бит на младших позициях(в новом числе);
Применяя маску, достать младшие 4 бита и посредством сдвига на 4 бита влево получить число, состоящее из нулей в младших 4 битах и из младших четырёх бит на старших позициях(в новом числе);
Применить побитовое "логическое ИЛИ" на полученные из первых двух пунктов числа.

Вот так такой алгоритм выглядит в виде записи последовательных формул:

${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_1 := t_1 >> 4 = \overline{ 0 0 0 0 a_1 a_2 a_3 a_4};}$ ${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}.}$

Теперь нужно поменять местами пары битов 5-6 и 7-8, а также 1-2 и 2-3:

${t_1 := a\&{11001100}_2 =\overline{a_5 a_6 0 0 a_1 a_2 0 0};}$ ${t_1 := t_1 >> 2 = \overline{ 00 a_5 a_6 0 0 a_1 a_2 } ;}$ ${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} ;}$

Теперь осталось поменять местами 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_1 := t_1 >> 1 = \overline{ 0 a_7 0 a_5 0 a_3 0 a_1 } ;}$ ${ 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} ;$

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

Если Вам интересно потыкать такие финты ушами, можете воспользоваться этим самодельным калькулятором.

А пока решается вопрос, на какую тему будет следующая статья(у меня есть несколько заготовок):

Моделирование зарплаты при вероятностном рынке труда;
Дальнейшие финты ушами с битами/байтами;
Небольшая нейросеть на C/C++.

Всем успехов!

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

View the original on Хабр →

KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.