C++ 如何在不使用 ++ 或 + 或其他算术运算符的情况下将两个数字相加
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1149929/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to add two numbers without using ++ or + or another arithmetic operator
提问by Vivek Sharma
How do I add two numbers without using ++ or + or any other arithmetic operator?
如何在不使用 ++ 或 + 或任何其他算术运算符的情况下将两个数字相加？
It was a question asked a long time ago in some campus interview. Anyway, today someone asked a question regarding some bit-manipulations, and in answers a beautiful quide Stanford bit twiddlingwas referred. I spend some time studying it and thought that there actually might be an answer to the question. I don't know, I could not find one. Does an answer exist?
这是很久以前在一些校园面试中提出的问题。不管怎么说，今天有人问一些关于位操作一个问题，在回答一个美丽的quide斯坦福位操作被提到。我花了一些时间研究它，并认为这个问题实际上可能有答案。我不知道，我找不到一个。有答案吗？
回答by Jason Creighton
This is something I have written a while ago for fun. It uses a two's complementrepresentation and implements addition using repeated shifts with a carry bit, implementing other operators mostly in terms of addition.
这是我前一段时间写的东西，为了好玩。它使用二进制补码表示，并使用带有进位的重复移位来实现加法，主要以加法来实现其他运算符。
#include <stdlib.h> /* atoi() */
#include <stdio.h> /* (f)printf */
#include <assert.h> /* assert() */
int add(int x, int y) {
int carry = 0;
int result = 0;
int i;
for(i = 0; i < 32; ++i) {
int a = (x >> i) & 1;
int b = (y >> i) & 1;
result |= ((a ^ b) ^ carry) << i;
carry = (a & b) | (b & carry) | (carry & a);
}
return result;
}
int negate(int x) {
return add(~x, 1);
}
int subtract(int x, int y) {
return add(x, negate(y));
}
int is_even(int n) {
return !(n & 1);
}
int divide_by_two(int n) {
return n >> 1;
}
int multiply_by_two(int n) {
return n << 1;
}
int multiply(int x, int y) {
int result = 0;
if(x < 0 && y < 0) {
return multiply(negate(x), negate(y));
}
if(x >= 0 && y < 0) {
return multiply(y, x);
}
while(y > 0) {
if(is_even(y)) {
x = multiply_by_two(x);
y = divide_by_two(y);
} else {
result = add(result, x);
y = add(y, -1);
}
}
return result;
}
int main(int argc, char **argv) {
int from = -100, to = 100;
int i, j;
for(i = from; i <= to; ++i) {
assert(0 - i == negate(i));
assert(((i % 2) == 0) == is_even(i));
assert(i * 2 == multiply_by_two(i));
if(is_even(i)) {
assert(i / 2 == divide_by_two(i));
}
}
for(i = from; i <= to; ++i) {
for(j = from; j <= to; ++j) {
assert(i + j == add(i, j));
assert(i - j == subtract(i, j));
assert(i * j == multiply(i, j));
}
}
return 0;
}
回答by Tom Leys
Or, rather than Jason's bitwise approach, you can calculate many bits in parallel - this should run much faster with large numbers. In each step figure out the carry part and the part that is sum. You attempt to add the carry to the sum, which could cause carry again - hence the loop.
或者，您可以并行计算许多位，而不是 Jason 的按位方法 - 这应该在处理大量数字时运行得更快。在每一步中找出进位部分和总和部分。您尝试将进位添加到总和中，这可能会再次导致进位 - 因此循环。
>>> def add(a, b):
while a != 0:
# v carry portion| v sum portion
a, b = ((a & b) << 1), (a ^ b)
print b, a
return b
when you add 1 and 3, both numbers have the 1 bit set, so the sum of that 1+1 carries. The next step you add 2 to 2 and that carries into the correct sum four. That causes an exit
当您将 1 和 3 相加时，两个数字都设置了 1 位，因此 1+1 的总和进位。下一步，您将 2 加到 2，然后得出正确的总和四。这会导致退出
>>> add(1,3)
2 2
4 0
4
Or a more complex example
或者更复杂的例子
>>> add(45, 291)
66 270
4 332
8 328
16 320
336
Edit:For it to work easily on signed numbers you need to introduce an upper limit on a and b
编辑：为了在有符号数字上轻松工作，您需要在 a 和 b 上引入上限
>>> def add(a, b):
while a != 0:
# v carry portion| v sum portion
a, b = ((a & b) << 1), (a ^ b)
a &= 0xFFFFFFFF
b &= 0xFFFFFFFF
print b, a
return b
Try it on
试试
add(-1, 1)
to see a single bit carry up through the entire range and overflow over 32 iterations
看到单个位在整个范围内向上进位并在 32 次迭代中溢出
4294967294 2
4294967292 4
4294967288 8
...
4294901760 65536
...
2147483648 2147483648
0 0
0L
回答by intepid
int Add(int a, int b)
{
while (b)
{
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
回答by Samuel Carrijo
You could transform an adder circuitinto an algorithm. They only do bitwise operations =)
您可以将加法器电路转换为算法。他们只做按位运算 =)
回答by Fabio Ceconello
Well, to implement an equivalent with boolean operators is quite simple: you do a bit-by-bit sum (which is an XOR), with carry (which is an AND). Like this:
好吧，用布尔运算符实现等价物非常简单：您使用进位（这是一个 AND）进行逐位求和（这是一个 XOR）。像这样：
int sum(int value1, int value2)
{
int result = 0;
int carry = 0;
for (int mask = 1; mask != 0; mask <<= 1)
{
int bit1 = value1 & mask;
int bit2 = value2 & mask;
result |= mask & (carry ^ bit1 ^ bit2);
carry = ((bit1 & bit2) | (bit1 & carry) | (bit2 & carry)) << 1;
}
return result;
}
回答by rampion
You've already gotten a couple bit manipulation answers. Here's something different.
你已经得到了一些操作的答案。这里有一些不同的东西。
In C, arr[ind] == *(arr + ind). This lets us do slightly confusing (but legal) things like int arr = { 3, 1, 4, 5 }; int val = 0[arr];.
在 C 中，arr[ind] == *(arr + ind)。这让我们可以做一些有点混乱（但合法）的事情，比如int arr = { 3, 1, 4, 5 }; int val = 0[arr];.
So we can define a custom add function (without explicit use of an arithmetic operator) thusly:
所以我们可以这样定义一个自定义的 add 函数（不显式使用算术运算符）：
unsigned int add(unsigned int const a, unsigned int const b)
{
/* this works b/c sizeof(char) == 1, by definition */
char * const aPtr = (char *)a;
return (int) &(aPtr[b]);
}
Alternately, if we want to avoid this trick, and if by arithmetic operator they include |, &, and ^(so direct bit manipulation is not allowed) , we can do it via lookup table:
或者，如果我们想避免这个技巧，并且如果通过算术运算符包括|, &, 和^（因此不允许直接位操作），我们可以通过查找表来完成：
typedef unsigned char byte;
const byte lut_add_mod_256[256][256] = {
{ 0, 1, 2, /*...*/, 255 },
{ 1, 2, /*...*/, 255, 0 },
{ 2, /*...*/, 255, 0, 1 },
/*...*/
{ 254, 255, 0, 1, /*...*/, 253 },
{ 255, 0, 1, /*...*/, 253, 254 },
};
const byte lut_add_carry_256[256][256] = {
{ 0, 0, 0, /*...*/, 0 },
{ 0, 0, /*...*/, 0, 1 },
{ 0, /*...*/, 0, 1, 1 },
/*...*/
{ 0, 0, 1, /*...*/, 1 },
{ 0, 1, 1, /*...*/, 1 },
};
void add_byte(byte const a, byte const b, byte * const sum, byte * const carry)
{
*sum = lut_add_mod_256[a][b];
*carry = lut_add_carry_256[a][b];
}
unsigned int add(unsigned int a, unsigned int b)
{
unsigned int sum;
unsigned int carry;
byte * const aBytes = (byte *) &a;
byte * const bBytes = (byte *) &b;
byte * const sumBytes = (byte *) ∑
byte * const carryBytes = (byte *) &carry;
byte const test[4] = { 0x12, 0x34, 0x56, 0x78 };
byte BYTE_0, BYTE_1, BYTE_2, BYTE_3;
/* figure out endian-ness */
if (0x12345678 == *(unsigned int *)test)
{
BYTE_0 = 3;
BYTE_1 = 2;
BYTE_2 = 1;
BYTE_3 = 0;
}
else
{
BYTE_0 = 0;
BYTE_1 = 1;
BYTE_2 = 2;
BYTE_3 = 3;
}
/* assume 4 bytes to the unsigned int */
add_byte(aBytes[BYTE_0], bBytes[BYTE_0], &sumBytes[BYTE_0], &carryBytes[BYTE_0]);
add_byte(aBytes[BYTE_1], bBytes[BYTE_1], &sumBytes[BYTE_1], &carryBytes[BYTE_1]);
if (carryBytes[BYTE_0] == 1)
{
if (sumBytes[BYTE_1] == 255)
{
sumBytes[BYTE_1] = 0;
carryBytes[BYTE_1] = 1;
}
else
{
add_byte(sumBytes[BYTE_1], 1, &sumBytes[BYTE_1], &carryBytes[BYTE_0]);
}
}
add_byte(aBytes[BYTE_2], bBytes[BYTE_2], &sumBytes[BYTE_2], &carryBytes[BYTE_2]);
if (carryBytes[BYTE_1] == 1)
{
if (sumBytes[BYTE_2] == 255)
{
sumBytes[BYTE_2] = 0;
carryBytes[BYTE_2] = 1;
}
else
{
add_byte(sumBytes[BYTE_2], 1, &sumBytes[BYTE_2], &carryBytes[BYTE_1]);
}
}
add_byte(aBytes[BYTE_3], bBytes[BYTE_3], &sumBytes[BYTE_3], &carryBytes[BYTE_3]);
if (carryBytes[BYTE_2] == 1)
{
if (sumBytes[BYTE_3] == 255)
{
sumBytes[BYTE_3] = 0;
carryBytes[BYTE_3] = 1;
}
else
{
add_byte(sumBytes[BYTE_3], 1, &sumBytes[BYTE_3], &carryBytes[BYTE_2]);
}
}
return sum;
}
回答by Indy9000
All arithmetic operations decompose to bitwise operations to be implemented in electronics, using NAND, AND, OR, etc. gates.
所有算术运算都分解为要在电子设备中实现的按位运算，使用 NAND、AND、OR 等门。
回答by Frederico
For unsigned numbers, use the same addition algorithm as you learned in first class, but for base 2 instead of base 10. Example for 3+2 (base 10), i.e 11+10 in base 2:
对于无符号数，使用与您在第一堂课中学到的相同的加法算法，但用于基数 2 而不是基数 10。 3+2（基数 10）的示例，即基数 2 中的 11+10：
1 ?--- carry bit
0 1 1 ?--- first operand (3)
+ 0 1 0 ?--- second operand (2)
-------
1 0 1 ?--- total sum (calculated in three steps)
回答by ChrisV
If you're feeling comedic, there's always this spectacularly awful approach for adding two (relatively small) unsigned integers. No arithmetic operators anywhere in your code.
如果您觉得很喜剧，那么添加两个（相对较小的）无符号整数总是有这种非常糟糕的方法。代码中的任何地方都没有算术运算符。
In C#:
在 C# 中：
static uint JokeAdder(uint a, uint b)
{
string result = string.Format(string.Format("{{0,{0}}}{{1,{1}}}", a, b), null, null);
return result.Length;
}
In C, using stdio (replace snprintf with _snprintf on Microsoft compilers):
在 C 中，使用 stdio（在 Microsoft 编译器上用 _snprintf 替换 snprintf）：
#include <stdio.h>
unsigned int JokeAdder(unsigned int a, unsigned int b)
{
return snprintf(NULL, 0, "%*.*s%*.*s", a, a, "", b, b, "");
}
回答by Tarik Kaya
Here is a compact C solution. Sometimes recursion is more readable than loops.
这是一个紧凑的 C 解决方案。有时递归比循环更具可读性。
int add(int a, int b){
if (b == 0) return a;
return add(a ^ b, (a & b) << 1);
}
