如何在不使用++或+或其他算术运算符的情况下添加两个数字
如何在不使用++或+或其他算术运算符的情况下添加两个数字？
这是很久以前在一些校园访谈中提出的一个问题。 无论如何，今天有人问了一些关于操纵的问题，并且在答复中提到了斯坦福的一些小动作 。 我花了一些时间研究它，并认为实际上可能会有这个问题的答案。 我不知道，我找不到一个。 有答案吗？
这是我前段时间为了好玩而写的。 它使用一个二进制补码表示法，并通过重复的移位来实现加法运算，主要通过加法实现其他运算符。
#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; } 或者，与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
当你添加1和3时，两个数字都有1位的设置，所以1 + 1的总和。 下一步你加2到2，并进行正确的总和四。 这导致退出
>>> add(1,3) 2 2 4 0 4
还是一个更复杂的例子
>>> add(45, 291) 66 270 4 332 8 328 16 320 336
编辑：为了在签名数字上轻松工作，您需要在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
试试
add(-1, 1)
看到一个单一的位遍历整个范围，并溢出了32次迭代
4294967294 2 4294967292 4 4294967288 8 ... 4294901760 65536 ... 2147483648 2147483648 0 0 0L
int Add(int a, int b) { while (b) { int carry = a & b; a = a ^ b; b = carry << 1; } return a; }
您可以将加法器电路转换为algorithm。 他们只做按位操作=）
那么，用布尔运算符来实现一个等价物是非常简单的：你用一个和（这是一个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; }
你已经得到了一些操纵答案。 这是不同的。
在C中， arr[ind] == *(arr + ind) 。 这可以让我们做一些轻微混淆（但合法）的事情，如int arr = { 3, 1, 4, 5 }; int val = 0[arr]; int arr = { 3, 1, 4, 5 }; int val = 0[arr]; 。
所以我们可以定义一个自定义的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]); }
或者，如果我们想避免这个诡计，并且通过算术运算符，他们包括| ， &和^ （所以不允许直接的位操作），我们可以通过查找表来实现：
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; }
所有的算术运算都可以分解为按位运算，在电子学中使用NAND，AND，OR等门。
加法器的组成可以在这里看到 。
对于无符号数，使用与第一类相同的加法algorithm，但是以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)
如果你感觉喜剧，总是有这种非常可怕的方法来添加两个（相对较小）的无符号整数。 代码中的任何地方都没有算术运算符
在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; }
在C中，使用stdio（在Microsoft编译器上用_snprintfreplacesnprintf）：
#include <stdio.h> unsigned int JokeAdder(unsigned int a, unsigned int b) { return snprintf(NULL, 0, "%*.*s%*.*s", a, a, "", b, b, ""); }
这是一个紧凑的C解决scheme。 有时recursion比循环更可读。
int add(int a, int b){ if (b == 0) return a; return add(a ^ b, (a & b) << 1); }
#include<stdio.h> int add(int x, int y) { int a, b; do { a = x & y; b = x ^ y; x = a << 1; y = b; } while (a); return b; } int main( void ){ printf( "2 + 3 = %d", add(2,3)); return 0; }
short int ripple_adder(short int a, short int b) { short int i, c, s, ai, bi; c = s = 0; for (i=0; i<16; i++) { ai = a & 1; bi = b & 1; s |= (((ai ^ bi)^c) << i); c = (ai & bi) | (c & (ai ^ bi)); a >>= 1; b >>= 1; } s |= (c << i); return s; }
## to add or subtract without using '+' and '-' ## #include<stdio.h> #include<conio.h> #include<process.h> void main() { int sub,a,b,carry,temp,c,d; clrscr(); printf("enter a and b:"); scanf("%d%d",&a,&b); c=a; d=b; while(b) { carry=a&b; a=a^b; b=carry<<1; } printf("add(%d,%d):%d\n",c,d,a); temp=~d+1; //take 2's complement of b and add it with a sub=c+temp; printf("diff(%d,%d):%d\n",c,d,temp); getch(); }
以下将工作。
x - (-y)
这可以recursion地完成：
int add_without_arithm_recursively(int a, int b) { if (b == 0) return a; int sum = a ^ b; // add without carrying int carry = (a & b) << 1; // carry, but don't add return add_without_arithm_recursively(sum, carry); // recurse }
或者迭代地：
int add_without_arithm_iteratively(int a, int b) { int sum, carry; do { sum = a ^ b; // add without carrying carry = (a & b) << 1; // carry, but don't add a = sum; b = carry; } while (b != 0); return a; }
代码实现添加，不使用+ ， *运算符的乘法; 用于减去通过1的补码+1的数字来add函数
#include<stdio.h> unsigned int add(unsigned int x,unsigned int y) { int carry=0; while (y != 0) { carry = x & y; x = x ^ y; y = carry << 1; } return x; } int multiply(int a,int b) { int res=0; int i=0; int large= a>b ? a :b ; int small= a<b ? a :b ; for(i=0;i<small;i++) { res = add(large,res); } return res; } int main() { printf("Sum :: %u,Multiply is :: %d",add(7,15),multiply(111,111)); return 0; }
这个问题问如何添加两个数字，所以我不明白为什么所有的解决scheme提供了两个整数？ 如果这两个数字是浮动的，即2.3 + 1.8 ，他们也不被视为数字？ 无论是问题需要修改还是答案。
对于浮点数，我认为数字应该被分解成它们的分量，即2.3 = 2 + 0.3那么0.3应该被转换为一个整数表示乘以指数因子，即0.3 = 3 * 10^-1对于另一个数字然后使用移位方法给出的移位方法之一添加整数段，作为解决scheme，在处理情况之后给予单位数字位置，即2.7 + 3.3 = 6.0 = 2+3+0.7+0.3 = 2 + 3 + 7x10^-1 + 3x10^-1 = 2 + 3 + 10^10^-1 （这可以作为两个单独的加法来处理2+3=5 ，然后5+1=6 ）
int add_without_arithmatic(int a, int b) { int sum; char *p; p = (char *)a; sum = (int)&p[b]; printf("\nSum : %d",sum); }
通过上面给出的答案，可以用单行代码完成：
int add(int a, int b) { return (b == 0) ? a : add(a ^ b, (a & b) << 1); }
我认为这个代码将有助于添加两个数字没有加运算符
#include<stdio.h> int main() { int a, b, c; printf("enter two no. : "); scanf("%d%d", &a, &b); c = (a - ~b - 1); printf("%d\n", c); return 0; }
