### 常見的位操作實現 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 該文章給出了大數的運算[大數運算](http://blog.csdn.net/u013074465/article/details/41253429) ### 加法操作 實現加法操作使用”異或“和”與“來實現。對應位的異或操作可以得到該位的值，對應位的與操作可以產生該位對高位的進位值。 ~~~ //加法 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; } ~~~