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 视为 2 的幂之和： n2 = c₃₀ 2³⁰ + c₂₉ 2^{29< /sup> + ... + c₁ 21 + c₀ 20，其中每个 c< sub>i 是 0 或 1。那么您可以将乘积 n₁ n₂ 视为}

n₁ n< sub>2 =

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

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

这有点密集，但其思想是两个数字的乘积由第一个数字乘以组成第二个数字的 2 的幂，乘以第二个数字的二进制数字的值。

现在的问题是我们是否可以在不进行任何实际乘法的情况下计算这个和的项。为此，我们需要能够读取 n₂ 的二进制数字。幸运的是，我们可以通过轮班来做到这一点。特别是，假设我们从 n₂ 开始，然后只查看最后一位。那是c₀。如果我们将值向下移动一位，则最后一位是 c₀，依此类推。更一般地，在将 n₂ 的值向下移动 i 个位置后，最低位为 c_i。要读取最后一位，我们只需将值与数字 1 进行按位与。这具有二进制表示形式，除了最后一位数字之外，所有位置都为零。由于对于任何 n 0 AND n = 0，这会清除所有最高位。此外，由于 0 AND 1 = 0 和 1 AND 1 = 1，因此此操作保留数字的最后一位。

好的 - 我们现在知道我们可以读取 c_i 的值；所以呢？好消息是，我们还可以以类似的方式计算序列 n₁ 2ⁱ 的值。特别地，考虑值序列 n₁ << 0, n₁ << 1 等。任何时候进行左移，都相当于乘以 2 的幂。这意味着我们现在拥有计算上述总和所需的所有组件。这是您的原始源代码，评论了正在发生的事情：

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

看起来你的问题不是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)

好的...您看到可以使用异或运算将两个一位数字相加。使用 and 您现在可以查明是否有“进位”位，这与用笔和纸相加数字非常相似。 （到目前为止，您已经有了一个称为半加器的东西）。当您添加接下来的两位时，您还需要将进位位添加到这两位数字上。考虑到这一点，您可以获得一个全加器。您可以在维基百科上了解半加器和全加器的概念：
http://en.wikipedia.org/wiki/Adder_(电子产品)
网络上还有更多地方。
我希望这能给你一个开始。

顺便说一句，乘法与乘法非常相似。只要记住你在小学时如何用笔和纸做乘法即可。这就是这里发生的事情。只是它发生在二进制数而不是十进制数上。

Answer 3

bitwiseAdd 方法的说明：

我知道这个问题不久前就被问到了，但由于没有给出关于 bitwiseAdd 方法如何工作的完整答案，这里就是一个。

理解bitwiseAdd中封装的逻辑的关键在于加法运算与异或和与按位运算之间的关系。该关系由以下等式定义（有关该等式的数值示例，请参阅附录 1）：

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

或者更简单地说：

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

with
    and = x & y
    xor = x ^ y

您可能已经注意到该等式中有些熟悉的内容：and 和 xor< /strong> 变量与 bitwiseAdd 开头定义的变量相同。还有一个乘以 2 的操作，在 bitwiseAdd 中是在 while 循环开始时完成的。但我稍后会再谈这个。

让我也对“&”做一个简短的旁注在我们继续下一步之前，按位运算符。 该运算符基本上“捕获”应用它的位序列的交集。例如，9& 13 = 1001 & 1101 = 1001 (=9)。从这个结果中您可以看到，只有两个位序列共有的位才会被复制到结果中。由此推导出，当两个比特序列没有公共比特时，应用“&”的结果对它们产生0。 这对按位加法关系产生了重要的影响，很快就会变得清晰

现在我们遇到的问题是方程 1.2 使用了“+”运算符，而 bitwiseAdd 没有（它只使用了“^”） 、“&”和“<<”）。那么我们如何才能让等式 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 表达式在 bitwiseAdd 的 while 循环内部定义。我们还注意到出现了一个模式：方程 1.4 看起来与方程 1.2 完全一样！

因此，如果保留递归符号，则进一步递归是轻而易举的事。在这里，我们将方程 1.2 再递归两次：

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

现在应该突出显示 bitwiseAdd 中的“temp”变量的作用：temp 允许从一个递归级别传递到下一个递归级别。

我们还注意到所有这些方程中都乘以二。如前所述，此乘法是在 bitwiseAdd 中的 while 循环开始时使用 and <<= 1 语句完成的。这种乘法会对下一个递归阶段产生影响，因为 and[i] 中的位与前一阶段的 and[i] 中的位不同（如果您还记得我之前关于 '&' 所做的小旁注）运算符，您现在可能知道这是怎么回事了）。

方程 1.4 的一般形式现在变为：

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

最终：

那么这个递归业务到底什么时候结束呢？

答案：当等式1.5的and[x]表达式中的两个比特序列之间的交集返回0时结束。当 while 循环条件变为 false 时，bitwiseAdd 中的等效操作就会发生。此时方程 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)

为了得到这个结果，我们只需采用上面等式 1.2 的 2* 和 + xor 部分，并应用等式给出的加法/按位操作数关系 1.1 到它。这被证明如下：

如果

    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)

用方程 1.2 的 and 和 xor 变量的定义来简化它给出方程 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 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);
}