Java 如何在没有“*”运算符的情况下执行乘法？

How can I perform multiplication without the '*' operator?

提问by Race

I was just going through some basic stuff as I am learning C. I came upon a question to multiply a number by 7 without using the * operator. Basically it's like this

我在学习 C 时只是在学习一些基本的东西。我遇到了一个问题，即在不使用 * 运算符的情况下将数字乘以 7。基本上是这样的

      (x << 3) - x;

Now I know about basic bit manipulation operations, but I can't get how do you multiply a number by any other odd number without using the * operator? Is there a general algorithm for this?

现在我知道基本的位操作操作，但我不知道如何在不使用 * 运算符的情况下将数字乘以任何其他奇数？有没有通用的算法？

回答by Ignacio Vazquez-Abrams

An integer left shift is multiplying by 2, provided it doesn't overflow. Just add or subtract as appropriate once you get close.

整数左移乘以 2，前提是它不会溢出。一旦接近，只需适当增加或减少。

回答by cletus

When it comes down to it, multiplication by a positive integer can be done like this:

归根结底，乘以一个正整数可以这样完成：

int multiply(int a, int b) {
  int ret = 0;
  for (int i=0; i<b; i++) {
    ret += b;
  }
  return ret;
}

Efficient? Hardly. But it's correct (factoring in limits on ints and so forth).

高效的？几乎不。但它是正确的（考虑到整数等的限制）。

So using a left-shift is just a shortcut for multiplying by 2. But once you get to the highest power-of-2 under byou just add athe necessary number of times, so:

所以使用左移只是乘以 2 的捷径。但是一旦你达到最高的 2次方，b你只需添加a必要的次数，所以：

int multiply(int a, int b) {
  int ret = a;
  int mult = 1;
  while (mult <= b) {
    ret <<= 1;
    mult <<= 1;
  }
  while (mult < b) {
    ret += a;
  }
  return ret;
}

or something close to that.

或接近的东西。

To put it another way, to multiply by 7.

换句话说，乘以 7。

• Left shift by 2 (times 4). Left shift 3 is 8 which is >7;
• Add b3 times.

• 左移 2（乘以 4）。左移 3 为 8，即 >7；
• 添加b3次。

回答by Igor Zevaka

It is the same as x*8-x = x*(8-1) = x*7

它与 x*8-x = x*(8-1) = x*7

回答by Wang

Ugly and slow and untested, but...

丑陋，缓慢且未经测试，但是......

int mult(a,b){
    int i, rv=0;
    for(i=0; i < 31; ++i){
        if(a & 1<<i){
            rv += b << i;
        }
    }
    if(a & 1<<31){ // two's complement
        rv -= b<<31;
    }
    return rv;
}

回答by Wayne Conrad

Think about how you multiply in decimal using pencil and paper:

想想你如何用铅笔和纸乘以十进制：

  12
x 26
----
  72
 24
----
 312

What does multiplication look like in binary?

二进制中的乘法是什么样的？

   0111
x  0101
-------
   0111
  0000
 0111
-------
 100011

Notice anything? Unlike multiplication in decimal, where you need to memorize the "times table," when multiplying in binary, you are always multiplying one of the terms by either 0 or 1 before writing it down in the list addends. There's no times table needed. If the digit of the second term is 1, you add in the first term. If it's 0, you don't. Also note how the addends are progressively shifted over to the left.

注意到什么了吗？与十进制乘法不同，您需要记住“时间表”，在二进制乘法中，您总是将其中一项乘以 0 或 1，然后再将其写在列表加数中。不需要时间表。如果第二项的数字为 1，则添加第一项。如果它是 0，你就没有。还要注意加数是如何逐渐向左移动的。

If you're unsure of this, do a few binary multiplications on paper. When you're done, convert the result back to decimal and see if it's correct. After you've done a few, I think you'll get the idea how binary multiplication can be implemented using shifts and adds.

如果您不确定这一点，请在纸上进行一些二进制乘法。完成后，将结果转换回十进制，看看它是否正确。在你做了一些之后，我想你会明白如何使用移位和加法来实现二进制乘法。

回答by benzado

Any number, odd or even, can be expressed as a sum of powers of two. For example,

任何数字，奇数或偶数，都可以表示为 2 的幂之和。例如，

     1   2   4   8
------------------
 1 = 1
 2 = 0 + 2
 3 = 1 + 2
 4 = 0 + 0 + 4
 5 = 1 + 0 + 4
 6 = 0 + 2 + 4
 7 = 1 + 2 + 4
 8 = 0 + 0 + 0 + 8
11 = 1 + 2 + 0 + 8

So, you can multiply x by any number by performing the right set of shifts and adds.

因此，您可以通过执行正确的一组移位和加法将 x 乘以任何数字。

 1x = x
 2x = 0 + x<<1
 3x = x + x<<1
 4x = 0 +  0   + x<<2
 5x = x +  0   + x<<2
11x = x + x<<1 +   0  + x<<3

回答by Andrew Shepherd

unsigned int Multiply(unsigned int m1, unsigned int m2)
{
    unsigned int numBits = sizeof(unsigned int) * 8; // Not part of the core algorithm
    unsigned int product = 0;
    unsigned int mask = 1;
    for(int i =0; i < numBits; ++i, mask = mask << 1)
    {
        if(m1 & mask)
        {
            product += (m2 << i);
        }
    }
    return product;
}

回答by Andrew Shepherd

int multiply(int multiplicand, int factor)
{
    if (factor == 0) return 0;

    int product = multiplicand;
    for (int ii = 1; ii < abs(factor); ++ii) {
        product += multiplicand;
    }

    return factor >= 0 ? product : -product;
}

You wanted multiplication without *, you got it, pal!

你想要乘法没有*，你明白了，伙计！

回答by Apprentice Queue

@Wang, that's a good generalization. But here is a slightly faster version. But it assumes no overflow and a is non-negative.

@Wang，这是一个很好的概括。但这里有一个稍微快一点的版本。但它假设没有溢出并且 a 是非负的。

int mult(int a, int b){
    int p=1;
    int rv=0;
    for(int i=0; a >= p && i < 31; i++){
        if(a & p){
            rv += b;
        }
        p = p << 1;
        b = b << 1;
    }

    return rv;
}

It will loop at most 1+log_2(a) times. Could be faster if you swap a and b when a > b.

它最多循环 1+log_2(a) 次。如果在 a > b 时交换 a 和 b，可能会更快。

回答by Jerry Coffin

It's easy to avoid the '*' operator:

很容易避免使用“*”运算符：

mov eax, 1234h
mov edx, 5678h
imul edx

No '*' in sight. Of course, if you wanted to get into the spirit of it, you could also use the trusty old shift and add algorithm:

看不到“*”。当然，如果你想深入了解它的精神，你也可以使用可靠的旧移位并添加算法：

mult proc
; Multiplies eax by ebx and places result in edx:ecx
    xor ecx, ecx
    xor edx, edx
mul1:
    test ebx, 1
    jz  mul2
    add ecx, eax
    adc edx, 0
mul2:
    shr ebx, 1
    shl eax, 1
    test ebx, ebx
    jnz  mul1
done:
    ret
mult endp

Of course, with modern processors, all (?) have multiplication instructions, but back when the PDP-11was shiny and new, code like this saw real use.

当然，对于现代处理器，所有 (?) 都有乘法指令，但是在PDP-11闪亮而新颖的时候，这样的代码才真正有用。