问题描述:在不使用运算符的情况下,实现简单的A+B问题。
重点:
- 不使用常规运算符 【+-×/】
- 计算A+B的值
主要考点:
- 二进制位运算
- 相关位运算符的使用
- 进位计算的基础知识点
算法公式:
- a+b = (a ^ b) + ( (a & b ) << 1 )
- 设sum = a ^ b;carryBit =(a & b ) << 1
- 则可以得到:a+b=sum+carryBit
- 由二进制进位规则可知,carryBit在N次进位后,最终值终为0,则式1可简化为a+b=sum+(0)
- 由4可知未知数N在carryBit不为0(carryBit始终为正整数)时始终有解
- 以此可得出最终结论:a + b = N(由(a & b )进位可得)= 0 => a ^ b
实现代码:
public int aplusb(int a,int b){
while(b!=0){
/**
* a^b(a异或b:a,b中不同则为1,相同则为0)
* 即13^9 = 【前位补0】100 = 4,不考虑进位
*/
int sum = a^b;
/**
* a&b(a位与b:a,b中相同则为1,不同则为0)
* 即13+9 = 【前位补0】1001 = 9,只考虑进位
* 不论位与的结果值大值小,进位的最终值始终为0,所以只需要循环进位至0即可
*/
int carryBit = (a&b) << 1;
/**
* 当carryBit进位至0时,a^b即是a+b最终的结果
*/
a=sum;
b=carryBit;
}
return a;
}
运算结果:
//第一次运算
a^b:4
(a&b) << 1:18
toBinary a^b:100
toBinary (a&b) << 1:10010
//第二次运算
a^b:22
(a&b) << 1:0
toBinary a^b :10110
toBinary (a&b) << 1:0
result = 22