LeetCode 371.Sum of Two Integers 位运算实现加法(减法)

1.原题

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.

2.思路

不允许用+、-操作符,那么暂且只能想到位运算来入手。
1.”&”与操作符, 2 (0010) & 7 (0111) => 2 (0010)
“^” XOR(异或) operation, 2 (0010) ^ 7 (0111) => 5 (0101)
2. a+b 不考虑进位的话则是相当于 a xor b的操作。(0001+0011=0010 不考虑进位)
3. 进位则可以看做 (a & b) << 1.
4. 因此模仿a+b的真实操作则是,(a xor b) + ( (a&b)<<1 ),这时候如果( (a&b)<<1 )进位不为0,那么肯定要继续相加,所以可以递归调用,也可以while循环直到进位为0的时候。

3.AC解

public class Solution {
    public int getSum(int a, int b) {
        if(a==0) return b;
        if(b==0) return a;

        int carry = 0;
        while(b!=0){
            carry = a & b; 
            a = a ^ b;  //xor位相加不进位,并赋给a
            b = carry << 1; //计算进位,并赋给b,然后循环 a+b,直到b为0,无进位
        }
        return a;
    }
}

4.优秀Discuss

// Iterative
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }

    return a;
}

// Iterative减法
public int getSubtract(int a, int b) {
    while (b != 0) {
        int borrow = (~a) & b;
        a = a ^ b;
        b = borrow << 1;
    }

    return a;
}

// Recursive
public int getSum(int a, int b) {
    return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

// Recursive
public int getSubtract(int a, int b) {
    return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}

// Get negative number
public int negate(int x) {
    return ~x + 1;
}
全部评论

相关推荐

06-07 17:17
嘉兴学院 教师
心爱的idea:你孩
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务