另一种在不使用"*"运算符的情况下将两个数相乘的方法

Question

昨天我进行了一次有趣的采访,面试官问我一个经典问题:如何在不使用*运算符的情况下将Java中的两个数字相乘.老实说,我不知道这是采访带来的压力,但我无法提出任何解决方案.

面试结束后,我回到家中,通过SO轻松寻找答案.到目前为止,我发现了以下内容:

第一种方法:使用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;
}

第二种方法:使用递归

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

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

}

第三种方法:使用Log10

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

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

1. 我还缺少另一种方法吗？
2. 我无法得出答案的事实证明我的逻辑推理不够强大,无法提出解决方案,而且我不会"削减"成为程序员吗？因为说实话,问题似乎并不那么困难,我很确定大多数程序员都会轻松快速地找到答案.

Answer 1

我不知道这是否必须是一个严格的"编程问题".但在数学中:

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

所以:

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

方法2(更多"编程/ API"解决方案):

使用大小数,大整数:

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

可能还有其他一些方法.

Answer 2

有一种称为俄罗斯农民增殖的方法.在班次操作员的帮助下证明这一点,

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

想法是将第一个数字加倍并重复减半第二个数字直到第二个数字不变为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;
}

参考:

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

Answer 3

其他人已经充分地回答了问题1,我不会在这里重新讨论它,但我确实想稍微回答问题2,因为看起来(对我来说)更有趣.

因此,当有人问你这类问题时,他们不太关心你的代码是什么样的,而是更关心你的思考方式.在现实世界中,如果没有*运算符,您将不会真正编写乘法; 我所知道的每种编程语言(除了Brainfuck,我猜)都实现了乘法运算,几乎总是使用*运算符.关键是,有时您正在使用代码,并且出于任何原因(可能由于库膨胀,由于配置错误,由于程序包不兼容等原因),您将无法使用您习惯的库.我们的想法是看看你在这些情况下的运作方式.

问题不在于你是否"被裁掉"成为一名程序员; 这些技能可以学习.我个人使用的一个技巧是考虑他们所问的问题的预期结果究竟是什么？在这个特殊的例子中,正如我(我也认为你)在小学4年级学习,乘法重复加法.因此,我会实施它(并且在过去;我在几次采访中也有同样的问题),并且循环重复添加.

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

Answer 4

TL; DR - 告诉采访者重新发明轮子是一个坏主意

我不会接受采访者的Code Golf问题,而是以不同的方式回答采访问题:

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

(例如无需预先浇铸a或b到long,2个整数的乘积如123456728 * 23456789 溢出到一个负数)

在这方面,高级语言只有一个与整数乘法相关的工作,即这样,即使处理器尽可能少地完成工作.

在软件IMO中复制此类乘法的任何数量的Code Golf都是疯狂的.

有无疑许多hacks可能模拟乘法,虽然很多人将只值范围受限制的工作a和b(事实上,没有由OP列出的3种方法进行无缺陷的所有的a值和b,即使我们忽略溢出问题).并且所有都将比IMUL指令慢(数量级).

例如,如果其中一个a或者b是2的正幂,则可以通过log将另一个变量向左移位.

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

但这真的很乏味.

在不太可能的情况下,*操作员真的从Java语言规范中一夜之间消失,接下来最好,我会使用包含乘法函数的现有库,例如BigInteger.multiply(),出于同样的原因 - 多年的批判性思维比我的思想更明亮生产和测试这样的库.

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

玩操作员*Code Golf的问题

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

• 如果第一个数字a为负数,方法A(循环)将不起作用.

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

对于a的任何负值都将返回0,因为从不满足循环连续条件

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

multiplier(100, 1000000)

"main"java.lang.StackOverflowError

• 在方法3中,您将得到舍入错误log10(更不用说尝试记录任何数字<= 0的明显问题).例如

multiplier(2389, 123123);

返回294140846,但实际答案是294140847(最后的数字9 x 3表示产品必须以7结尾)

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

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

例如,对于一个值(int)multiply(1, 93)返回92,因为multiply返回92.99999 ....这会被强制转换为32位整数.

当然,我们不需要提及这些算法中的许多都是O(N)或者更差,因此性能将非常糟糕.