如何使用位运算符执行乘法操作？

Question

我正在解决一个问题，除了最后一步，我已经解决了所有问题 - 我不确定如何使用位运算符进行乘法：

0*8 = 0

1*8 = 8

2*8 = 16 

3*8 = 24 

4*8 = 32

您能推荐一种解决这个问题的方法吗？

- James Raitsev

Answer 1

要将某个值乘以2的N次方（即2^N），将其位移N次到左侧。

0000 0001 = 1 

times 4 = (2^2 => N = 2) = 2 bit shift : 0000 0100 = 4

times 8 = (2^3 -> N = 3) = 3 bit shift : 0010 0000 = 32

将其右移以进行除法运算。

位是整个的1或0 - 你不能只移动部分位数，因此如果你要乘上的数字不能被N的整数因子整除，则会出现不完整的值。

since: 17 = 16  + 1 
thus:  17 = 2^4 + 1

therefore: x * 17 = (x * 16) + x in other words 17 x's  

因此，要乘以17，您需要将数字向左移4位，然后再加上原始数字：

==> x * 17 = (x * 16) + x 
==> x * 17 = (x * 2^4) + x 
==> x * 17 = (x shifted to left by 4 bits) + x 

so let x = 3 = 0000 0011 

times 16 = (2^4 => N = 4) = 4 bit shift : 0011 0000 = 48

plus the x (0000 0011)

例如。

    0011 0000  (48)  
+   0000 0011   (3)
=============
    0011 0011  (51)

编辑：更新原回答。 Charles Petzold 写了一本名为"Code"的绝妙书籍，它会以最简单易懂的方式解释这些内容和更多内容。我强烈推荐阅读。

- Preet Sangha

---

没错，但这并不完全相同。如果你想计算3*17怎么办？ - James Raitsev

Answer 2

在没有乘法指令的情况下，要相乘两个二进制编码的数。 通过迭代加法来达到乘积是很简单的。

unsigned int mult(x, y)
unsigned int x, y;
{
    unsigned int reg = 0;

    while(y--)
        reg += x;
    return reg;
}

通过使用位运算，可以利用数据编码的特征。 如前所述，位移相当于乘以二。 利用这一点，可以在二的幂上使用加法器。

// multiply two numbers with bit operations

unsigned int mult(x, y)
unsigned int x, y;
{
    unsigned int reg = 0;

    while (y != 0)
    {
        if (y & 1)
        {
            reg += x;
        }
        x <<= 1;
        y >>= 1;
    }
    return reg;
}

- user2035522

---

什么编程语言？C？ - Peter Mortensen

好的，OP已经离开了建筑物：“上次出现是十年前”。 - Peter Mortensen

Answer 3

您需要将被乘数分解为2的幂次方。
3*17 = 3*(16+1) = 3*16 + 3*1 ... = 0011b << 4 + 0011b

- epic_fil

---

如果使用这种方法，这难道不意味着将数字乘以(2^n)-1会对处理器产生最多的工作量吗？ - user4531029

有人可能会问如何以简单的方式获取2的幂次方...这就是 https://dev59.com/OnA65IYBdhLWcg3wnQBt#28158393 所做的...因此，给出的答案为：317 = ??? => 17 = b10001 = 161 + 80 + 40 +20 +11 => 317 = 113 + 023+043+083+1163（乘以2的幂次方很容易：向左移动'power'次，简单地说就是添加一个零）= 13 + 13222*2 = b11 + b110000 = b110011 = 3 + 48 = 51 - WiRa

Answer 4

public static int multi(int x, int y){
        boolean neg = false;
        if(x < 0 && y >= 0){
            x = -x;
            neg = true;
        }
        else if(y < 0 && x >= 0){
            y = -y;
            neg = true;
        }else if( x < 0 && y < 0){
            x = -x;
            y = -y;
        }

        int res = 0;
        while(y!=0){
            if((y & 1) == 1) res += x;
            x <<= 1;
            y >>= 1;
        }
        return neg ? (-res) : res;
    }

- Algorithmatic

---

什么编程语言？Java？ - Peter Mortensen

Answer 5

我认为这应该是一个左移操作。8等于2的3次方，因此向左移动3位：

2 << 3 = 8

- Jeff Ogata

---

难道不应该是2 << 3 = 16吗？因为2的二进制表示是00000010，所以如果你将数字2左移三次，你会得到00010000 = 16（而不是8）。 - Bitcoin Cash - ADA enthusiast

Answer 6

使用位运算符可以降低时间复杂度。

在C++中：

#include<iostream>
using name space std;

int main(){
   int a, b, res = 0;           // read the elements
   cin>>a>>b;

   // find the small number to reduce the iterations

   small = (a<b)?a:b;           // small number using ternary operator
   big = (small^a)?a:b;         // big number using bitwise XOR operator

   while(small > 0)
   {
      if(small & 1)
      {
         res += big;
      }
      big = big << 1;           // it increases the number << is big * (2 power of big)
      small = small >> 1;       // it decreases the number >> is small / (2 power of small)
   }
   cout<<res;
}

在Python中：

a = int(input())
b = int(input())
res = 0

small = a if(a < b) else b
big  = a if(small ^ a) else b

def multiplication(small, big):
    res = 0
    while small > 0:
        if small & 1:
            res += big
        big = big << 1
        small = small >> 1

        return res

 answer = multiplication(small, big)
 print(answer)

- Sameera

Answer 7

我在解决一个递归乘法问题时，没有使用*运算符，并且参考了这里的顶级答案，得出了一个解决方案。

我觉得值得发帖，因为我真的很喜欢这里顶级答案中的解释，但是我想以一种方式进行扩展，满足以下条件：

1. 具有函数表示。
2. 处理“余数”任意的情况。

这仅适用于正整数，但你可以将其包装在一个检查负数的语句中，就像其他答案中的一些方法。

Python代码：

def rec_mult_bitwise(a,b):
    # Base cases for recursion
    if b == 0:
        return 0
    if b == 1:
        return a

    # Get the most significant bit and the power of two it represents
    msb = 1
    pwr_of_2 = 0
    while True:
        next_msb = msb << 1
        if next_msb > b:
            break
        pwr_of_2 += 1
        msb = next_msb
        if next_msb == b:
            break

    # To understand the return value, remember:
    # 1: Left shifting by the power of two is the same as multiplying by the number itself (ie x*16=x<<4)
    # 2: Once we've done that, we still need to multiply by the remainder, hence b - msb
    return (a << pwr_of_2) + rec_mult_bitwise(a, b - msb)

- Willow

Answer 8

-(int)multiplyNumber:(int)num1 withNumber:(int)num2
{
    int mulResult =0;
    int ithBit;

    BOOL isNegativeSign = (num1<0 && num2>0) || (num1>0 && num2<0)   ;
    num1 = abs(num1);
    num2 = abs(num2);


    for(int i=0;i<sizeof(num2)*8;i++)
    {
        ithBit =  num2 & (1<<i);
        if(ithBit>0){
            mulResult +=(num1<<i);
        }

    }

    if (isNegativeSign) {
        mulResult =  ((~mulResult)+1 );
    }

    return mulResult;
}

- muzz

---

什么编程语言？Objective-C？ - Peter Mortensen

Answer 9

我刚刚意识到这个答案和之前的一样。哈哈，抱歉。

public static uint Multiply(uint a, uint b)
{
   uint c = 0;
   while(b > 0)
   {
      c += ((b & 1) > 0) ? a : 0;
      a <<= 1;
      b >>= 1;
   }
   return c;
}

- Nicolas

---

欢迎来到 Stack Overflow。如果这是一个重复的答案，您可以通过删除自己的帖子来帮助管理网站。 - Alex S

Answer 10

def multiply(x, y):
     return x << (y >> 1)

你需要将y的值减半，因此将y向右移动一位（y >> 1），然后再将位移x次以左来得到答案 x << (y >> 1)。

- ahmedabdihakim

---

什么编程语言？Python？ - Peter Mortensen