x&x-1 zero out the least significant 1
The first solution is to use the popCount method which could count the 1 bits for one specific number.
The time complexity O(kn). k is the number of 1 bits in the number.
class Solution { public int[] countBits(int num) { int[] ans = new int[num+1]; for(int i = 0; i <= num; i++){ ans[i] = popCount(i); } return ans; } public int popCount(int num){ int count; for(count = 0; num != 0; count++){ num &= num - 1; } return count; } }
The time complexity is O(n).
For example 4(100) 3 (11) 2 (10) num(3) = num(2) + 1 num(4) = num(2).
floor(x/2) == x>>1. It discard the decimal points. If num % 2 == 0, then i & 1 == 0. If num % 2 == 1, then i & 1 == 1
class Solution { public int[] countBits(int num) { int[] ans = new int[num+1]; for(int i = 1; i <= num; i++){ ans[i] = ans[i >> 1] + (i & 1); } return ans; } }
原文：http://www.cnblogs.com/ninalei/p/7989700.html