逐位比较bit

Single Number II

在一个数组里，有一个数出现了一次，别的数都出现了恰好三次，找那个single number。对于每一位bit，统计所有number在这一位上是0或1，如果是1的总数余3不为0，那那个single number在这个bit位上是1。

public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num: nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            if (count % 3 != 0) {
                result |= 1 << i;
            }
        }
        return result;
    }
}

Majority Element

对于每一位bit，统计所有number在这位上出现1的次数。如果次数*2大于array的length，那majority element在这位上是1。

public class Solution {
    public int majorityElement(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num: nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            if (count * 2 > nums.length) {
                result |= 1 << i;
            }
        }
        return result;
    }
}

Reverse Bits

这题的input需要当成unsigned value来做，所以我们在看当前位是不是1的时候，要用>>>，而不是>>。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            if ((n >>> i & 1) == 1) {
                result |= 1 << (31 - i);
            }    
        }
        return result;
    }
}

Number of 1 Bits

跟上一题一样，注意input是unsigned value时的操作。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n >>> i & 1) == 1) {
                count++;
            }
        }
        return count;
    }
}

Hamming Distance

这题也是逐位比较的，当两个数在当前位不相同的话，我们更新count的数值。

public class Solution {
    public int hammingDistance(int x, int y) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            int n1 = x >> i & 1;
            int n2 = y >> i & 1;
            if (n1 != n2) {
                count++;
            }
        }
        return count;
    }
}

Total Hamming Distance

这题brute force的做法是两重for循环，用上一题的方法，两两比较，O(n ^ 2)的时间复杂度，超时了。

O(n)的复杂度的做法是，外层的for循环遍历int上的每一位，内层的for循环遍历数组，统计每一位出现了1的count，那该位的hamming distance就是count * (array.length - count)。

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num: nums) {
                if ((num >> i & 1) == 1) {
                    count++;
                }
            }
            total += count * (nums.length - count);
        }
        return total;
    }
}

Power of Two

排除首位，其余有且只有一位是1的，就是power of two。

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        } 

        int count = 0;
        for (int i = 0; i < 31; i++) {
            if ((n >> i & 1) == 1) {
                count++;
            }
        }
        return count == 1;
    }
}

Power of Four

排除首位，有且只有一位是1的，而且是1的一位的index是偶数的，就是power of four。

public class Solution {
    public boolean isPowerOfFour(int num) {
        if (num <= 0) {
            return false;
        }

        int count = 0, index = -1;
        for (int i = 0; i < 32; i++) {
            if ((num >> i & 1) == 1) {
                index = i;
                count++;
            }
        }
        return count == 1 && index % 2 == 0;
    }
}