Unsigned can hold a larger positive value, and no negative value. uses the leading bit as a part of the value, while the signed version uses the left-most-bit to identify if the number is positive or negative.

XOR-- 不相等的才return 1

so if you want to get a negative number, you can simply do ~x + 1

无符号右移补0

右移相当于除2 要一直检查！= 0 >> 正的补0 负的补1

左移补0

Power of Two Trick n & (n - 1) == 0则 n是power of two (观察)

>>> 干嘛的？

The unsigned right-shift operator may also be useful when a computation would, arithmetically, yield a positive number between 0 and 4,294,967,295 and one wishes to divide that number by a power of two.

191. Number of 1 Bits

    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            count += (n & 1);
            n = n >>> 1;
        }
        return count;
    }
}

371. Sum of Two Integers

怎么想的？

169. Majority Element

Bit Manipulation: 出现超过一半的元素也可以通过每一位计算不是最快的但是比较好理解

We can iterate over the bits of all numbers and for every position find out if ones outnumber the zeros (among all numbers). If this is the case, the corresponding bit of the ret variable (which holds the result) is set. We essentially "construct" the number we look for.

因为只有“1”的时候才需要set

public class Solution {
    //Bit Manipulation
    public int majorityElement(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            int ones = 0, zeros = 0;
            for (int num : nums) {
                if ((num & (1 << i)) != 0) ++ones;
                else ++zeros;
            }
            if (ones > zeros) res |= (1 << i);
        }
        return res;
    }
}

Boyer–Moore majority vote algorithm：如果是我自己写肯定是hashmap

public class Solution {
    //Boyer–Moore majority vote algorithm 记不住。。不知道还有什么应用
    public int majorityElement(int[] nums) {
        int res = 0;
        int cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {
                res = num;
            }
            if(num == res){
                cnt++;
            }
            else{
                cnt--;
            }
        }
        return res;
    }
}

137. Single Number II

不规则的可能出现了1次或者2次统计每一位1出现的次数

public class Solution {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        int res = 0;
        for(int i = 0;i < 32;i++){
            int sum = 0;
            for(int j = 0;j < len;j++){
                sum  += (nums[j] >> i) & 1;
            }
            res = res | (sum % 3) << i;
        }
        return res;
    }
}

461. Hamming Distance

XOR反应不同位再检查是不是1

public class Solution {
    public int hammingDistance(int x, int y) {
        int dif = 0;
        int xor = x ^ y;
        for(int i = 0;i < 32;i++){
            dif = dif + ((xor >> i) & 1);
        }
        return dif;
    }
}

231. Power of Two

little trick here

public class Solution {
    public boolean isPowerOfTwo(int n) {
        //Power of two
        if(n > 0 && ((n & (n - 1)) == 0))return true;
        return false;
    }
}

187. Repeated DNA Sequences

give each character different meaning of number (1,2,3) use two bit to represent them and each time clear two bit and add the new two bit and set the bit mask to only contain the 10 bit specified

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        Set<Integer> word = new HashSet<>();
        Set<Integer> secondWord = new HashSet<>();
        int[] map = new int[26];
        map['C' - 'A'] = 1;
        map['G' - 'A'] = 2;
        map['T' - 'A'] = 3;
        int value = 0;
        //keep a window and move right 
        for (int i = 0; i < s.length(); i++) {
            //01-- 0100
            value <<= 2;
            value |= map[s.charAt(i) - 'A'];
            value &= 0xfffff;
            if (i < 9) {
                continue;
            }
            if (!word.add(value) && secondWord.add(value)) {
                result.add(s.substring(i - 9, i + 1));
            }
        }
        return result;
    }
}

Bit Manipulation