Java位运算实现四则运算


一直以来对位运算不熟悉,最近做到 leetcode 里 easy 模式(捂脸)的 sum of two integers ,感觉没头绪。所以好好学习了一下JAVA里的位运算。

Add


Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example: Given a = 1 and b = 2, return 3.

先从这个题说起。

比如说 5 + 17, 转换为二进制分别是 101_{[2]}10001_{[2]},直接相加不进位,结果是 10100_{[2]} = 20_{[10]}。如果只算进位的话,结果是 10_{[2]} = 2_{[10]}。结果是正确的,证明我们的思路可行。那么怎么用位运算实现二进制的运算呢?

算和不带进位的时候,0与1,1与0都会得到1,1与1,0与0都会得到0,这是典型的异或(XOR)运算,在 JAVA 中用 “^” 符号来表示。这样一来,sum = a ^ b

算进位的时候,只有1与1会产生1,其他都会产生0,这是典型的位与运算,并且往左移一位。所以carry = a & b

所以采用递归我们可以写出代码。

public class Solution {
    public int getSum(int a, int b) {
    	if (b == 0) {
    		return a;
    	}
    	
    	int sum = a ^ b;
    	int carry = (a & b) << 1;
    		
    	return getSum(sum, carry);
    }
}

也可以很简单的改写成非递归。

public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = a ^ b;
            b = (a & b) << 1;
            a = carry;
        }
        return a;
    }
}

Sub


计算机内的减法采用补码减法。

(x-y)_C = x_C - y_C = x_C + (-y)_C

而取补码是用“求反并在最末尾加1”实现的。所以我们实现减法。

int neg(int a) {
	return add(~a, 1);
}

int sub(int a, int b) {
	return add(a, neg(b));
}

Mul


这个很简单了,先看看 b 的末位是不是1,是的话就加上 a,然后 a 左移,b 右移。

int mul(int a, int b) {
	int res = 0;
	while (b != 0) {
		if (b & 1 != 0) {
			res = add(res, a);
		}
		a = (a << 1);
		b = (b >> 1);
	}
	return res;
}

Div


除法事实上就是乘法倒过来。

int div(int a, int b) {
	int res = 0;
	for (int i = 32; i >= 0 ; i--) {
		if ((a >> i) > b) {
			res += (1 << i);
			a -= (y << i);
		}
	}
	return res;
}