LeetCode 191 Number of 1 Bits

LeetCode 191 Number of 1 Bits 

解法一(较为传统都解法)：使用将n不断右移，并与1想&得到1的个数；（也有使用除法/2的，明显除法的运行效率要低于位移）

时间复杂度:0(logn)

 1 int hammingWeight(uint32_t n){
 2     int count=0;
 3     
 4     while (n!=0) {
 5         if (n & 1) {
 6             ++count;
 7         }
 8         n = n>>1;
 9     }
10     
11     return count;
12 }

解法二：

使用n&(n-1)的方法

假使 n =0x110101

                n                    n-1               n&(n-1)

step1:   110101          110100          110100

step2:   110100          110011          110000

step3:   110000          101111          100000

step4:   100000          011111          000000

发现有几个1，就循环几次n&(n-1)得到0，明显较于上者运行效率更高些。

时间复杂度：O(M),M是n中1的个数。

代码如下：

 1 int hammingWeight(uint32_t n){
 2     int count=0;
 3     
 4     while (n!=0) {
 5         count++;
 6         n = n&(n-1);
 7     }
 8     
 9     return count;
10 }

LeetCode 191 Number of 1 Bits

原文：http://www.cnblogs.com/wudongyang/p/4337295.html