c - 没有算术运算符的C中的乘法

Question

是否可以在 C 语言中不使用算术运算符将两个数字相乘？使用左移运算符，我只能将任何数字乘以 2。其他数字呢？

Answer 1

要解决这个问题，您要做的第一件事就是弄清楚如何仅使用按位运算符进行简单的算术运算。

例如，可以使用这种技术实现加法

int add(int a, int b) {
   int c;
   while (a != 0) {
      c = b & a;
      b = b ^ a;
      c = c << 1;
      a = c;
   }
   return b;
}

然后就是用加法做乘法了:

int mult(int a, int b) {
   int i = 0;
   int c = 0;
   while (i < b) {
      c = add(c, a);
      i = add(i, 1);
   }
   return c;
}

如果 b 为负，则此乘法还不起作用，但由于这看起来像是一道家庭作业题，我将把它留作您的练习。 ;)

编辑:虽然乘法一旦有了加法就很直观，但加法函数就不那么容易理解了，所以我将在这里解释一下。

假设您要将两个数字相加，11010011 和 10101。通常的做法是将它们排成一行:

11010011
 + 10101

你会注意到，当你将两个二进制数相加时，如果两个数的第 i 位都是 1，则结果位为 0，并且 i 左边的位有一个结位。

这个进位是代码中变量'c'存储的内容。

//...
c = b & a;
//...
c << 1;
//...

我们对 b 和 a 进行位运算，只得到 a 和 b 都为 1 的位，然后左移 1 得到进位。

然后您可以查看 a 和 b 不同的位，即一位为 1，另一位为 0。在这种情况下，结果位将是 1，没有进位。

这就是这行存储的内容:

b = b ^ a;

上面的行基本上删除了 a 和 b 都为 1 的位(现在存储在 c 中)。

现在您有另外两个数字 b 和 c，您需要将它们相加。

首先让我们看看在循环的第一次迭代之后我们使用示例的位置

c = a = 00100010
    b = 11000110

它可能还不是很明显，但是 b 正在累积结果总和。通过循环的更多次迭代，更多携带的位被“添加”回 b，进位再次存储在 c 中。从这个意义上说，您可以将 xor 运算符视为没有进位的加法运算。

这是该循环的第二次迭代:

c = a = 00000010
    b = 11100100

第三次迭代:

c = a = 00000000
    b = 11100110

现在 c(和 a)为 0，所以没有更多的进位需要添加。我们退出循环并返回 b。请注意，即使您继续循环，任何数字都不会改变。