from 1 to n, count the number of bits that were set to 1.
For example,
n == 1, return 1,
n == 2, return 3,
n == 3, return 5
n==4, return 6
A:
solution 1: 一个个数,
Solution 2:把n 从2^j 一个个整除,来计算。
private static int numberOf1Bits(int n) { int mask = 0; // set the mask as the left part of nPlusOne int nBits = 0; // counts the bits from 1 to n in their binary form for (int i = 30; i >= 0; i--) { int power2 = 1 << i; if(n/power2<1) // this two lines can be commented continue; // can be commented mask |= (n & power2); int nRepeatOnes = n / (power2<<1) * power2 ; int nLeftOnes = ( n>>i & 1) * (n - mask+1); nBits += nRepeatOnes + nLeftOnes; } return nBits; }
Mistakes:
1: 这里,要除的时候,跟n+1无关,而应该是n / 上一位的power,因此要power2<<1
No comments:
Post a Comment