Bit Manipulation is a topic that is not easy to come up with without specific memory. So I conclude the useful conclusions and some typical problems here.

Conclusions

$$a\oplus 0=a$$

$$a\oplus a=0$$

$$a\oplus b\oplus a=(a\oplus a)\oplus b=0\oplus b=b$$

Problems

1. LeetCode 371

Description

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.

Analysis

We know computer operations is based on bit manipulation. So if some decimal operators are not permitted, we could be easy to come up with bit operators.

Considering about bit manipulation, we can analysis the sum of two binary numbers \(a\) and \(b\). They could be \(0\) or \(1\).

$$0+0=00$$

$$0+1=01$$

$$1+0=01$$

$$1+1=10$$

We can conclude that the higher digit is \(a\&b\) and the lower digit is \(a\oplus b\). So we can extend the conclusion to decimal numbers. Because decimal numbers is the sequence of many binary numbers.

Solution

class Solution {
    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;
    }
}

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/SumofTwoIntegers.java

[2] https://www.bilibili.com/video/av8810638

[3] https://www.bilibili.com/video/av8829564

Leave a Reply

Your email address will not be published. Required fields are marked *