Labels

Tuesday, March 10, 2015

Number of 1 Bits

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.

Naive Way: To go through each bit using a mask will take 32 unit time. However, there is a way that runs faster, x & (x-1), which removes the right most 1 from x. For reference, see low-level-bit-hacks

 public class Solution {  
   // you need to treat n as an unsigned value  
   public int hammingWeight(int n) {  
     int count = 0;  
     while(n != 0){  
       n = n & (n-1);  
       count++;  
     }  
     return count;  
   }  
 }  

No comments:

Post a Comment