bit manipulation

• Counting Bits

• [method1] naive O(n*sizeof(int))

    vector<int> countBits(int num) {
        //ret[i] gives # of 1 in binary representation of i
        vector<int> ret(num+1, 0);
        for (int i=0; i<=num; ++i) {
            int curr = i;
            for (int b=0; b<8*sizeof(int); ++b) {
                ret[i] += curr&1;
                curr>>=1;
            }
        }
        return ret;
    }

side note

    bool isPowOfTwo(int n) {
        return (n & (n - 1)) == 0;
    }

num/2 ===> num>>1
num%2 ===> num&1

• [method2] observe and follow pattern: O(n)

• 1.observe that each number append 0 or 1 gets the new number :
  e.g. 0 appends 0 =》00； 0 appends 1 =》01
  容易发现，除了11最右边那个位和5的最高位，其他位对应一样。也就是说i用二进制表示时1出现的次数等于i/2中1出现的次数加1（如果i用二进制表示时最右边一位为1，否则不加1）。这样我们在计算i时可以利用前面已计算出的i/2：ret[i] = ret[i/2] + (i % 2 == 0 ? 0 : 1);

• 2 . OR, observe that ret[i] = ret[i&(i-1)] + 1; Recall i&(i-1)==0 when i is power of 2, meaning only has one bit 1.

    vector<int> countBits(int num) {
        vector<int> ret(num+1, 0);
        for (int i=1; i<num+1; ++i) {
            // ret[i] = ret[i/2] + i%2;
            ret[i] = ret[i>>1] + (i&1); //NOTE: add ()!!! + EXCUTES BEFORE &
            // Or
            ret[i] = ret[i&(i-1)] + 1;  （nearest power of 2）
        }
        return ret;
    }