程序员面试金典17.01-不用加号的加法

原题(来源Leetcode)

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

示例:

输入: a = 1, b = 1
输出: 2

提示:

  • a, b 均可能是负数或 0
  • 结果不会溢出 32 位整数

解法

思想

位运算,如果把两个数看作二进制,异或之后的结果就是未算入进位部分的结果。而需要进位的数可以通过两个数的与运算得到。

代码

class Solution {
    public int add(int a, int b) {
        int sum = 0, carry = 0;
        while(b != 0) {
            sum = a ^ b;            // 异或计算未进位的部分
            carry = (a & b) << 1;   // 进位部分
            a = sum;                // 保存未进位部分,再次计算
            b = carry;              // 保存进位部分,再次计算
        }
        return a;    // 最后无进位,异或的结果即加法结果
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e7%a8%8b%e5%ba%8f%e5%91%98%e9%9d%a2%e8%af%95%e9%87%91%e5%85%b817-01-%e4%b8%8d%e7%94%a8%e5%8a%a0%e5%8f%b7%e7%9a%84%e5%8a%a0%e6%b3%95/

发表回复

登录后才能评论