按位乘法并在 Java 中添加

java bit-manipulation bitwise-operators addition multiplication

2022-09-03 09:26:28

我有同时进行乘法和加法的方法，但我只是无法弄清楚它们。它们都来自外部网站，而不是我自己的网站：

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中的按位操作。

答案 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⁰

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

现在的问题是，我们是否可以在不进行任何实际乘法的情况下计算此总和的项。为了做到这一点，我们需要能够读取n₂的二进制数字。幸运的是，我们可以使用班次来做到这一点。特别是，假设我们从n₂开始，然后只看最后一点。这是 c₀。如果我们然后将值向下移动一个位置，则最后一位是c₀，依此类推。更一般地说，在将n₂的值向下移动i个位置后，最低位将是c_i。要读取最后一位，我们可以按位读取数字为1的值。这具有一个二进制表示形式，除最后一个数字外，其他位置均为零。由于 0 和 n = 0 表示任何 n，这将清除所有最上面的位。此外，由于 0 和 1 = 0 和 1 和 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);
}

希望这有帮助！

答案 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)

还行。。。您会看到可以使用异或运算添加两个一位数的数字。有了，你现在可以知道你是否有一个“携带”位，这与用笔和纸加数字非常相似。（到目前为止，您有一种叫做半加法器的东西）。当您添加接下来的两位时，您还需要将携带位添加到这两位数字。考虑到这一点，你可以得到一个完整的加法器。您可以在维基百科上阅读有关Half-Adders和Full-Adders的概念：http://en.wikipedia.org/wiki/Adder_（电子）以及网络上的更多地方。我希望这能给你一个开始。

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