Математика в двоичной системе счисления

Коротко

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

Зачем это нужно

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

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

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

Во всех примерах двоичные числа отмечены индексом ₂, а десятичные - индексом ₁₀.

Основные правила сложения

В одном двоичном разряде действуют четыре простых правила:

0₂ + 0₂ = 0₂
0₂ + 1₂ = 1₂
1₂ + 0₂ = 1₂
1₂ + 1₂ = 10₂

Запись 10₂ означает 2₁₀: в текущем разряде остается 0, а 1 переносится в следующий разряд.

Что такое перенос

Перенос - единица, которая переходит в следующий разряд, когда результат текущего разряда не помещается в одной двоичной цифре.

Сложение двоичных чисел

Сложение выполняется справа налево, как в десятичной системе.

Пример 1: без переноса

  0010₂
+ 0001₂
= 0011₂

Проверка:

2₁₀ + 1₁₀ = 3₁₀
0010₂ + 0001₂ = 0011₂

Пример 2: один перенос

  0011₂
+ 0001₂
= 0100₂

Справа получаем 1₂ + 1₂ = 10₂. Записываем 0, а единицу переносим в следующий разряд.

Проверка:

3₁₀ + 1₁₀ = 4₁₀
0011₂ + 0001₂ = 0100₂

Пример 3: несколько переносов

  0111₂
+ 0001₂
= 1000₂

Перенос последовательно проходит через три разряда.

Проверка:

7₁₀ + 1₁₀ = 8₁₀
0111₂ + 0001₂ = 1000₂

Сложение с входящим переносом

A	B	Перенос на входе	Цифра суммы	Перенос дальше
0	0	0	0	0
0	1	0	1	0
1	0	0	1	0
1	1	0	0	1
0	0	1	1	0
0	1	1	0	1
1	0	1	0	1
1	1	1	1	1

Последняя строка соответствует вычислению:

1₁₀ + 1₁₀ + 1₁₀ = 3₁₀ = 11₂

Вычитание двоичных чисел

Базовые правила:

0₂ - 0₂ = 0₂
1₂ - 0₂ = 1₂
1₂ - 1₂ = 0₂
10₂ - 1₂ = 1₂

В последнем случае происходит заем из старшего разряда. Двоичное 10₂ равно 2₁₀, поэтому 2₁₀ - 1₁₀ = 1₁₀.

Что такое заем

Заем используется, когда из 0 нужно вычесть 1. Из старшего разряда берется одна единица, которая в текущем разряде имеет значение 10₂.

Пример 1: без займа

  0111₂
- 0010₂
= 0101₂

Проверка:

7₁₀ - 2₁₀ = 5₁₀
0111₂ - 0010₂ = 0101₂

Пример 2: с одним займом

  0100₂
- 0001₂
= 0011₂

Проверка:

4₁₀ - 1₁₀ = 3₁₀
0100₂ - 0001₂ = 0011₂

Пример 3: заем через несколько разрядов

  1000₂
- 0011₂
= 0101₂

Проверка:

8₁₀ - 3₁₀ = 5₁₀
1000₂ - 0011₂ = 0101₂

Умножение двоичных чисел

Умножение строится из сдвигов и сложения. Правила умножения одного разряда очень просты:

0₂ · 0₂ = 0₂
0₂ · 1₂ = 0₂
1₂ · 0₂ = 0₂
1₂ · 1₂ = 1₂

Пример 1: умножение на 10₂

0011₂ · 0010₂ = 0110₂

Проверка:

3₁₀ · 2₁₀ = 6₁₀
0011₂ · 0010₂ = 0110₂

Умножение положительного целого числа на 10₂ = 2₁₀ соответствует сдвигу влево на один разряд, если результат помещается в выделенном размере.

Пример 2

  0011₂
· 0011₂
---------
  0011₂
+ 0110₂
= 1001₂

Проверка:

3₁₀ · 3₁₀ = 9₁₀
0011₂ · 0011₂ = 1001₂

Пример 3

0101₂ · 0010₂ = 1010₂

Проверка:

5₁₀ · 2₁₀ = 10₁₀
0101₂ · 0010₂ = 1010₂

Деление двоичных чисел

Деление можно выполнять столбиком, как в десятичной системе. При делении положительного целого числа на степень двойки также можно использовать сдвиг вправо.

Пример 1: деление на 10₂

1000₂ : 0010₂ = 0100₂

Проверка:

8₁₀ : 2₁₀ = 4₁₀
1000₂ : 0010₂ = 0100₂

Пример 2

1100₂ : 0011₂ = 0100₂

Проверка:

12₁₀ : 3₁₀ = 4₁₀
1100₂ : 0011₂ = 0100₂

Пример 3: деление с остатком

0111₂ : 0010₂ = 0011₂, остаток 1₂

Проверка:

7₁₀ : 2₁₀ = 3₁₀, остаток 1₁₀

Важно про сдвиги

Для положительных целых чисел сдвиг влево на один разряд часто соответствует умножению на 2₁₀, а сдвиг вправо - целочисленному делению на 2₁₀. Но результат зависит от размера типа, наличия знака и переполнения. Поэтому сдвиг нельзя считать универсальной заменой арифметики.

Переполнение

Представим, что для числа выделено только четыре бита. Максимальное беззнаковое значение:

1111₂ = 15₁₀

Попробуем прибавить 1₁₀:

  1111₂
+ 0001₂
=10000₂

Результату требуется пять бит. Если система сохраняет только младшие четыре бита, получится 0000₂. Такое явление называется переполнением.

Конкретная реакция программы зависит от языка, типа данных и режима проверки ошибок.

Отрицательные числа

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

Для восьми бит последовательность 11111111₂ может означать:

• 255₁₀, если тип беззнаковый;
• -1₁₀, если тип знаковый и используется дополнительный код.

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

Арифметика и битовые операции - не одно и то же

Арифметические операции работают с числовым значением целиком. Битовые операции независимо сравнивают или изменяют отдельные позиции.

Например:

0101₂ + 0011₂ = 1000₂   // арифметическое сложение: 5₁₀ + 3₁₀ = 8₁₀
0101₂ ИЛИ 0011₂ = 0111₂ // битовая операция: 5₁₀ ИЛИ 3₁₀ = 7₁₀

Результаты различаются, потому что правила операций разные.

Битовые операции

Битовое И

В результате остается 1 только в тех позициях, где оба исходных бита равны 1.

1010₂ И 1100₂ = 1000₂
0111₂ И 0011₂ = 0011₂

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

Битовое ИЛИ

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

1010₂ ИЛИ 1100₂ = 1110₂
0100₂ ИЛИ 0011₂ = 0111₂

Битовое ИЛИ можно использовать для включения выбранных битов.

Битовое XOR

В результате находится 1, если исходные биты различаются.

1010₂ XOR 1100₂ = 0110₂
0111₂ XOR 0011₂ = 0100₂

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

Битовое НЕ

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

Для четырехбитных значений:

НЕ 1010₂ = 0101₂
НЕ 0011₂ = 1100₂

Сдвиги

Сдвиг перемещает биты на заданное число позиций.

0011₂ << 1 = 0110₂   // 3₁₀ · 2₁₀ = 6₁₀
1100₂ >> 1 = 0110₂   // 12₁₀ : 2₁₀ = 6₁₀

Знаки << и >> часто используются в языках программирования для сдвига влево и вправо.

Битовые маски и флаги

Флаг - один бит, который хранит логический признак: включен режим или нет, есть ошибка или нет.

Маска - двоичное значение, в котором выбранные позиции отмечены единицами.

состояние: 10110100₂
маска:     00000100₂
результат: 00000100₂

Так как результат битового И не равен 00000000₂, выбранный бит был включен.

Другой пример:

состояние: 10110000₂
маска:     00000100₂
результат: 00000000₂

Здесь выбранный бит выключен.

Двоичная математика в роботах

У колесного робота энкодер создает импульсы при вращении колеса. Каждый новый импульс увеличивает счетчик:

0₁₀ -> 1₁₀ -> 2₁₀ -> 3₁₀ -> 4₁₀
000₂ -> 001₂ -> 010₂ -> 011₂ -> 100₂

Младший бит меняется при каждом увеличении счетчика:

0 -> 1 -> 0 -> 1 -> 0

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

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

Бит	Признак
0	моторы включены
1	линия обнаружена
2	низкий заряд
3	обнаружена ошибка

Что запомнить про двоичную математику

Идея	Короткое объяснение
1₂ + 1₂ = 10₂	возникает перенос
При вычитании возможен заем	10₂ - 1₂ = 1₂
Умножение строится из сдвигов и сложения	сдвиг влево связан с умножением на степени 2₁₀
Деление может иметь остаток	как и в десятичной системе
Ограниченное число бит может переполниться	результат требует больше разрядов
Битовые операции работают по позициям	они не равны обычной арифметике
Смысл битов зависит от формата	одни биты могут быть знаковым или беззнаковым числом

Практика

Задание 1. Сложение

Двоичный пример	Проверка в десятичной СС	Результат
0010₂ + 0001₂	2₁₀ + 1₁₀
0101₂ + 0010₂	5₁₀ + 2₁₀
0111₂ + 0001₂	7₁₀ + 1₁₀

Задание 2. Вычитание, умножение и деление

Выполните операции и проверьте их в десятичной системе:

1001₂ - 0011₂
0101₂ · 0010₂
1110₂ : 0010₂

Задание 3. Битовая маска

состояние: 10101000₂
маска:     00001000₂

Выполните битовое И и объясните, включен ли выбранный флаг.

Проверьте себя

• Почему 1₂ + 1₂ дает 10₂?
• Когда при вычитании требуется заем?
• Как умножение на 10₂ связано со сдвигом?
• Почему деление целых чисел может иметь остаток?
• Что такое переполнение?
• Чем арифметическое сложение отличается от битового ИЛИ?
• Для чего применяют битовую маску?

Ориентиры для самопроверки

Сначала ответьте без подсказки. Ответ можно считать полным, если вы:

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

Если один из пунктов объяснить не получается, найдите соответствующую главу статьи, перечитайте её и повторите ответ.

Словарь статьи

• Перенос - единица, переходящая в следующий разряд при сложении.
• Заем - получение единицы из старшего разряда при вычитании.
• Переполнение - ситуация, когда результат не помещается в выделенном количестве битов.
• Дополнительный код - распространенный способ представления отрицательных целых чисел.
• Битовая операция - операция над отдельными позициями двоичной записи.
• Маска - двоичное значение для выбора определенных битов.
• Флаг - бит, хранящий один логический признак.
• Сдвиг - перемещение битов влево или вправо.
• Энкодер - датчик, позволяющий измерять вращение или перемещение.

Связанные темы

• Двоичная система счисления - разряды и перевод чисел.
• Хранение данных в памяти - почему формат меняет смысл битов.
• Логические элементы - логические правила для состояний 0 и 1.
• Сравнение протоколов обмена - передача байтов между устройствами.

Источники

• Arduino Docs. Bit Math: https://docs.arduino.cc/learn/programming/bit-math/
• Python Documentation. Bitwise operations on integer types: https://docs.python.org/3/library/stdtypes.html#bitwise-operations-on-integer-types
• Python Documentation. Integer methods: https://docs.python.org/3/library/stdtypes.html#additional-methods-on-integer-types