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 1和n 2。然后，您可以将n1视为两个幂的和：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

这有点密集，但是我们的想法是，两个数字的乘积由第一个数字乘以组成第二个数字的两个数字的乘方乘以第二个数字的二进制数字的值得出。

现在的问题是，我们是否可以在不进行任何实际乘法的情况下计算该和项。为了做到这一点，我们将需要能够读取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);
}

希望这可以帮助！