开个位运算的坑，补到哪算哪。

前面树有道题用位运算做的，想不起来哪个了。

78. Subsets

非递归的方法, 用的是位运算的思想

1 << n 是 2^n
每一个subset对应一个integer介于 0 到 2^n - 1

0 -> 000 -> []
1 -> 001 -> [1]
2 -> 010 -> [2]
...
7 -> 111 -> [1,2,3]

public ArrayList<ArrayList<Integer>> subsetsNonRecursion(int[] nums) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if(nums == null || nums.length == 0){
        return result;
    }
    int n = nums.length;
    Arrays.sort(nums);

    for(int i = 0; i < (1 << n); ++i){
        ArrayList<Integer> subset = new ArrayList<Integer>();
        for(int j = 0; j < n; ++j){
            if((i & (1 << j)) != 0){
                subset.add(nums[j]);
            }
        }
        result.add(subset);
    }
    return result;
}

191. Number of 1 Bits

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

这题我有个疑点，unsigned integer不需要特殊声明吗，为什么 1 直接可以当做32位的unsigned int来进行位运算？

所以有一种更好的解法，不用引入新的integer就可以解决。

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;

        while(n != 0){
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

每次减一之后 AND 运算都刚好去掉一个 1。去到0为止，我们得到了1的个数。

338. Counting Bits

朴素的做法很简单。O(n*sizeof(integer))

和上一道题是一样的。

public class Solution {
    public int[] countBits(int num) {
        int[] result = new int[num + 1];

        for (int i = 0; i <= num; ++i) {
            int count = 0;
            int j = i;
            while (j != 0) {
                j = j & (j - 1);
                count++;
            }
            result[i] = count;
        }
        return result;
    }
}

此题重点和难点在于：Do it like a Boss.

• 12 :..............0000001100

• -12 :............11111110100

• 12 & -12:.....0000000100

n - (n & -n) 效果为减去 n 的二进制表示中最右边为 1 的 bit

由于结果肯定比 n 小，bit 数又一定只比 n 多一个，就可以迭代求解了~

public class Solution {
    public int[] countBits(int num) {
        int[] rst = new int[num + 1];

        for(int i = 1; i <= num; i++){
            // previous index = Remove most significant digit
            // then add one as current bit.
            rst[i] = rst[i - (i & -i)] + 1;
        }

        return rst;
    }
}

89. Gray Code

n=3时，正确的GrayCode应该是 000 001 011 010 110 111 //如果按照题意的话，只是要求有一位不同，这里也可以是100 101 100

这样的话，规律就出来了，n=k时的Gray Code，相当于n=k-1时的Gray Code的逆序 加上 1 < < k

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();

        result.add(0);
        for (int i = 0; i < n; ++i) {
            int higher = 1 << i;
            int size = result.size();
            for (int j = size - 1; j >= 0; --j) {
                result.add(result.get(j) + higher);
            }
        }
        return result;
    }
}

题意不清楚，如果每次只是与上一个数有一个位不同的话，其实有很多种组合出来。如果不是查了Gray Code的定义，根本看不出来什么规律。

而且，Gray Code这种东西，必然有数学解，否则在早期的工程界是没法应用的。其实也可以这么做，第i个数可以由如下公式产生： (i>>1)^i，所以代码也可以是：

public List<Integer> grayCode(int n) {
    List<Integer> result = new LinkedList<>();
    for (int i = 0; i < 1<<n; i++) result.add(i ^ i>>1);
    return result;
}

不过这种投机取巧的方法没什么价值，数学解就失去了interview的意思了