位操作实现加减乘除

爱被打了一巴掌 2022-06-10 08:07 180阅读 0赞

一、位操作实现加法

分析，1）不考虑进位实现算法2）加上进位

//递归实现
        int BinaryAddTraverse(int num1, int num2) {
            if (num2 == 0) return num1;//没有进位的时候完成运算
            int sum, carry;
            sum = num1 ^ num2;//完成第一步没有进位的加法运算
            carry = (num1 & num2) << 1;//完成第二步进位并且左移运算
            return BinaryAddTraverse(sum, carry);//进行递归，相加
        }
    
        //非递归实现
        int BinaryAdd(int a, int b) {
            int add;
            int carry;
            do {
                add = a ^ b;
                carry = (a & b) << 1;
                a = add;
                b = carry;
            } while (carry != 0);
            return add;
        }

二、位操作实现减法

负数用补码表示，用加法加起

补码： ~a+1

int BinarySub(int a, int b) {
            return BinaryAdd(a, BinaryAdd(~b, 1));
        }

三、 位操作实现乘法

对于正负乘数，统一使用正数来乘，乘数的每一位，分别乘以被乘数（被乘数按照位数移位），然后将这些数求和即得到最终结果。 当然负数需要添加符号

![Center][]

int BinaryMultiply(int a, int b) {
            boolean neg = (b < 0);
            if (b < 0)
                b = -b;
            int sum = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < 32; i++) {
                map.put(1 << i, i);
            }
    
            while (b > 0) {
            /*
            b & ~(b - 1)可以得到乘数b的二进制表示中最右侧1的位置
            last_bit记录被乘数a需要位移的位数
            */
                int last_bit = map.get(b & ~(b - 1));
                //将得到的乘法结果全部相加即为最后结果
                sum += (a << last_bit);
                b &= b - 1; //每次将b的二进制表示的最右侧1去掉用于下一次乘法
            }
            if (neg)
                sum = -sum;
            return sum;
        }

四、位操作符实现除法

例如：求101011除以11：

![Center 1][]

1）将除数左移，直到大于被除数，

2）将被除数与左移后的除数相减得到下一轮的被除数，在除数右移的过程中，如果还是大于被除数则商0，继续右移。

int BinaryDivide(int a, int b){
            boolean 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;
        }

[Center]: /images/20220610/ea15b4d0158f4b98ac25ef2628f4dacb.png
[Center 1]: /images/20220610/ce1caa11df9f4275bede7577cda40911.png