java - 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< sub>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 的值。这有一个二进制表示，除最后一位外，其他地方都是零。由于 0 AND n = 0 对于任何 n，这将清除所有最高位。此外，由于 0 AND 1 = 0 和 1 AND 1 = 1，此操作保留数字的最后一位。

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

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

希望这对您有所帮助!