Java 另一种不使用“*”运算符将两个数字相乘的方法

Another method to multiply two numbers without using the "*" operator

提问by Jesse James

I had an interesting interview yesterday where the interviewer asked me a classic question: How can we multiply two numbers in Java without using the *operator. Honestly, I don't know if it's the stress that comes with interviews, but I wasn't able to come up with any solution.

昨天我有一个有趣的面试，面试官问了我一个经典问题：我们如何在不使用*运算符的情况下在 Java 中将两个数字相乘。老实说，我不知道是不是面试带来的压力，但我想不出任何解决方案。

After the interview, I went home and breezed through SO for answers. So far, here are the ones I have found:

面试结束后，我回到家，轻而易举地通过 SO 寻找答案。到目前为止，以下是我找到的：

First Method: Using a For loop

第一种方法：使用 For 循环

// Using For loop
public static int multiplierLoop(int a, int b) {
    int resultat = 0;
    for (int i = 0; i < a; i++) {
        resultat += b;
    }

    return resultat;
}

Second Method: Using Recursion

第二种方法：使用递归

// using Recursion
public static int multiplier(int a, int b) {

    if ((a == 0) || (b == 0))
        return 0;
    else
        return (a + multiplier(a, b - 1));

}

Third Method: Using Log10

第三种方法：使用 Log10

**// Using Math.Log10
public static double multiplierLog(int a, int b) {
    return Math.pow(10, (Math.log10(a) + Math.log10(b)));
}**

So now I have two questions for you:

所以现在我有两个问题要问你：

1. Is there still another method I'm missing?
2. Does the fact that I wasn't able to come up with the answer proves that my logical reasoning isn't strong enough to come up with solutions and that I'm not "cut out" to be a programmer? Cause let's be honest, the question didn't seem that difficult and I'm pretty sure most programmers would easily and quickly find an answer.

1. 我还缺少另一种方法吗？
2. 我无法想出答案的事实是否证明我的逻辑推理不够强大，无法提出解决方案，而且我还没有“被淘汰”成为一名程序员？因为老实说，这个问题似乎并不难，而且我很确定大多数程序员会轻松快速地找到答案。

回答by ernest_k

I don't know whether that has to be a strictly "programming question". But in Maths:

我不知道这是否必须是一个严格的“编程问题”。但是在数学中：

x * y = x / (1 / y) #divide by inverse

So:

所以：

Method 1:

方法一：

public static double multiplier(double a, double b) {

    // return a / (1 / b);

    // the above may be too rough
    // Java doesn't know that "(a / (b / 0)) == 0"
    // a special case for zero should probably be added:

    return 0 == b ? 0 : a / (1 / b);
}

Method 2(a more "programming/API" solution):

方法 2（更“编程/API”的解决方案）：

Use big decimal, big integer:

使用大十进制、大整数：

new BigDecimal("3").multiply(new BigDecimal("9"))

There are probably a few more ways.

可能还有几种方法。

回答by StuartLC

TL;DR - Inform the interviewer that re-inventing the wheel is a bad idea

TL;DR - 告诉面试官重新发明轮子是个坏主意

Rather than entertain the interviewer's Code Golfquestion, I would have answered the interview question differently:

与其招待面试官的Code Golf问题，我会以不同的方式回答面试问题：

Brilliant engineers at Intel, AMD, ARMand other microprocessor manufacturers have agonized for decades as how to multiply 32 bit integers together in the fewest possible cycles, and in fact, are even able to produce the correct, full 64 bit result of multiplication of 32 bit integers without overflow.

几十年来，英特尔、AMD、ARM和其他微处理器制造商的杰出工程师一直在为如何在尽可能少的周期内将 32 位整数相乘而苦苦挣扎，事实上，他们甚至能够产生 32 相乘的正确、完整的 64 位结果没有溢出的位整数。

(e.g. without pre-casting aor bto long, a multiplication of 2 ints such as 123456728 * 23456789overflows into a negative number)

（例如，没有预转换a或bto long，乘以 2 个整数，例如123456728 * 23456789溢出为负数）

In this respect, high level languages have only one jobto do with integer multiplications like this, viz, to get the job done by the processor with as little fluff as possible.

在这方面，高级语言只有一项工作与像这样的整数乘法有关，即让处理器尽可能少地完成工作。

Any amount of Code Golf to replicate such multiplication in software IMO is insanity.

在软件 IMO 中复制这种乘法的任何数量的 Code Golf 都是疯狂的。

There's undoubtedly many hackswhich could simulate multiplication, although many will only work on limited ranges of values aand b(in fact, none of the 3 methods listed by the OP perform bug-free for all values of a and b, even if we disregard the overflow problem). And all will be (orders of magnitude) slower than an IMULinstruction.

毫无疑问hacks，有很多可以模拟乘法，尽管很多只适用于有限范围的值a和b（事实上​​，OP 列出的 3 种方法中没有一个对 a 和 b 的所有值执行无错误，即使我们忽略溢出问题）。并且所有这些都将比IMUL指令慢（几个数量级）。

For example, if either aor bis a positive power of 2, then bit shifting the other variable to the left by log can be done.

例如，如果a或b是2的正幂，则可以将另一个变量向左移位 log 。

if (b == 2)
   return a << 1;
if (b == 4)
   return a << 2;
... 

But this would be really tedious.

但这真的会很乏味。

In the unlikely event of the *operator really disappearing overnight from the Java language spec, next best, I would be to use existing libraries which contain multiplication functions, e.g. BigInteger.multiply(), for the same reasons - many years of critical thinking by minds brighter than mine has gone into producing, and testing, such libraries.

万一*操作符真的在一夜之间从 Java 语言规范中消失，那么接下来最好的情况是，我将使用包含乘法函数的现有库，例如BigInteger.multiply()，出于同样的原因 - 比我更聪明的头脑多年来的批判性思维已经一去不复返了进入生产和测试，这样的库。

BigInteger.multiplywould obviously be reliable to 64 bits and beyond, although casting the result back to a 32 bit int would again invite overflow problems.

BigInteger.multiply显然对 64 位及更高版本是可靠的，尽管将结果转换回 32 位 int 会再次引发溢出问题。

The problem with playing operator * Code Golf

玩运营商的问题 * Code Golf

There's inherent problems with all 3 of the solutions cited in the OP's question:

OP 问题中引用的所有 3 个解决方案都存在固有问题：

• Method A(loop) won't work if the first number ais negative.

• 如果第一个数字a是负数，方法 A（循环）将不起作用。

 for (int i = 0; i < a; i++) {
      resultat += b;
  }

Will return 0 for any negative value of a, because the loop continuation condition is never met

对于 a 的任何负值都将返回 0，因为永远不会满足循环继续条件

• In Method B, you'll run out of stack for large values of bin method 2, unless you refactor the code to allow for Tail Call Optimisation

• 在方法 B 中，b除非您重构代码以允许尾调用优化，否则您将用完方法 2 中的大值的堆栈

multiplier(100, 1000000)

"main" java.lang.StackOverflowError

“主”java.lang.StackOverflowError

• And in Method 3, you'll get rounding errors with log10(not to mention the obvious problems with attempting to take a log of any number <= 0). e.g.

• 在方法 3 中，您将得到舍入错误log10（更不用说尝试记录任何数字 <= 0 的日志时存在的明显问题）。例如

multiplier(2389, 123123);

returns 294140846, but the actual answer is 294140847(the last digits 9 x 3 mean the product must end in 7)

返回294140846，但实际答案是294140847（最后一位数字 9 x 3 表示产品必须以 7 结尾）

Even the answer using two consecutive double precision division operatorsis prone to rounding issueswhen re-casting the double result back to an integer:

即使使用两个连续的双精度除法运算符的答案在将双精度结果重新转换为整数时也容易出现舍入问题：

static double multiply(double a, double b) {
    return 0 == (int)b 
       ? 0.0 
       : a / (1 / b);
}

e.g. for a value (int)multiply(1, 93)returns 92, because multiplyreturns 92.99999.... which is truncated with the cast back to a 32 bit integer.

例如，对于一个值(int)multiply(1, 93)返回 92，因为multiply返回 92.99999.... 它被截断为 32 位整数。

And of course, we don't need to mention that many of these algorithms are O(N)or worse, so the performance will be abysmal.

当然，我们无需提及其中许多算法O(N)或更糟，因此性能将非常糟糕。

回答by prime

There is a method called Russian Peasant Multiplication. Demonstrate this with the help of a shift operator,

有一种方法叫做俄罗斯农民乘法。在移位运算符的帮助下证明这一点，

public static int multiply(int n, int m)
{ 
    int ans = 0, count = 0;
    while (m > 0)
    {
        if (m % 2 == 1)             
            ans += n << count;
        count++;
        m /= 2;
    }

    return ans;
}

The idea is to double the first number and halve the second number repeatedly till the second number doesn't become 1. In the process, whenever the second number become odd, we add the first number to result (result is initialized as 0) One other implementation is,

这个想法是将第一个数字加倍，然后将第二个数字重复减半，直到第二个数字不变成1。在这个过程中，每当第二个数字变成奇数时，我们将第一个数字添加到结果中（结果初始化为0）一个其他实现是，

static int russianPeasant(int n, int m) {
    int ans = 0;

    while (m > 0) {
        if ((m & 1) != 0)
            ans = ans + n;

        n = n << 1;
        m = m >> 1;
    }
    return ans;
}

refer :

参考 ：

• https://www.geeksforgeeks.org/russian-peasant-multiply-two-numbers-using-bitwise-operators/
• https://www.geeksforgeeks.org/multiplication-two-numbers-shift-operator/

• https://www.geeksforgeeks.org/russian-peasant-multiply-two-numbers-using-bitwise-operators/
• https://www.geeksforgeeks.org/multiplication-two-numbers-shift-operator/

回答by Hulk

For completeness:

为了完整性：

Math.multiplyExact(int,int):

Math.multiplyExact(int,int)：

Returns the product of the arguments, throwing an exception if the result overflows an int.

返回参数的乘积，如果结果溢出 int 则抛出异常。

if throwing on overflow is acceptable.

如果抛出溢出是可以接受的。

回答by Ertai87

Others have hit on question 1 sufficiently that I'm not going to rehash it here, but I did want to hit on question 2 a little, because it seems (to me) the more interesting one.

其他人已经充分回答了问题 1，我不打算在这里重新讨论它，但我确实想稍微回答问题 2，因为它似乎（对我来说）更有趣。

So, when someone is asking you this type of question, they are less concerned with what your code looks like, and more concerned with how you are thinking. In the real world, you won't ever actually have to write multiplication without the * operator; every programming language known to man (with the exception of Brainfwor, I guess) has multiplication implemented, almost always with the * operator. The point is, sometimes you are working with code, and for whatever reason (maybe due to library bloat, due to configuration errors, due to package incompatibility, etc), you won't be able to use a library you are used to. The idea is to see how you function in those situations.

所以，当有人问你这类问题时，他们不太关心你的代码是什么样子，而更关心你是如何思考的。在现实世界中，您实际上不必在没有 * 运算符的情况下编写乘法；人类已知的每种编程语言（我猜是Brainfwor除外）都实现了乘法，几乎总是使用 * 运算符。关键是，有时您正在处理代码，无论出于何种原因（可能由于库膨胀、配置错误、包不兼容等），您将无法使用您习惯的库。这个想法是看看你在这些情况下是如何运作的。

The question isn't whether or not you are "cut out" to be a programmer; skills like these can be learned. A trick I use personally is to think about what, exactly, is the expected result for the question they're asking? In this particular example, as I (and I presume you as well) learned in grade 4 in elementary school, multiplication is repeated addition. Therefore, I would implement it (and have in the past; I've had this same question in a few interviews) with a for loop doing repeated addition.

问题不在于你是否“适合”成为一名程序员；这样的技能是可以学习的。我个人使用的一个技巧是考虑他们提出的问题的预期结果究竟是什么？在这个特定的例子中，正如我（我假设你也是）在小学 4 年级学到的，乘法是重复的加法。因此，我会使用 for 循环重复添加来实现它（并且在过去；我在几次采访中都遇到过同样的问题）。

The thing is, if you don't realize that multiplication is repeated addition (or whatever other question you're being asked to answer), then you'll just be screwed. Which is why I'm not a huge fan of these types of questions, because a lot of them boil down to trivia that you either know or don't know, rather than testing your true skills as a programmer (the skills mentioned above regarding libraries etc can be tested much better in other ways).

问题是，如果你没有意识到乘法是重复的加法（或者你被要求回答的任何其他问题），那么你就会被搞砸。这就是为什么我不是这类问题的忠实粉丝，因为其中很多都归结为你知道或不知道的琐事，而不是测试你作为程序员的真正技能（上面提到的技能可以通过其他方式更好地测试库等）。

回答by DavidW

If you don't have integer values, you can take advantage of other mathematical properties to get the product of 2 numbers. Someone has already mentioned log10, so here's a bit more obscure one:

如果您没有整数值，您可以利用其他数学属性来获得 2 个数字的乘积。有人已经提到了log10，所以这里有一个更晦涩的：

public double multiply(double x, double y) {
    Vector3d vx = new Vector3d(x, 0, 0);
    Vector3d vy = new Vector3d(0, y, 0);
    Vector3d result = new Vector3d().cross(vx, vy);
    return result.length();
}

回答by emory

Use BigInteger.multiplyor BigDecimal.multiplyas appropriate.

根据需要使用BigInteger.multiply或BigDecimal.multiply。

回答by lkrv

One solution is to use bit wise operations. That's a bit similar to an answer presented before, but eliminating division also. We can have something like this. I'll use C, because I don't know Java that well.

一种解决方案是使用按位运算。这有点类似于之前提出的答案，但也消除了除法。我们可以有这样的事情。我将使用 C，因为我不太了解 Java。

uint16_t multiply( uint16_t a, uint16_t b ) {
  uint16_t i = 0;
  uint16_t result = 0;

  for (i = 0; i < 16; i++) {
    if ( a & (1<<i) ) {
      result += b << i;
    }
  }
  return result;
}

回答by Jason Orendorff

The questions interviewers ask reflect their values. Many programmers prize their own puzzle-solving skills and mathematical acumen, and they think those skills make the best programmers.

面试官提出的问题反映了他们的价值观。许多程序员看重自己的解谜技能和数学敏锐度，他们认为这些技能可以造就最好的程序员。

They are wrong. The best programmers work on the most important thing rather than the most interesting bit; make simple, boring technical choices; write clearly; think about users; and steer away from stupid detours. I wish I had these skills and tendencies!

他们错了。最好的程序员致力于最重要的事情，而不是最有趣的部分；做出简单、无聊的技术选择；写清楚；为用户着想；并避开愚蠢的弯路。我希望我有这些技能和倾向！

If you can do several of those things and also crank out working code, many programming teams need you. You might be a superstar.

如果您可以完成其中几件事并编写出可运行的代码，那么许多编程团队都需要您。你可能是超级巨星。

---

---

But what should you do in an interview when you're stumped?

但是当你被难住的时候，你应该在面试中做什么？

Ask clarifying questions. ("What kind of numbers?" "What kind of programming language is this that doesn't have multiplication?" And without being rude: "Why am I doing this?") If, as you suspect, the question is just a dumb puzzle with no bearing on reality, these questions will not produce useful answers. But common sense and a desire to get at "the problem behind the problem" are important engineering virtues.

提出澄清问题。（“什么样的数字？”“这种没有乘法的编程语言是什么？”并且毫不粗鲁地：“我为什么要这样做？”）如果，正如你所怀疑的，这个问题只是一个愚蠢的问题与现实无关的谜题，这些问题不会产生有用的答案。但常识和解决“问题背后的问题”的愿望是重要的工程美德。

The best you can do in a bad interview is demonstrate your strengths. Recognizing them is up to your interviewer; if they don't, that's their loss. Don't be discouraged. There are other companies.

在糟糕的面试中你能做的最好的事情就是展示你的优势。识别它们取决于你的面试官；如果他们不这样做，那就是他们的损失。不要气馁。还有其他公司。