0

最近有人问我一个问题,"how do you multiply without using the multiplication operator, without any sort of looping statements or explicit addition"并意识到我根本不熟悉按位运算。

显然有维基百科,但我需要更多针对新手的解释。还有this hack guide,但我还没有掌握它。

我不介意你指出书中的一章,因为我可以通过 Safari Books 和其他资源访问一个好的图书馆。

4

2 回答 2

3

高德纳第2 卷 - 半数值算法

于 2010-07-19T15:40:16.803 回答
2

关键在于“半加器”和“全加器”。半加器将输入的两位相加以产生一位结果和一位进位。全加器将三位输入(两个正常输入加上来自低位的进位)相加以产生一位结果和一位进位。

在任何情况下,结果都是基于加法的真值表。对于半加器,即:0+0=0, 0+1=1, 1+0=1, 1+1=0+进位。

因此,结果的“正常”部分是输入的 XOR。结果的“进位”部分是输入的与。全加器几乎相同,但留下了臭名昭著的“读者练习”。

将它们放在一起,您对最低有效位使用半加器,对其他位使用全加器来添加 N 位输入。

一旦你可以做加法,就有几种方法可以做乘法。乘以 NxM 的简单(且缓慢)方法是将 N 与自身相加 M 次。更快(但更难理解)的方法是移位和添加。例如,Nx5 = Nx4 + Nx1。您可以通过将 N 左移 L 位来产生 NxB,其中 B = 2 L。

于 2010-07-19T15:42:21.797 回答