15

我有做乘法和加法的方法，但我无法理解它们。它们都来自外部网站，而不是我自己的：

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 中的按位运算。

4

4 回答 4

26

让我们从查看乘法代码开始。这个想法实际上非常聪明。假设您有 n 1和 n 2以二进制形式编写。然后您可以将 n1 视为 2 的幂的和：n2 = c 30 2 30 + c 29 2 29 + ... + c 1 2 1 + c 0 2 0，其中每个 c i为 0 或 1。然后您可以将乘积 n 1 n 2视为

n 1 n 2 =

n 1 (c 30 2 30 + c 29 2 29 + ... + c 1 2 1 + c 0 2 0 ) =

n 1 c 30 2 30 + n 1 c 29 2 29 + ... + n 1 c 1 2 1 + n 1 c 0 2 0

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

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

好的 - 我们现在知道我们可以读取 c i的值；所以呢？好消息是我们也可以用类似的方式计算序列 n 1 2 i的值。特别是，考虑 n 1 << 0、n 1 << 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);
}

希望这可以帮助！

于 2011-02-04T06:46:43.897 回答
6

看起来你的问题不是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 操作添加两个一位数。使用 an ，您现在可以确定是否有“进位”位，这与用纸笔加数字非常相似。（到目前为止，你有一个叫做 Half-Adder 的东西）。当您添加接下来的两位时，您还需要将进位位添加到这两位数。考虑到这一点，您可以获得全加器。您可以在 Wikipedia 上阅读有关半加器和全加器的概念： http ://en.wikipedia.org/wiki/Adder_(electronics ) 以及网络上的更多地方。我希望这能给你一个开始。

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

于 2011-02-04T06:39:45.790 回答
6

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变量与在 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]是什么时，这种联系变得更加明显：它们与在bitwiseAdd中的 while 循环内定义的and和xor表达式是相同的表达式。我们还注意到出现了一种模式：方程 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'
于 2012-11-24T01:22:18.153 回答
0

这是乘法的另一种方法

/**
 * 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);
}
于 2015-10-09T09:04:45.987 回答