两整数之和
位运算 + 迭代计算每一位
-
解题思路：
- 从低位往高位进行处理，处理过程中使用变量 add 记录进位信息；
- 由于长度为 32 的二进制，所以循环 32 次，每次取 a、b 第 i 位的值 u1、u2；
- 记录进位信息：add = u1 + u2 + add > 1 ? 1 : 0;
- res 记录相加的结果：res |= (u1 ^ u2 ^ add) << i;
-
复杂度：
- 时间复杂度：O©，C 为常数，固定为 32；
- 空间复杂度：O(1)；
-
代码实现：
function getSum(a: number, b: number): number { let res = 0, add = 0; // 进位 for (let i = 0; i < 32; i++) { // 获取 a、b 二进制位第 i 位的值 let u1 = (a >> i) & 1, u2 = (b >> i) & 1; res |= (u1 ^ u2 ^ add) << i; // 判断是否进位 add = u1 + u2 + add > 1 ? 1 : 0; } return res; };
无进位相加 + 获取进位
-
解题思路：
- a ^ b 是无进位的相加；
- a & b 结果左移一位即可得到进位；
- 无进位的加法再加上进位就等于两个数相加，让无进位相加的结果与进位不断的异或，直到进位为 0；
-
复杂度：
- 时间复杂度：O©，C 为常数，固定为 32；
- 空间复杂度：O(1)；
-
代码实现：
function getSum(a: number, b: number): number { // 进位为 0，循环终止 while (b != 0) { // 相与为了让进位显现出来 const carry = (a & b) << 1; // 异或这里可看做是无进位相加 // 让无进位相加的结果与进位不断的异或，直到进位为0 a = a ^ b; b = carry; } return a; };
无进位相加 + 递归
-
复杂度：
- 时间复杂度：O©，C 为常数，固定为 32；
- 空间复杂度：O(1)；
-
代码实现：
function getSum(a: number, b: number): number { // a = (a & b) << 1; 进位 // b = a ^ b; 无进位相加 return a == 0 ? b : getSum((a & b) << 1, a ^ b); };
打赏作者
您的打赏是我前进的动力
微信
支付宝
67.二进制求和
上一篇
评论
