按位乘法和加法在Java中 [英] Bitwise Multiply and Add in Java

问题描述

我有两者都做乘法和加法的方法，但我只是不能让我的头周围。他们两人都是从外部网站，而不是我自己的：

I have the methods that do both the multiplication and addition, but I'm just not able to get my head around them. Both of them are from external websites and not my own:

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

我试着做了一步一步的调试，但它确实没有太大的意义对我来说，虽然它的工作原理。

I tried doing a step-by-step debug, but it really didn't make much sense to me, though it works.

我正在寻找可能的是，试图理解它是如何工作的（数学基础吧？）。

What I'm possibly looking for is to try and understand how this works (the mathematical basis perhaps?).

编辑：这不是功课，我只是想在Java中学习位运算

This is not homework, I'm just trying to learn bitwise operations in Java.

推荐答案

让我们先来看看乘法code。这个想法其实是pretty聪明。假设您有n个 ₁ 和N ₂ 写成二进制文件。然后，你可以认为n1的作为两个大国的总和：N2 = C ₃₀ 2 ³⁰ + C ₂₉ 2 ²⁹ + ... + C ₁ 2 ¹ + C ₀ 2 ⁰ ，其中每个C <子> I 为0或1。然后你能想到的产品为n ₁ N ₂ 为

Let's begin by looking the multiplication code. The idea is actually pretty clever. Suppose that you have n₁ and n₂ written in binary. Then you can think of n1 as a sum of powers of two: n2 = c₃₀ 2³⁰ + c₂₉ 2²⁹ + ... + c₁ 2¹ + c₀ 2⁰, where each c_i is either 0 or 1. Then you can think of the product n₁ n₂ as

N ₁ N ₂ =

N ₁ （C ₃₀ 2 ³⁰ + C ₂₉ 2 ²⁹ + ... + C ₁ 2 ¹ + C ₀ 2 ⁰ ）=

n₁ (c₃₀ 2³⁰ + c₂₉ 2²⁹ + ... + c₁ 2¹ + c₀ 2⁰) =

N ₁ C ₃₀ 2 ³⁰ + N ₁ C ₂₉ 2 ²⁹ + ... + N ₁ C ₁ 2 ¹ + N ₁ ç ₀ 2 ⁰

n₁ c₃₀ 2³⁰ + n₁ c₂₉ 2²⁹ + ... + n₁ c₁ 2¹ + n₁ c₀ 2⁰

这是有点致密，但这个想法是，这两个数字的乘积是通过乘以2构成第二数，倍的第二数目的二进制数位的值的权力的第一个数字给出。

This is a bit dense, but the idea is that the product of the two numbers is given by the first number multiplied by the powers of two making up the second number, times the value of the binary digits of the second number.

现在的问题是，我们是否可以计算这笔款项的条款没有做任何实际的乘法。为了做到这一点，我们将需要能够读取n ₂ 的二进制数字。幸运的是，我们可以通过移位做到这一点。特别是，假设我们开始有n ₂ ，然后就看最后一位。那公司的C ₀ 。如果我们那么该值向下移动一个位置，那么最后一位为c ₀ 等更一般地，通过我的位置移动n ₂ 的价值下降之后，最低位将是c _I 。要阅读的最后一点，我们只要按位与数字1的值，这有一个二进制重新presentation到处都有是零，除了最后一位。由于对任意n 0和n = 0，这将清除所有的最顶层位。此外，由于在0和1 = 0和1，1 = 1，该操作preserves数的最后一个比特。

The question now is whether we can compute the terms of this sum without doing any actual multiplications. In order to do so, we're going to need to be able to read the binary digits of n₂. Fortunately, we can do this using shifts. In particular, suppose we start off with n₂ and then just look at the last bit. That's c₀. If we then shift the value down one position, then the last bit is c₀, etc. More generally, after shifting the value of n₂ down by i positions, the lowest bit will be c_i. To read the very last bit, we can just bitwise AND the value with the number 1. This has a binary representation that's zero everywhere except the last digit. Since 0 AND n = 0 for any n, this clears all the topmost bits. Moreover, since 0 AND 1 = 0 and 1 AND 1 = 1, this operation preserves the last bit of the number.

好了 - 现在我们知道我们能够READ C _的值I ;所以呢？好了，好消息是，我们还可以计算以类似的方式在N系列 ₁ 2 ^我的值。特别是，考虑值序列ñ ₁ ＆LT;＆LT; 0，N ₁ ＆LT;＆LT; 1等无论何时做一个左位移，它相当于由二的幂相乘。这意味着我们现在拥有所有我们需要计算上述款项的组件。这里的原始源$ C ​​$ C，有评论说这是怎么回事：

Okay - we now know that we can read the values of c_i; so what? Well, the good news is that we also can compute the values of the series n₁ 2ⁱ in a similar fashion. In particular, consider the sequence of values n₁ << 0, n₁ << 1, etc. Any time you do a left bit-shift, it's equivalent to multiplying by a power of two. This means that we now have all the components we need to compute the above sum. Here's your original source code, commented with what's going on:

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

希望这有助于！

这篇关于按位乘法和加法在Java中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！