另一种在不使用“*”运算符的情况下将两个数相乘的方法
昨天我进行了一次有趣的采访,面试官问我一个经典问题:如何在不使用*
运算符的情况下将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))); }**
所以现在我有两个问题要问你:
- 我还缺少另一种方法吗?
- 我无法得出答案的事实certificate我的逻辑推理不够强大,无法提出解决方案,而且我不会“削减”成为程序员吗? 因为说实话,问题似乎并不那么困难,我很确定大多数程序员都会轻松快速地找到答案。
我不知道这是否必须是一个严格的“编程问题”。 但在数学中:
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"))
可能还有更多方法。
有一种称为俄罗斯农民增殖的方法。 在class次操作员的帮助下certificate这一点,
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; }
参考:
其他人已经充分地回答了问题1,我不会在这里重新讨论它,但我确实想在问题2上稍微打一针,因为看起来(对我来说)更有趣。
所以,当有人问你这类问题时,他们不太关心你的代码是什么样的,而是更关心你的思考方式。 在现实世界中,如果没有*运算符,您将不必实际编写乘法; 我知道的每种编程语言(除了Brainfuck ,我猜)都实现了乘法,几乎总是使用*运算符。 关键是,有时您正在处理代码,并且出于任何原因(可能由于库膨胀,由于配置错误,由于程序包不兼容等原因),您将无法使用您习惯的库。 我们的想法是看看你在这些情况下的运作方式。
问题不在于你是否“被裁掉”成为一名程序员; 这些技能可以学习。 我个人使用的一个技巧是考虑他们所问的问题的预期结果究竟是什么? 在这个特殊的例子中,正如我(我也认为你)在小学4年级学习,乘法重复加法。 因此,我会实施它(并且在过去;我在几次采访中也有同样的问题),并且循环重复添加。
问题是,如果你没有意识到乘法是重复加法(或者你被要求回答的任何其他问题),那么你只会被搞砸。 这就是为什么我不是这些类型问题的忠实粉丝,因为很多问题归结为你知道或不知道的琐事,而不是测试你作为程序员的真正技能(上面提到的技能)库等可以通过其他方式进行更好的测试)。
TL; DR – 告诉采访者重新发明轮子是一个坏主意
我不会接受采访者的Code Golf问题,而是以不同方式回答采访问题:
英特尔 , AMD , ARM和其他微处理器制造商的辉煌工程师几十年来一直在为如何在尽可能少的周期内将32位整数相乘而苦恼,事实上,甚至能够产生正确的,完整的64位乘法结果。位整数没有溢出。
(例如,没有预先铸造a
或b
到long
,2个整数的乘法,如123456728 * 23456789
溢出为负数 )
在这方面,高级语言只有一个与这样的整数乘法相关的工作,即,以尽可能少的绒毛来完成处理器的工作。
任何数量的Code Golf都可以在软件IMO中复制这样的乘法是精神错乱。
毫无疑问,很多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中 ,除非您重构代码以允许尾部调用优化 ,否则在方法2中对于大的
b
值将耗尽堆栈
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)
或更差,因此性能将非常糟糕。
为了完整性:
Math.multiplyExact(int,int) :
返回参数的乘积,如果结果溢出int则抛出exception。
如果抛出溢出是可以接受的。
如果您没有整数值,则可以利用其他数学属性来获得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(); }
一种解决方案是使用逐位操作。 这有点类似于之前提出的答案,但也消除了分裂。 我们可以有类似的东西。 我会用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<
采访者提出的问题反映了他们的价值观。 许多程序员都会奖励他们自己的解谜技巧和数学敏锐度,他们认为这些技能是最好的程序员。
他们错了。 最好的程序员处理最重要的事情,而不是最有趣的事情; 做出简单,无聊的技术选择; 写清楚; 想想用户; 并远离愚蠢的弯路。 我希望我有这些技能和倾向!
如果你可以做其中的几件事并且还要编写工作代码,许多编程团队都需要你。 你可能是一个超级明星。
但是当你被困难时,你应该在面试中做些什么呢?
提出澄清问题。 (“什么样的数字?”“这是什么样的编程语言没有乘法?”并且没有粗鲁:“为什么我这样做?”)如果你怀疑,问题只是一个愚蠢与现实无关的谜题,这些问题不会产生有用的答案。 但是常识和想要解决“问题背后的问题”的重要工程美德。
在糟糕的面试中你能做的最好的就是展示自己的优势。 认识到他们取决于你的面试官; 如果他们不这样做,那就是他们的损失。 不要气馁。 还有其他公司。
根据需要使用BigInteger.multiply
或BigDecimal.multiply
。