Сложение — обычная математическая операция, но знаете ли вы, что она представляет в двоичном виде? Вы узнаете это в этой статье.

Вопреки тому, что вы могли подумать, знак + не обязателен для выполнения сложения между целыми числами. Фактически, бинарные операторы ‹‹, ››, &, | и ^ достаточно для выполнения этой математической операции, и я покажу вам, как их использовать.

Чтобы сделать объяснения как можно более понятными, я закодирую функцию adder в Rust, которая позволяет выполнять побитовые операции над целочисленными типами. Но даже если вы не знаете Rust, у вас не возникнет проблем с пониманием туториала!

Понимание 32-битной целочисленной двоичной структуры без знака

fn adder(a: u32, b: u32) -> u32;

Как видно из приведенного выше прототипа функции, мы хотим добавить 32-битные целые числа без знака и вернуть тот же тип. Таким образом, каждое десятичное число состоит из 32 битов (1 или 0), представляющих степень числа 2.

Например, 1011(2) равно 1 * 2⁰ + 1 * 2¹ + 0 * 2² + 1 * 2³ = 1 + 2 + 0 + 8 = 11. Мы начинаем с самого правого бита, а затем добавляем последовательные результаты, чтобы получить окончательное значение в десятичном виде. Эта концепция будет полезна для урока.

Реализация бинарной системы сложения

Возьмем 29 и 9. Их двоичные представления: 011101(2) и 001001(2). Теперь мы хотим добавить их, но без оператора +!

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

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

Результат — это двоичная запись сложения, которое мы хотим выполнить, т. е. 38. Чтобы вычислить его, мы должны сделать побитовые сложения, начиная с самых правых битов, используя правила Я дал вам ранее.

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

Формула для получения бинарного результата

Чтобы получить результат, мы будем использовать оператор ^ (XOR или исключающее ИЛИ). a ^ b возвращает 1, если только одна из двух переменных равна 1. В противном случае возвращается 0. Но в нашем случае нужно учитывать дополнительную переменную: carry немного больше.

Бит переноса в начале установлен в 0. Каждый раз, когда сложение двух целых битов и бита переноса больше или равно 2, бит переноса устанавливается в 1. Затем он будет использоваться для добавления следующего бита.

Таким образом, формула для получения результирующего битового значения для каждого побитового сложения выглядит следующим образом: binary_result = a_bit ^ b_bit ^ Carry_over. Это дает тот же результат, что и в таблице двоичного сложения.

Чтобы реализовать это в Rust, нам нужно создать цикл для применения операции XOR между каждым из 32 бит. Вот следующий эквивалент кода:

fn adder(a: u32, b: u32) -> u32 {
    let mut result = 0;
    let mut carry_over = 0;

    for i in 0..32 {
        // Formula to get the i-th bit of the first number, from the right.
        let a_bit = a >> i & 1;
        // Formula to get the i-th bit of the second number, from the right.
        let b_bit = b >> i & 1;
        // Binary result that will be stored in the total number called result
        let binary_result = a_bit ^ b_bit ^ carry_over;
    }
}

Формула для переноса

Как вы можете понять с помощью правил двоичного сложения, перенос будет равен 1, только если хотя бы 2 бита из 3 (первый числовой бит, второй числовой бит и текущий бит переноса) равны 1.

Мы можем легко представить ситуацию с помощью | оператор (ИЛИ). Этот оператор возвращает 1, если хотя бы одна из переменных равна 1. В противном случае он возвращает 0. Вот реализация:

carry_over = (a_bit & b_bit) | (a_bit & carry_over) | (b_bit & carry_over);

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

Окончательный результат — 100110(2), что равно 38. А 29 + 9 — это действительно 38!

Установка битов переменной результата

Рассчитать перенос и результат вручную очень просто. Но как установить биты переменной result на каждой итерации в нашем коде?

Еще раз побитовые операторы помогут нам решить эту проблему. Оператор ИЛИ (|) идеально подходит для установки битов в определенное значение. На самом деле, независимо от того, какое битовое значение уже сохранено в результате, правильное новое значение будет назначено.

На самом деле 1 остается 1 во всех случаях, а 0 становится 1, если второй операнд равен 1, в противном случае он остается 0:

  • 0 | 0 = 0
  • 1 | 0 = 1, 0 | 1 = 1, 1 | 1 = 1

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

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

fn adder(a: u32, b: u32) -> u32 {
    let mut result = 0;
    let mut carry_over = 0;

    for i in 0..32 {
        // Formula to get the i-th bit of the first number, from the right.
        let a_bit = a >> i & 1;
        // Formula to get the i-th bit of the second number, from the right.
        let b_bit = b >> i & 1;
        // Binary result that will be stored in the total number called result
        let binary_result = a_bit ^ b_bit ^ carry_over;

        carry_over = (a_bit & b_bit) | (a_bit & carry_over) | (b_bit & carry_over);
        // If binary_pos is 0, it doesn't do anything. Otherwise, it set the correct bit to 1.
        result |= binary_result << i;
    }
    result
}

Это четкое и короткое решение для добавления целых чисел без использования знака плюс. Удобно понять концепцию побитового сложения без каких-либо затруднений.

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

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

Понравилась ли вам эта статья? Вы можете сообщить мне об этом разными способами:

  • Похлопайте статье.
  • Напишите, что вы думаете о моей истории.
  • Подписаться на мой аккаунт.

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