Written by Shi Yinong
on January 20, 2022

一道有趣的面试题

今天在网上看到一个面试题：在不使用乘法的前提下，计算两个32位正整数$n_1$和$n_2$的乘积。这个问题本质上是个数学问题，还比较有趣，这里我给出解法以及详细数学证明，并给出进阶问题。

解法一：使用加法

$n_1 * n_2 = n_1 + n_1 + … + n_1$，一共$n_2$个$n_1$相加，但使用这个解法，面试肯定是不会通过的^_^

解法二：位运算

我们都知道乘法分配律：$a * b + a * c = a * (b+c)$，所以我们在计算两数相乘时，可以先将$n_2$分割成32个数：

\[n_2 = i_0 * 2^0 + i_1 * 2^1 + ... + i_{31} * 2^{31} ; \quad i_0, i_1 ... i_{31} \in (0, 1)\]

所以，根据乘法分配律：

\[n_1 * n_2 = n_1 * ( i_0 * 2^0 + i_1 * 2^1 + ... + i_{31} * 2^{31} )\] \[n_1 * n_2 = n_1 * i_0 * 2^0 + n_1 * i_1 * 2^1 + ... + n_1 * i_{31} * 2^{31}\]

当$n_1$和一个2的n次幂相乘时，我们可以使用位运算得到结果：$n_1 * 2^j = n_1 < < j$

所以现在唯一的问题就是，$n_2$如何分解成32个2的n次幂，其实本质就是要分别求出$i_0, i_1 … i_{31}$的值具体是0还是1即可。具体方法：遍历$2^{31}, 2^{30} … 2^0$，如果$n_2 >= 2^j$，则$i_j = 1, n_2 = n_2 - 2^j$，否则$i_j=0$

下面给出go代码实现：

func multiply(n1, n2 int64) int64 {
	var res int64
	for j := 31; j >= 0; j-- {
		if n2 >= 1<<j {
			res += n1 << j
			n2 -= 1 << j
		}
	}
	return res
}

进阶问题：不使用除法计算两个32位正整型的商和余数

按照上面计算乘积的思路，我们来计算$n_1$和$n_2$的商和余数。下面直接给公式：

\[n_1 \div n_2 = x ... y\] \[n_1 = n_2*x + y\]

我们将$x$按照上面的方式，分割为32个2的n次幂得到：

\[n_1 = n_2*( i_0 * 2^0 + i_1 * 2^1 + ... + i_{31} * 2^{31} ) + y\]

所以，这里仍需要计算$i_0, i_1 … i_{31}$，计算方式类似，遍历$2^{31}, 2^{30} … 2^0$，当$n_2 * 2^j <= n_1$时，$i_j = 1, n_1 = n_1 - n_2 * 2^j$，遍历完毕后，$y = n_1 $

下面给出go代码实现：

func divide(n1, n2 int64) (int64, int64) {
	if n2 == 0 {
		return 0, 0
	}
	var x int64
	for j := 31; j >= 0; j-- {
		if n1 >= n2<<j {
			n1 -= n2 << j
			x += 1 << j
		}
	}
	return x, n1
}

← → Top