Побитовое умножение и сложение в Java

Начнем с поиска кода умножения. Идея на самом деле очень умная. Предположим, что у вас есть n₁ и n₂, записанные в двоичном формате. Тогда вы можете представить n1 как сумму степеней двойки: n2 = c₃₀ 2³⁰ + c₂₉ 2^{29< /sup> + ... + c₁ 21 + c₀ 20, где каждый c< sub>i равно 0 или 1. Тогда вы можете думать о произведении n₁ n₂ как}

n₁ n₂ =

n₁ (c₃₀ 2³⁰ + c₂₉ 2²⁹ + .. . + c₁ 2¹ + c₀ 2⁰) =

n₁ c₃₀ 2³⁰ + n₁ c₂₉ 2 ²⁹ + ... + n₁ c₁ 2¹ + n₁ c₀ 2⁰

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

Теперь вопрос состоит в том, можем ли мы вычислить члены этой суммы, не производя никаких реальных умножений. Для этого нам нужно иметь возможность читать двоичные цифры числа n₂. К счастью, мы можем сделать это, используя сдвиги. В частности, предположим, что мы начинаем с n₂, а затем просто смотрим на последний бит. Это c₀. Если мы затем сдвинем значение вниз на одну позицию, тогда последним битом будет c₀ и т. д. В более общем случае, после сдвига значения n₂ вниз на i позиций, младший бит будет c_i. Чтобы прочитать самый последний бит, мы можем просто выполнить побитовое И значение с числом 1. Это имеет двоичное представление, которое равно нулю везде, кроме последней цифры. Поскольку 0 И n = 0 для любого n, это очищает все самые верхние биты. Более того, поскольку 0 И 1 = 0, а 1 И 1 = 1, эта операция сохраняет последний бит числа.

Хорошо, теперь мы знаем, что можем читать значения c_i; И что? Что ж, хорошая новость заключается в том, что мы также можем вычислить значения ряда n₁ 2ⁱ аналогичным образом. В частности, рассмотрим последовательность значений n₁ ‹‹ 0, n₁ ‹‹ 1 и т. д. Каждый раз, когда вы выполняете битовый сдвиг влево, это эквивалентно умножению в степени двойки. Это означает, что теперь у нас есть все компоненты, необходимые для вычисления приведенной выше суммы. Вот ваш оригинальный исходный код с комментариями о том, что происходит:

public static void bitwiseMultiply(int n1, int n2) {
    /* This value will hold n1 * 2^i for varying values of i.  It will
     * start off holding n1 * 2^0 = n1, and after each iteration will 
     * be updated to hold the next term in the sequence.
     */
    int a = n1;

    /* This value will be used to read the individual bits out of n2.
     * We'll use the shifting trick to read the bits and will maintain
     * the invariant that after i iterations, b is equal to n2 >> i.
     */
    int b = n2;

    /* This value will hold the sum of the terms so far. */
    int result = 0;

    /* Continuously loop over more and more bits of n2 until we've
     * consumed the last of them.  Since after i iterations of the
     * loop b = n2 >> i, this only reaches zero once we've used up
     * all the bits of the original value of n2.
     */
    while (b != 0)
    {
        /* Using the bitwise AND trick, determine whether the ith 
         * bit of b is a zero or one.  If it's a zero, then the
         * current term in our sum is zero and we don't do anything.
         * Otherwise, then we should add n1 * 2^i.
         */
        if ((b & 1) != 0)
        {
            /* Recall that a = n1 * 2^i at this point, so we're adding
             * in the next term in the sum.
             */
            result = result + a;
        }

        /* To maintain that a = n1 * 2^i after i iterations, scale it
         * by a factor of two by left shifting one position.
         */
        a <<= 1;

        /* To maintain that b = n2 >> i after i iterations, shift it
         * one spot over.
         */
        b >>>= 1;
    }

    System.out.println(result);
}

Надеюсь это поможет!

Похоже, ваша проблема не в java, а просто в расчетах с двоичными числами. Начало простого: (все числа двоичные:)

0 + 0 = 0   # 0 xor 0 = 0
0 + 1 = 1   # 0 xor 1 = 1
1 + 0 = 1   # 1 xor 0 = 1
1 + 1 = 10  # 1 xor 1 = 0 ( read 1 + 1 = 10 as 1 + 1 = 0 and 1 carry)

Хорошо... Вы видите, что вы можете сложить два однозначных числа, используя операцию xor. Теперь с помощью and вы можете узнать, есть ли у вас бит переноса, что очень похоже на сложение чисел с помощью ручки и бумаги. (До этого момента у вас было что-то под названием Half-Adder). Когда вы добавляете следующие два бита, вам также нужно добавить бит переноса к этим двум цифрам. С учетом этого можно получить Full-Adder. Вы можете прочитать о концепциях Half-Adders и Full-Adders в Википедии: http://en.wikipedia.org/wiki/Adder_(electronics) И многие другие места в Интернете. Надеюсь, это послужит вам началом.

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

ОБЪЯСНЕНИЕ МЕТОДА bitwiseAdd:

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

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

x + y = 2 * (x&y)+(x^y)     (1.1)

Или проще:

x + y = 2 * and + xor       (1.2)

with
    and = x & y
    xor = x ^ y

Возможно, вы заметили что-то знакомое в этом уравнении: переменные и и xor такие же, как те, что определены в начале bitwiseAdd. Также есть умножение на два, которое в bitwiseAdd делается в начале цикла while. Но я вернусь к этому позже.

Позвольте мне также сделать небольшую заметку о побитовом операторе '&', прежде чем мы продолжим. Этот оператор в основном "захватывает" пересечение битовых последовательностей, к которым он применяется. Например, 9 и 13 = 1001 и 1101 = 1001 (=9). Из этого результата видно, что в результат копируются только те биты, которые являются общими для обеих битовых последовательностей. Из этого следует, что когда две битовые последовательности не имеют общего бита, результат применения к ним '&' дает 0. Это имеет важное значение для побитового отношения сложения, которое скоро станет ясно

Проблема в том, что в уравнении 1.2 используется оператор «+», тогда как в побитовом добавлении его нет (используются только «^», «&» и «‹‹»). Так как же сделать так, чтобы «+» в уравнении 1.2 каким-то образом исчез? Ответ: «заставив» выражение and возвращать 0. Мы делаем это с помощью рекурсии.

Чтобы продемонстрировать это, я собираюсь повторить уравнение 1.2 один раз (этот шаг может быть немного сложным поначалу, но при необходимости в приложении 2 есть подробный пошаговый результат):

x + y = 2*(2*and & xor) + (2*and ^ xor)     (1.3)

Или проще:

x + y = 2 * and[1] + xor[1]     (1.4)

with
    and[1] = 2*and & xor,
    xor[1] = 2*and ^ xor,
    [1] meaning 'recursed one time'

Здесь следует отметить несколько интересных вещей. Во-первых, вы заметили, что концепция рекурсии звучит близко к циклу, как, например, в BitwiseAdd. Эта связь становится еще более очевидной, если учесть, что такое and[1] и xor[1]: это те же выражения, что и and и выражения xor определяют ВНУТРИ цикл while в bitwiseAdd. Мы также отмечаем, что возникает закономерность: уравнение 1.4 выглядит точно так же, как уравнение 1.2!

В результате этого выполнение дальнейших рекурсий становится проще простого, если вы сохраняете рекурсивную нотацию. Здесь мы повторяем уравнение 1.2 еще два раза:

x + y = 2 * and[2] + xor[2]
x + y = 2 * and[3] + xor[3]

Теперь это должно подчеркнуть роль переменной temp в bitwiseAdd: temp позволяет переходить с одного уровня рекурсии на другой.

Мы также замечаем умножение на два во всех этих уравнениях. Как упоминалось ранее, это умножение выполняется в начале цикла while в bitwiseAdd с использованием оператора and ‹‹= 1. Это умножение имеет последствия на следующем этапе рекурсии, поскольку биты в and[i] отличаются от битов в and[i] на предыдущем этапе (и если вы помните маленькое примечание, которое я сделал ранее об операторе '&' вы, вероятно, видите, к чему это идет сейчас).

Общая форма уравнения 1.4 теперь принимает вид:

x + y = 2 * and[x] + xor[x]     (1.5)
with x the nth recursion

НАКОНЕЦ:

Так когда именно эта рекурсия закончится?

Ответ: он заканчивается, когда пересечение двух последовательностей битов в выражении и[x] уравнения 1.5 возвращает 0. Эквивалент этого в bitwiseAdd происходит, когда условие цикла while становится ложным. В этот момент уравнение 1.5 принимает вид:

    x + y = xor[x]      (1.6)

И это объясняет, почему в bitwiseAdd мы возвращаем xor только в конце!

И мы закончили! Должен сказать, довольно умный кусок кода.

надеюсь это помогло

ПРИЛОЖЕНИЕ:

1) Числовой пример уравнения 1.1

уравнение 1.1 говорит:

    x + y = 2(x&y)+(x^y)        (1.1)

Чтобы проверить это утверждение, можно взять простой пример, скажем, сложить вместе 9 и 13. Шаги показаны ниже (побитовые представления указаны в скобках):

У нас есть

    x = 9 (1001)
    y = 13  (1101)

И

    x + y = 9 + 13 = 22
    x & y = 9 & 13 = 9 (1001 & 1101 = 1001)
    x ^ y = 9^13 = 4 (1001 ^ 1101 = 0100)

подставляя это обратно в уравнение 1.1, мы находим:

    9 + 13 = 2 * 9 + 4 = 22 et voila!

2) Демонстрация первого шага рекурсии

Первое уравнение рекурсии в презентации (уравнение 1.3) говорит, что

if

x + y = 2 * and + xor           (equation 1.2)

потом

x + y = 2*(2*and & xor) + (2*and ^ xor)     (equation 1.3)

Чтобы получить этот результат, мы просто взяли 2* и + xor часть уравнения 1.2 выше и применили к ней отношение сложения/побитовых операндов, заданное уравнением 1.1. Это демонстрируется следующим образом:

if

    x + y = 2(x&y) + (x^y)      (equation 1.1)

потом

     [2(x&y)] + (x^y)     =      2 ([2(x&y)] & (x^y)) + ([2(x&y)] ^ (x^y))
(left side of equation 1.1)  (after applying the addition/bitwise operands relationship)

Упрощение этого с помощью определений переменных и и xor уравнения 1.2 дает результат уравнения 1.3:

[2(x&y)] + (x^y) = 2*(2*and & xor) + (2*and ^ xor)

with
    and = x&y
    xor = x^y

И использование того же упрощения дает результат уравнения 1.4:

2*(2*and & xor) + (2*and ^ xor) = 2*and[1] + xor[1]

with
    and[1] = 2*and & xor
    xor[1] = 2*and ^ xor
    [1] meaning 'recursed one time'

Вот еще один подход к умножению

/**
 * Multiplication of binary numbers without using '*' operator
 * uses bitwise Shifting/Anding
 *
 * @param n1
 * @param n2
 */
public static void multiply(int n1, int n2) {
    int temp, i = 0, result = 0;

    while (n2 != 0) {
        if ((n2 & 1) == 1) {
            temp = n1;

            // result += (temp>>=(1/i)); // To do it only using Right shift
            result += (temp<<=i); // Left shift (temp * 2^i)
        }
        n2 >>= 1;   // Right shift n2 by 1.
        i++;
    }

    System.out.println(result);
}