这个题是leetcode里面的一个经典面试题，整理了几种比较经典的实现方法。
１、加法
要实现加法操作可以分为两步：
（１）不进位部分的加法用ａ^ b；
（２）进位部分的加法用（ａ＆ｂ）<< 1;
递归实和非递归现方法实现如下：
//加法 //(递归方法) int getAddNumber(int a, int b) { if (b == 0) return a; int sum = a^b; //可以得到进位 int carray = (a & b) << 1; return getAddNumber(sum, carray); } //(非递归方法) int getAddNumber1(int a, int b) { while (b) { // 防止 AddressSanitizer 对有符号左移的溢出保护处理 auto c = ((unsigned int)a & b) << 1; a = a ^ b; b = c; } return a; } int getAddNumber2(int a, int b) { int sum; int carry; if (a == 0) return b; if (b == 0) return a; carry = a & b; sum = a ^ b; while (carry) { int temp = sum; //最高位为1即负数左移会报错, 使carry最高位永远为0 carry = carry & (-1); sum = sum ^ (carry << 1); carry = temp & (carry << 1); } return sum; }２、减法
要实现减法首先的有补码相关的知识：补码相关知识
我们分以下几步来看：（以a - b为例）
(1) 如果b 的值为0，那么结果显而易见就是a 了。
(2) b 不为0 的情况下，我们仍然先不考虑借位，先将被减数和减数同为1 的位置去掉。
第一步，找出减数和被减数同为1 的位置。可使用 sameNum = a&b;
第二步，分别将被减数和减数同为1 的位置去掉1 ，这里可以用
a ^= sameNum; b ^= sameNum;
(3) 此时，减数和被减数相同位只存在以下三种情况：
被减数：0 ；减数： 0；差：0；被减数：0 ；减数： 1；差：1；被减数：1 ；减数： 0；差：1；(4) 通过对被减数、减数和差的分析，很容易就能知道差值应该是被减数和减数的按位或的结果。于是我们便有：a | b 得到临时的结果;
(5) 此时再考虑借位问题。很明显只有在减数为1的情况下，被减数与之对应的左一位才会出现借位，于是借位便可以用 b << 1 ; 来表示。
(6) 再把临时结果减去借位，直到借位为0,得到的结果便是最终的结果了。
//减法 int getSubNUm(int a, int b) { while (b != 0) { // 去掉被减数和减数中同为1的位 int sameNum = a & b; a ^= sameNum; b ^= sameNum; // 此时，a 和 b 不存在同时为1 的位 // 0 - 1 和 1 - 0 都为1 a |= b; // 得到相减的临时结果（不考虑借位） b = b << 1; // 减数为1 时，必有借位 } return a; }3、乘法
（1）先考虑正整数之间的乘法运算
在二进制中，每向左移动一次，都相当于原始数乘以2。而每个数据都可以写成k0×20+k1×21+...+km×2m的形式。因此我们可以得到以下式子：
a x b = ax20xk0 + ax21xk1 + .... + ax2mxkm 其中ki = {0, 1};
（2）其次就是要考虑正负号（溢出问题）
这里可以直接判断a、b和0 的关系来判断正负，也可以做左移操作，因为计算机中数据都是以补码的数据存储的，其中正数和负数的区别便是最高位是否为1；（负数的补码最高位为1）；
int maxNumFlag() { int bitsOfByte = 8; int maxNum = 0x80; int tmp = maxNum; while (tmp != 0) { maxNum = tmp; tmp <<= bitsOfByte; } return maxNum; } //乘法 int getMultip(int a, int b) { // 1.先只考虑正整数的相乘 // 2.考虑正负情况和溢出问题 int maxNum = maxNumFlag(); int flag_a = 1; if ((maxNum & a) != 0) { flag_a = 0; // 负数 a = getAddNumber(~a, 1); } int flag_b = 1; if ((maxNum & b) != 0) { flag_b = 0; b = getAddNumber(~b, 1); } int result = 0; for (int bits = 1; bits != 0; bits <<= 1) { if ((bits & b) != 0) { result = getAddNumber(result, a); if ((result & maxNum) != 0 || (a & maxNum) != 0) { cout << "数据过大！" << endl; } } a <<= 1; } return (flag_a ^ flag_b) == 0 ? result : getAddNumber(~result, 1); }4、除法
第一种方法：除法没有溢出，但是有其他的限定条件，比如除数不能为“0”。
这里先说下除法和减法之间的关系。以97÷23=4（余5）为例：
也就是 97-23×4=5
：=》97-23-23-23-23 = 5
//除法 int getDivision(int a, int b) { if (b == 0) { cout<< "除数不能为0！！"<< endl; } int maxNum = maxNumFlag(); int flag_a = 1; if ((maxNum & a) != 0) { flag_a = 0; // 负数 a = getAddNumber(~a, 1); } int flag_b = 1; if ((maxNum & b) != 0) { flag_b = 0; b = getAddNumber(~b, 1); } int index = 1; int tmp = getSubNUm(a, b); if (tmp < 0) { return 0; } while (tmp >= b) { tmp = getSubNUm(tmp, b); // 最后一次循环后的tmp 便是a/b 的余数 index = getAddNumber(index, 1); } return (flag_a ^ flag_b) == 0 ? index : getAddNumber(~index, 1); }第二种方法：思路如下：
预备工作：置商为0；判断“被除数>=除数 ”是否成立：成立，继续步骤3；
不成立，被除数的值赋给余数，计算结束。
备份除数，并设置商分子（一个临时变量，最终需加到商上面，故暂且如此命名）为1；对商分子和除数同步向左移位，直到继续移位将大于被除数时为止；
从被除数上减去除数，并将商加上商分子。通过备份的除数值还原除数，跳转到步骤2继续执行。 int getDivision1(int a, int b) { if (b == 0) { cout<< "除数不能为0！！"<< endl; } int maxNum = maxNumFlag(); int flag_a = 1; if ((maxNum & a) != 0) { flag_a = 0; // 负数 a = getAddNumber(~a, 1); } int flag_b = 1; if ((maxNum & b) != 0) { flag_b = 0; b = getAddNumber(~b, 1); } int quotient = 0; int backupB = b; while (a >= b) { int tempB = b << 1; int tempQ = 1; while ((tempB <= a) && ((tempB & maxNumFlag()) == 0)) { b = tempB; tempQ <<= 1; tempB <<= 1; } a = getSubNUm(a, b); quotient |= tempQ; b = backupB; } if (((maxNum & a) != 0) && (a != 0)) { quotient = getAddNumber(quotient, 1); } return (flag_a ^ flag_b) == 0 ? quotient : getAddNumber(~quotient, 1); }完整实现的代码：
#include <iostream> using namespace std; //加法 //(递归方法) int getAddNumber(int a, int b) { if (b == 0) return a; int sum = a^b; //可以得到进位 int carray = (a & b) << 1; return getAddNumber(sum, carray); } //(非递归方法) int getAddNumber1(int a, int b) { while (b) { // 防止 AddressSanitizer 对有符号左移的溢出保护处理 auto c = ((unsigned int)a & b) << 1; a = a ^ b; b = c; } return a; } int getAddNumber2(int a, int b) { int sum; int carry; if (a == 0) return b; if (b == 0) return a; carry = a & b; sum = a ^ b; while (carry) { int temp = sum; //最高位为1即负数左移会报错, 使carry最高位永远为0 carry = carry & (-1); sum = sum ^ (carry << 1); carry = temp & (carry << 1); } return sum; } //减法 int getSubNUm(int a, int b) { while (b != 0) { // 去掉被减数和减数中同为1的位 int sameNum = a & b; a ^= sameNum; b ^= sameNum; // 此时，a 和 b 不存在同时为1 的位 // 0 - 1 和 1 - 0 都为1 a |= b; // 得到相减的临时结果（不考虑借位） b = b << 1; // 减数为1 时，必有借位 } return a; } int maxNumFlag() { int bitsOfByte = 8; int maxNum = 0x80; int tmp = maxNum; while (tmp != 0) { maxNum = tmp; tmp <<= bitsOfByte; } return maxNum; } //乘法 int getMultip(int a, int b) { // 1.先只考虑正整数的相乘 // 2.考虑正负情况和溢出问题 int maxNum = maxNumFlag(); int flag_a = 1; if ((maxNum & a) != 0) { flag_a = 0; // 负数 a = getAddNumber(~a, 1); } int flag_b = 1; if ((maxNum & b) != 0) { flag_b = 0; b = getAddNumber(~b, 1); } int result = 0; for (int bits = 1; bits != 0; bits <<= 1) { if ((bits & b) != 0) { result = getAddNumber(result, a); if ((result & maxNum) != 0 || (a & maxNum) != 0) { cout << "数据过大！" << endl; } } a <<= 1; } return (flag_a ^ flag_b) == 0 ? result : getAddNumber(~result, 1); } //除法 int getDivision(int a, int b) { if (b == 0) { cout<< "除数不能为0！！"<< endl; } int maxNum = maxNumFlag(); int flag_a = 1; if ((maxNum & a) != 0) { flag_a = 0; // 负数 a = getAddNumber(~a, 1); } int flag_b = 1; if ((maxNum & b) != 0) { flag_b = 0; b = getAddNumber(~b, 1); } int index = 1; int tmp = getSubNUm(a, b); if (tmp < 0) { return 0; } while (tmp >= b) { tmp = getSubNUm(tmp, b); // 最后一次循环后的tmp 便是a/b 的余数 index = getAddNumber(index, 1); } return (flag_a ^ flag_b) == 0 ? index : getAddNumber(~index, 1); } int getDivision1(int a, int b) { if (b == 0) { cout<< "除数不能为0！！"<< endl; } int maxNum = maxNumFlag(); int flag_a = 1; if ((maxNum & a) != 0) { flag_a = 0; // 负数 a = getAddNumber(~a, 1); } int flag_b = 1; if ((maxNum & b) != 0) { flag_b = 0; b = getAddNumber(~b, 1); } int quotient = 0; int backupB = b; while (a >= b) { int tempB = b << 1; int tempQ = 1; while ((tempB <= a) && ((tempB & maxNumFlag()) == 0)) { b = tempB; tempQ <<= 1; tempB <<= 1; } a = getSubNUm(a, b); quotient |= tempQ; b = backupB; } if (((maxNum & a) != 0) && (a != 0)) { quotient = getAddNumber(quotient, 1); } return (flag_a ^ flag_b) == 0 ? quotient : getAddNumber(~quotient, 1); } int main() { cout << getAddNumber(-2, 8) << endl; cout << getAddNumber1(10, 999999) << endl; cout << getAddNumber2(-2, -30) << endl; cout << getSubNUm(100, -3) << endl; cout << getMultip(-30, 6) << endl; cout << getDivision(42,3) << endl; cout << getDivision(9,2) << endl; return 0; }
