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

Question

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

public static void bitwiseMultiply(int n1, int n2) {
    int a = n1, b = n2, result=0;
    while (b != 0) // Iterate the loop till b==0
    {
        if ((b & 01) != 0) // Logical ANDing of the value of b with 01
        {
            result = result + a; // Update the result with the new value of a.
        }
        a <<= 1;              // Left shifting the value contained in 'a' by 1.
        b >>= 1;             // Right shifting the value contained in 'b' by 1.
    }
    System.out.println(result);
}

public static void bitwiseAdd(int n1, int n2) {
    int x = n1, y = n2;
    int xor, and, temp;
    and = x & y;
    xor = x ^ y;

    while (and != 0) {
        and <<= 1;
        temp = xor ^ and;
        and &= xor;
        xor = temp;
    }
    System.out.println(xor);
}

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

То, что я, возможно, ищу, это попытаться понять, как это работает (возможно, математическая основа?).

Редактировать: Это не домашняя работа, я просто пытаюсь изучить побитовые операции в Java.

Answer 1

Давайте начнем с просмотра кода умножения. Идея на самом деле довольно умная. Предположим, что у вас есть n ₁ и n ₂ , записанные в двоичном виде. Тогда вы можете думать о n1 как о сумме двух степеней: n2 = c ₃₀ 2 ³⁰ + c ₂₉ 2 ²⁹ + ... + c ₁ 2 ¹ + c ₀ 2 ⁰ , где каждый c _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 ₀ и т. Д. В более общем смысле, после смещения значения n ₂ вниз на i позиции, младший бит будет с _я . Чтобы прочитать самый последний бит, мы можем просто поразрядно И значение с номером 1. Это имеет двоичное представление, которое является нулем везде, кроме последней цифры. Поскольку 0 И n = 0 для любого n, это очищает все старшие биты. Более того, поскольку 0 И 1 = 0 и 1 И 1 = 1, эта операция сохраняет последний бит числа.

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

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);
}

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

Answer 2

ОБЪЯСНЕНИЕ ПОБОЧНОГО ДОПОЛНИТЕЛЬНОГО МЕТОДА:

Я знаю, что этот вопрос был задан некоторое время назад, но поскольку полный ответ о том, как работает метод 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 использует оператор «+», а bitwiseAdd - нет (оно использует только «^», «&» и «<<»). Так как же заставить «+» в уравнении 1.2 как-то исчезнуть? Ответ: «заставляя» выражения <strong>и возвращать 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. Эта связь становится еще более очевидной, если учесть, что и [1] и xor [1] : это те же выражения, что и и и xor выражения определены INSIDE цикл 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 с использованием операторов и << = 1 </strong>. Это умножение имеет последствия на следующем этапе рекурсии, поскольку биты в и [i] отличаются от битов в и [i] предыдущего этапа (и если вы вспомните небольшую заметку, которую я сделал ранее об операторе '&' вы, наверное, видите, куда это идет сейчас).

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

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

Finaly:

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

Ответ: заканчивается, когда пересечение между двумя битовыми последовательностями в выражении и [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) говорит, что

если

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. Это демонстрируется следующим образом:

если

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

* * +1136 затем * +1137 *

     [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'

Answer 3

Похоже, ваша проблема не в 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.С помощью и вы теперь можете узнать, есть ли у вас бит «переноса», который очень похож на добавление чисел ручкой и бумагой.(До этого момента у вас есть что-то, что называется Half-Adder).Когда вы добавляете следующие два бита, вам также необходимо добавить бит переноса к этим двум цифрам.Принимая это во внимание, вы можете получить полный сумматор.Вы можете прочитать о концепциях Half-Adders и Full-Adders в Википедии: http://en.wikipedia.org/wiki/Adder_(electronics) и многих других местах в Интернете.Я надеюсь, что это даст вам начало.

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

Answer 4

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

/**
 * 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);
}