位运算实现乘除法
1、基础知识
对于任何十进制正整数 K :
设其二进制为 “bn…b2b1b0”（其中 bi 为二进制某位值，i∈[0,n] ）
二进制数：K = b0 * 2^0 + b1 * 2^1 + b2 * 2^2 + … + bn * 2^n
故乘二有：K = b0 * 2^1 + b1 * 2^2 + b2 * 2^3 + … + bn * 2^(n+1)
即左移一：K = 00 * 2^0 + b0 * 2^1 + b1 * 2^2 + … + bn * 2^(n+1)
同理除二：K = b0 *2^-1 + b1 * 2^0 + b2 * 2^1 + … + bn * 2^(n-1)
即左移一：K = b1 * 2^0 + b2 * 2^1 + b3 * 2^2 + … + bn * 2^(n-1)
舍最低位：K = (整数除) + b1 * 2^0 + b2 * 2^1 + … + bn * 2^(n-1)
根据以上可知：
除2 = 右移1位； 乘2 = 左移1位
除4 = 右移2位； 乘4 = 左移2位
除8 = 右移3位； 乘8 = 左移3位
…
2、整数乘法
通常如果需要乘以或除以2的n次方，都可以用移位的方法代替，大部分的C编译器,用移位的方法得到代码比调用乘除法子程序生成的代码效率高。 实际上，只要是乘以或除以一个整数才可以用移位的方法得到结果。
例如：
a=a*9 => a=a*(8+1) => a=a*8 + a*1 => a=(a<<3)+a
a=a*7 => a=a*(8–1) => a=a*8 – a*1 => a=(a<<3)–a
a=a*7 => a=a*(4+2+1) => a=a*4 + a*2 + a => a=(a<<2)+(a<<1)+a
a=a*10 => a=a*(8+2) => a=a*8 + a*2 => a=(a<<3)+(a<<1)
long long multiple(int num1, int num2)
{if (num1 == 0 || num2 == 0){return 0;}bool sign = false;if (num1 < 0 && num2 < 0 ||num1 > 0 && num2 > 0){ //记录结果符号sign = true;}long long first = abs((long long)num1);long long second = abs((long long)num2);if (first < second){ //操作小的num2，逐位判断long long temp = first;first = second;second = temp;}//两个int相乘不能超过一个longlong的范围，防溢出long long ans = 0; for (size_t i = 0; i < 32; i++){ //从低位取值bool isOne = (second >> i) & 0x01;if (isOne){ans += first << i;}}return sign ? ans : -ans;
}
3、整数除法
位移配合相减实现，例如：91(1011011) / 14(1110) 的过程如下：
| 被除数位数 | 减除数 | 结果 | 商 | 余数 | 左移 |
|---|---|---|---|---|---|
| 1 | 1 | 不够减 | 0 | 1 | 10 |
| 0 | 10 | 不够减 | 0 | 10 | 101 |
| 1 | 101 | 不够减 | 0 | 101 | 1011 |
| 1 | 1011 | 不够减 | 0 | 1011 | 10110 |
| 0 | 10110 | 够减 | 1 | 1000 | 10001 |
| 1 | 10001 | 够减 | 1 | 11 | 111 |
| 1 | 111 | 不够减 | 0 | 111 | 完毕 |
所以有：1011011 = 1110 * 0000110 + 111 。
也就是：91 = 14 * 6 + 7。
过程实现如下：
long long divide(int dividend, int divisor)
{if (dividend == 0){return 0;}bool sign = false;if (dividend < 0 && divisor < 0 ||dividend > 0 && divisor > 0){ //记录结果符号sign = true;}long long first = abs((long long)dividend);long long second = abs((long long)divisor);if (first < second){return 0;}long long bit_sum = 1;int first_bit_count = 0;while (bit_sum <= first){ //获取dividend位数bit_sum <<= 1;++first_bit_count;}long long ans = 0;long long remainder = 0;while (first_bit_count--){bit_sum >>= 1;remainder <<= 1;remainder |= (first >> first_bit_count) & 0x01;if (remainder >= second){remainder -= second;ans |= bit_sum;}}return sign ? ans : -ans;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！