首页 > 代码库 > 位操作实现加减乘除四则运算
位操作实现加减乘除四则运算
常见的位操作实现
1. 常用的一个等式:-n = ~(n - 1) = ~n + 1
2. 获取整数的二进制的最右边的1:n & (-n) 或 n & ~(n - 1)。例如 n = 010100, -n = 101100,那么n & (-n) = 000100
3. 去除整数的二进制的最右边的1:n & (n - 1)。例如 n = 010100,n-1 = 010011,n&(n-1) = 010000
加法操作
实现加法操作使用”异或“和”与“来实现。对应位的异或操作可以得到该位的值,对应位的与操作可以产生该位对高位的进位值。
//加法 int BinaryAdd(int a, int b) { int carry, add; do { add = a ^ b; //该操作得到本位的加法结果 carry = (a & b) << 1; //该操作得到该位对高位的进位值 a = add; b = carry; } while (carry != 0); //循环直到某次运算没有进位,运算结束 return add; }
减法操作
减法操作可以用加法操作来实现。例如 a - b = a + (-b) = a + (~b + 1)
//减法 int BinarySub(int a, int b) { return BinaryAdd(a, BinaryAdd(~b, 1)); }
乘法操作
二进制的乘法与十进制原理类似:都是将乘数的每一位和被乘数的每一位依次相乘,然后将相乘的结果相加即可。
例如:
可以看出,乘法过程:如果乘数b的第i(i >= 1;i = 1是乘数最右侧的那一位)位为1,那么该位与被乘数a相乘的结果S[i]就是(a << i);然后将这些所有的结果S[i]相加即为最后结果。
/*乘法 该过程中的bit_map是为了快速得到乘法过程中某位相乘的中间结果S[i] 需要位移的位数。bit_map的键值是2^0, 2^1,2^2, ……之类的数,对应的 值是0,1,2,……(即需要位移的位数)。 */ int BinaryMultiply(int a, int b) { bool neg = (b < 0); if(b < 0) b = -b; int sum = 0; map<int, int> bit_map; for(int i = 0; i < 32; i++) { bit_map.insert(pair<int, int>(1 << i, i)); } while(b > 0) { /* b & ~(b - 1)可以得到乘数b的二进制表示中最右侧1的位置 last_bit记录被乘数a需要位移的位数 */ int last_bit = bit_map[b & ~(b - 1)]; //将得到的乘法结果全部相加即为最后结果 sum += (a << last_bit); b &= b - 1; //每次将b的二进制表示的最右侧1去掉用于下一次乘法 } if(neg) sum = -sum; return sum; }
除法操作
例如:求101011除以11:
在上图的除法过程中:
(1)第一次除法先找到除数应该左移的位数,使得除数是不大于除数的数,上图中将除数左移了三位(11<< 3 = 11000),变为11000;然后本次除法结果为(1 << 3);被除数变为了原来的被除数101011 减去当前的除数11000:10011,该被除数就是下一次除法的被除数。
(2)第二次除法的被除数为10011,此次的除数为上一次除法右移一位,即(原始除数11左移两位:11<<2 = 1100);本次除法结果为(1<<2);被除数变为10011 - 1100 = 111,这作为下一次除法的被除数。
(3)第三次除法的被除数变为111,除数是上一次除法右移一位,也就是初始除数11左移一位(11<< 1 = 110);本次除法结果为(1<<1);被除数为111 - 110 = 1;
(4)乘法结束。商为(1 << 3 + 1 << 2 + 1 << 1) = 1000 + 100 + 10 = 1110 = 14。
代码如下:
//除法 int BinaryDivide(int a, int b){ bool neg = (a > 0) ^ (b > 0); if(a < 0) a = -a; if(b < 0) b = -b; if(a < b) return 0; int msb = 0; //msd记录除数需要左移的位数 for(msb = 0; msb < 32; msb++) { if((b << msb) >= a) break; } int q = 0; //记录每次除法的商 for(int i = msb; i >= 0; i--) { if((b << i) > a) continue; q |= (1 << i); a -= (b << i); } if(neg) return -q; return q; }
测试
int main() { int a, b; cin >> a >> b; cout << "和: " << BinaryAdd(a, b) << endl; cout << "差: " << BinarySub(a, b) << endl; cout << "积: " << BinaryMultiply(a, b) << endl; cout << "商: " << BinaryDivide(a, b) << endl; }
位操作实现加减乘除四则运算