Problem:
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
Analysis:
This problem is like a magic, it could teach you a mgic skill in bit operation. The instant idea:
Let us count the bit one by one, the easy way is to use a dividend (initial value is 2^31).
Theoretically, all integer could be represented in the form :
digit(31)*2^31 + digit(30)*2^30 + digit(29)*2^29 + ...
It could be solved by following pattern.
Assume: dividen = 2^i
digit = n / dividen (n is no larger than 2^(i+1))
The digit is the digit at 'i' index.
For next index, we need update dividen
dividen = dividen / 2; However that's just theoretical way!!!-.- Wrong solution: public int hammingWeight(int n) {
int count = 0;
long dividen = 1;
int digit = 0;
for (int i = 0; i < 31; i++)
dividen = dividen * 2;
while (n != 0) {
digit = n / dividen;
if (digit == 1)
count++;
n = n % dividen;
dividen = dividen / 2;
}
return count;
}
Wrong case:
Input:
1 (00000000000000000000000000000001)
Output:
0
Expected:
1 Reason:
For ordinary integer, it has reserved one bit for indicate 'negative' or 'positive' of a number. Only 31 bit could be used for representing digits.
Positive Range: [0, 2^31-1]
Negative Range: [-1, -(2^31)]
Why negtaive could reach 2^31, cause for "0000...000", it is no need for representing '-0', thus we use it for representing '-(2^31)'. Reference:
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html Thus the following code could exceed range of positive number.
----------------------------------------------------------------------
for (int i = 0; i < 31; i++)
dividen = dividen * 2;
---------------------------------------------------------------------- A magic way to solve this problem:
Skill:
How to wipe out the last '1' of a integer?
n = n & (n-1)
Reason:
n-1 would turn the last '1' into '0', and all '0' after it into '1'.
Then we use '&', to keep recovering all bits except the last '1'. (has already been changed into '0')
Case:
n = 11110001000
&
n - 1 = 11110000000
ans = 11110000000 Great! Right! Don't mix this skill with
n = n ^ (n-1)
Which could keep the rightmost '1' bit only, all other bit were set into '0'.
Reference:
http://www.cnblogs.com/airwindow/p/4765145.html
Solution:
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 = n & (n-1);
}
return count;
}
}