C中的乘法,没有算术运算符

Question

是否可以将两个数字相乘而不使用算术运算符？使用左移运算符,我可以将任意数乘以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

第3次迭代:

c = a = 00000000
    b = 11100110

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

Answer 2

有可能,请看这个wiki的方向:http://en.wikipedia.org/wiki/Binary_multiplier

Answer 3

void main()
{ 
  int n1, n2, n3, n4, x, y, i;
  printf("Enter first number");
  scanf("%d", &n1);
  printf("Enter second number");
  scanf("%d", &n2);
  n3 = n2;
  n4 = n2;
  n1-=1;
  for(i = n1;i > 0;i-=1)
  { 
    do { 
      x = n2 & n3; 
      y= n2 ^ n3; 
      n2 = x << 1; 
      n3 = y; 
    } while (x);
    n2 = y;
    n3 = n4;
  }
  printf("product of two number is %d", y);
  getch();
}