当前位置：文江博客话题详情

C 语言中不带算术运算符的乘法

发布于 2024-11-26 18:34:13 字数 64 浏览 1 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

跨年 2024-12-03 18:34:13

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

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

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 中。从这个意义上说，您可以将异或运算符视为不带进位的加法运算。

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

c = a = 00000010
    b = 11100100

第三次迭代：

c = a = 00000000
    b = 11100110

现在 c（和 a）为 0，因此不再需要添加进位。我们退出循环并返回 b。请注意，即使继续循环，任何数字都不会改变。

To solve this problem, the first thing you want to do is figure out how to get simple arithmetic operations using just bitwise operators.

For example, addition can be achieved using this technique

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

Then it's a matter of doing multiplication using addition:

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;
}

This multiplication doesn't yet work if b is negative, but since this looks like a homework problem, I'll leave that as an exercise for you. ;)

Edit:
While multiplication is intuitive once you have addition, the addition function is not so easy to understand, so I'll explain it here.

Let's say you want to add two numbers, 11010011 and 10101. The usual way to do it is to line them up like so:

11010011
 + 10101

You'll notice that when you add two binary numbers, if the ith bit from both numbers is 1, then the resulting bit is 0, and there is a carry over to a bit to the left of i.

This carry is what the variable 'c' in the code stores.

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

We bit wise and b and a to get only the bits where both a and b are 1, then we left shift it by 1 to get the carry bits.

Then you can look at the bits where a and b differ, i.e. one of the bits is 1 and the other bit is 0. The resulting bit in this case will be 1 with no carry.

that's what this line stores:

b = b ^ a;

The line above essentially removes the bits where both a and b are 1 (now stored in c).

So now you have another two numbers b and c, that you need to add together.

First let's look at where we're at with the example after the first iteration of the loop

c = a = 00100010
    b = 11000110

It might not be entirely obvious yet, but b is accumulating the resulting sum. Through more iterations of the loop, more bits that are carried over are "added" back to b, with carries stored again in c. In that sense, you can think of the xor operator as an addition operation without carry.

Here's the second iteration of that loop:

c = a = 00000010
    b = 11100100

3rd iteration:

c = a = 00000000
    b = 11100110

Now c (and a) is 0, so there is no more carry to add. We exit the loop and return b. Note that even if you continue the loop, none of the numbers will change.

回复收藏 0 原文

风苍溪 2024-12-03 18:34:13

这是可能的，请参阅此 wiki 了解方向： http://en.wikipedia.org/wiki/Binary_multiplier< /a>

回复收藏 0 原文

淡莣 2024-12-03 18:34:13

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();
}

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();
}

回复收藏 0 原文