转载

LeetCode Number of 1 Bits

1.题目

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

2.解决方案1

class Solution { public:  int hammingWeight(uint32_t n) {   int count = 0;  while (n)  {   ++ count;   n = (n - 1) & n;  }  return count;  } }; 

比如容易想到的解决方案是下面这个,每次往右移动一位,判断最后一位是不是1,但这样会有点慢,32位就要移动32次。上面的方法巧妙的使用了(n-1) & n,这个有什么用?我们来看下具体的例子:

假设n= 1111000111000 那 n-1 = 1111000110111, (n-1) & n = 1111000110000,刚好把最后一个1给干掉了。也就是说, (n-1)&n 刚好会从最后一位开始,每次会干掉一个1.这样速度就比下面的快了。有几个1,执行几次。

class Solution { public:  int hammingWeight(uint32_t n) {     int count = 0;  while(n)  {   if(n & 1)    count ++;   n = n >> 1;  }  return count;  } }; 
正文到此结束
Loading...