位运算实现四则运算

加法

异或运算 是一个无进位加法

int a = 46; //0101110
int b = 20; //0010100
System.out.println(a^b); //58 ==> 0111010
System.out.println(a&b); //4 ==> 0000100  进位位置
System.out.println((a&b) << 1);//8 ==>0001000   需要左移一位才是进位后的结果
//不断的无进位加法 + 进位信息 直到进行信息为空则为 加法

完整写法

	public static int add(int a,int b) {
		int sum = a;
		while (b != 0) { //直接进位信息为空
			sum = a ^ b; //无进位相加
			b = (a&b)<<1; // 进位信息
			a = sum; //a变成无进位信息 加法的结果
		}
		return sum;
	}

减法

a - b = a + (-b) = a + (~b + 1)

//减法
	public static int sub(int a,int b) {
		b = add(~b,1);
		return add(a,b);
	}

乘法

如果乘数当前位为 1，则取被乘数左移一位的结果加到最终结果中；如果当前位为 0，则取 0 加到乘积中

	//乘法
	public static int multiply(int a, int b) {
		int sum = 0;
		while (b != 0) {
			if ((b & 1) != 0) { //如果b 与 1 不等于0则需要相加
				sum = add(sum, a);
			}
			a = a << 1; //a左移一位0补全
			b = b >>> 1; //b右移一位
		}
		return sum;
	}

除法

	public static int div(int a, int b) {
		int x = a < 0 ? add(~a, 1) : a; // 判断是否为负数 如是则转为绝对值计算
		int y = b < 0 ? add(~b, 1) : b;
		int res = 0;
		for (int i = 30; i >= 0; i = add(i, -1)) { // i-- ==> add(i,-1)
			if ((x >> i) >= y) { // 如果x右移i位 >= 被除数 则进入分支
				res |= (1 << i); // 将倍数(位数)结果增加到ans中
				x = add(x, add(~y, 1) << i); // 减掉n倍的被除数
				
			}
		}
		return (a < 0 == b < 0) ? res : add(~res, 1); // 判断ab两数符号是否相等 不相等则返回相反数
	}

29. 两数相除 (opens new window)

	// 加法
	public static int add(int a, int b) {
		int sum = a;
		while (b != 0) { // 直接进位信息为空
			sum = a ^ b; // 无进位相加
			b = (a & b) << 1; // 进位信息
			a = sum; // a变成无进位信息 加法的结果
		}
		return sum;
	}

	// 减法
	public static int sub(int a, int b) {
		b = add(~b, 1); // 取反+1
		return add(a, b);
	}

	// 乘法
	public static int multiply(int a, int b) {
		int sum = 0;
		while (b != 0) {
			if ((b & 1) != 0) {
				sum = add(sum, a);
			}
			a = a << 1;
			b = b >>> 1;
		}
		return sum;
	}

	// 除法
	public static int div(int a, int b) {
		int x = a < 0 ? add(~a, 1) : a; // 判断是否为负数 如是则转为绝对值计算
		int y = b < 0 ? add(~b, 1) : b;
		int res = 0;
		for (int i = 30; i >= 0; i = add(i, -1)) { // i-- ==> add(i,-1)
			if ((x >> i) >= y) { // 如果x右移i位 >= 被除数 则进入分支
				res |= (1 << i); // 将倍数(位数)结果增加到ans中
				x = add(x, add(~y, 1) << i); // 减掉n倍的被除数
				
			}
		}
		return (a < 0 == b < 0) ? res : add(~res, 1); // 判断ab两数符号是否相等 不相等则返回相反数
	}

	public static int divide(int a, int b) {
		if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) { // a和b都为最小值 返回1
			return 1;
		} else if (b == Integer.MIN_VALUE) { // 被除数为最小值 返回0
			return 0;
		} else if (a == Integer.MIN_VALUE) { // 除数为最小值
			if (b == add(~1, 1)) { // 被除数为-1 返回最大值
				return Integer.MAX_VALUE;
			} else {
				int c = div(add(a, 1), b); // (a+1)/b = c
				int e = multiply(b, c); // b*c = e
				int f = add(a, add(~e, 1)); // a-(b*c) = f
				int q = div(f, b); // f/b = q
				return add(c, q); // c+q
			}
		} else {
			return div(a, b);
		}
	}