LeetCode 191 Number of 1 Bits 题解

题意

求一个整数的二进制中1的个数。例如32位整数11的二进制为00000000000000000000000000001011,共有3个1,所以返回3.

分析

利用位运算n & (n - 1)消去最后一个1,直到整数为零为止。这个位运算的具体解释请参见231题:Power of Two. 直接上代码了。

C代码:

1
2
3
4
5
6
int hammingWeight(uint32_t n) {
int sum = 1;
if(n == 0) return 0;
while(n = (n & (n - 1))) sum++;
return sum;
}

sum要初始化为1,因为最后一个1被消掉时while循环是进不去的,所以少累加了一次,要补上。输入0时,循环也进不去,但要返回0,这里要特别判定一下。另外附上讨论区里面给的一个非常神棍而变态的无循环版的位运算解法,耗时跟我的解法一样,都是4ms。

1
2
3
4
5
6
7
8
int hammingWeight(uint32_t n)
{
unsigned int c;
c = ((n & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((n & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += ((n >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
return c;
}

这个解法大家看看热闹就好~


版权声明

The Bloom of Youth by KUANG Qi is licensed under a Creative Commons BY-NC-ND 4.0 International License.
况琪创作并维护的锦瑟华年博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于The Bloom of Youth | 锦瑟华年博客( http://kuangqi.me ),版权所有,侵权必究。

本文永久链接:http://kuangqi.me/programming/leetcode-number-of-1-bits/