按位乘法并在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 ²⁹ + ... + 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 ⁰

这有点密集,但是这个想法是两个数字的乘积由第一个数字乘以构成第二个数字的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)

好的......您看到可以使用xor操作添加两个一位数字.使用a,您现在可以找出是否有"进位"位,这与使用笔和纸添加数字非常相似.(到目前为止,你有一个叫做半加法器的东西).当您添加接下来的两位时,您还需要将进位位添加到这两位数.考虑到这一点,您可以获得Full-Adder.您可以在维基百科上阅读有关半加器和全加器的概念:http://en.wikipedia.org/wiki/Adder_ (electronics )以及网络上的更多地方.我希望这能给你一个开始.

通过乘法,它非常相似.只记得你在小学里如何用笔和纸成倍增长.多数民众赞成在这里发生的事情.只是它发生了二进制数而不是十进制数.

Answer 3

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

您可能已经注意到此等式中熟悉的内容:and和xor变量与bitwiseAdd开头定义的变量相同.还有一个乘以2,在bitwiseAdd中,在while循环的开始处完成.但我稍后会回过头来.

在进一步讨论之前,让我也快速注意一下'&'位运算符. 该运算符基本上"捕获"应用它的位序列的交集.例如,9&13 = 1001&1101 = 1001(= 9).从该结果可以看出,只有两个位序列共有的那些位被复制到结果中.由此得出,当两个比特序列没有公共比特时,对它们应用'&'的结果产生0. 这对加法 - 按位关系有重要影响,很快就会清楚

现在我们遇到的问题是方程式1.2使用'+'运算符而bitwiseAdd不使用(它只使用'^','&'和'<<').那么我们如何使方程式1.2中的"+"以某种方式消失呢？答案:通过'强制' 和表达式返回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在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允许从一个递归级别传递到下一个递归级别.

我们还注意到在所有这些方程中乘以2.如前所述,这个乘法是在bitwiseAdd的while循环开始时使用和<< = 1语句完成的.这个乘法在下一个递归阶段有一个结果,因为和[i]中的位不同于前一阶段和[i]中的位(如果你还记得我之前提到的关于'&'运算符的小边注释你可能会看到现在的情况).

公式1.4的一般形式现在变为:

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

FINALY:

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

答案:当方程式1.5的[x]表达式中的两个位序列之间的交点返回0时,它结束.当while循环条件变为false时,在bitwiseAdd中等效.此时,等式1.5变为:

    x + y = xor[x]      (1.6)

这就解释了为什么在bitwiseAdd中我们只返回xor!

我们完成了!一个非常聪明的代码,这个bitwiseAdd我必须说:)

我希望这有帮助

附录:

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 的和和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'