位操作实现加减乘除四则运算

ゝ一纸荒年。 2022-08-06 10:19 191阅读 0赞

## 常见的位操作实现 ##

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

该文章给出了大数的运算[大数运算][Link 1]

## 加法操作 ##

实现加法操作使用”异或“和”与“来实现。**对应位的异或操作可以得到该位的值，对应位的与操作可以产生该位对高位的进位值。**

//加法
    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));
    }

## 乘法操作 ##

二进制的乘法与十进制原理类似：都是将乘数的每一位和被乘数的每一位依次相乘，然后将相乘的结果相加即可。

例如：

![Center][]

可以看出，乘法过程：如果乘数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：

![Center 1][]

在上图的除法过程中：

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

![Center 2][]

[Link 1]: http://blog.csdn.net/u013074465/article/details/41253429
[Center]: /images/20220806/279b55a64c4946e7b7158ae2e22e4d02.png
[Center 1]: /images/20220806/97cb579b9fd540f5872b05cbfdf5370f.png
[Center 2]: /images/20220806/dfb972a80eb6430588f5b611393ae3aa.png