CloudLander's Blog
0%

只用位运算不用算术运算实现整数的加减乘除运算

发表于 分类于

只用位运算不用算术运算实现整数的加减乘除运算

给定两个32位整数a和b，可正，可负，可0，不能使用算术运算符，分别实现a和b的加减乘除运算
不考虑溢出

用位运算实现加法

如果不考虑进位，a^b就是正确结果。
在只算进位的情况下，也就是只考虑a加b的过程中进位产生的值是什么，结果就是(a&b)<<1，因为在第i位只有1与1相加才会产生进位。

把完全不考虑进位的相加值与只考虑进位的产生值再相加，就是最终的结果，也就是说，一直重复这样的过程，直到进位产生的值完全消失，说明所有的过程都加完了。

1
2
3
4
5
6
7
8
public int add(int a, int b){
    int sum=a;
    while(b!=0){
        sum = a^b;
        b = (a&b)<<1;
        a = sum;
    }
}

用位运算实现减法运算

实现a-b只要实现a+(-b)即可，根据二进制数在机器中表达的规则，得到一个数的相反数，就是这个数的二进制数表达取反加1的结果，，得到b的相反数-b后，再与a进行加法

1
2
3
4
5
6
7
int negNum(int n){
    return add(~n, 1);
}

public int minus(int a, int b){
    return add(a, negNum(b));
}

用位运算实现乘法运算

a×b的结果可以写成：a×2^0×b0+a×2^1×b1+…+a×2^31×b31
其中，bi为0或1代表整数b的二进制数表达中第i位的值，

举例：a=22=000010110，b=13=000001101，res=0
b的最右侧为1，所以res=res+a，同时b右移一位，a左移一位(左移一位即乘2)
a=000101100, b=000000110
b最右侧为0，所以res不变，b右移一位，a左移一位
a=001011000，b=000000011
b最右侧为1，res=res+a，同时b右移一位，a左移一位。
a=010110000，b=000000001
b最右侧为1，res=res+a，同时b右移一位，a左移一位。
a=101100000，b=000000000
此时b为0，过程停止，返回res=100011110，即286
不管a和b是正，负，还是0，上述过程都是对的，因为都满足a×2^0×b0+a×2^1×b1+…+a×2^31×b31

1
2
3
4
5
6
7
8
9
10
11
public int multi(int a, int b){
    int res = 0;
    while(b!=0){
        if((b&1)!=0){
            res = add(res,a);
        }
        a << =1;
        b >>> = 1;
    }
    return res;
}

用位运算实现除法运算，其实就是乘法的逆运算。

其实就是找到a能包含的最大部分（指b* 2^x ）然后让a减去这个最大部分，再让剩下的a找到次大部分，并依次找下去。以上过程只适用于a和b都不是负数的时候，所以，如果a和b中有一个为负数或都为负数时，可以先把a和b转成正数，计算完后再看res的真实符号是什么就可以。

1
2
3
4
5
6
7
8
9
10
11
12
public int div(int a, int b){
    int x = isNeg(a)?negNum(a):a;
    int y = isNeg(b)?negNum(b):b;
    int res = 0;
    for(int i=31; i > -1; i= minus(i, 1)){
        if((x>>i)>=y){
            res |= (1<<i);
            x = minus(x, y<<i);
        }
    }
    return isNeg(a) ^ isNeg(b)?negNum(res):res;
}

上述方法可以计算绝大多数情况，但32位整数最小值为-2147483648，最小值的绝对值比最大值的绝对值大1，所以，如果a或b等于最小值，是转不成相应正数的，总结如下：
1.如果a和b都不为最小值，直接使用上述过程，返回div(a,b)
2.如果a和b都为最小值，a/b的结果为1，直接返回1
3.如果a不为最小值，b为最小值，a/b结果为0，直接 返回0
4.如果a为最小值，b不为最小值，只能把最小值增加一点，计算出一个结果，然后根据这个结果修正一下，得到最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int divide(int a, int b){
    if (b==0) {
        throw new RuntimeException("divisor is 0");
    }
    if(a==Integer.MIN_VALUE && b==Integer.MIN_VALUE){
        return 1;
    }else if(b==Integer.MIN_VALUE){
        return 0;
    }else if(a==Integer.MIN_VALUE){
        int res = div(add(a, 1), b);
        return add(res, div(minus(a, multi(res, b)), b));
    }else{
        return div(a, b);
    }

}