#191 Number of 1 Bits

- 日理万妓 2022-08-02 04:58 132阅读 0赞

没有找到数算书。。摸了一本C++ Primer过来。再从网上学学吧~

今天还是看看简单题好了，哪里不会学哪里。

挑一道看起来就简单的嘿嘿。

[\#191 Number of 1 Bits][191 Number of 1 Bits]

题目是查找32位无符号整数中bit上1的个数。首先想到的自然是&1然后移位啦~

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

中间脑残了两次敲错了一些，果然缺少记事本写C++的经验还是不行呀。4ms Accepted。但是感觉应该还有更好的解法吧，不过位运算这里当年学ICS就发现自己缺少经验了，想了一下没有回忆起学过什么，于是还是百度一下好了。学习了 [Canglingye][]的解法，又打开了新世界的大门。

解法原理也很简单，看过一次之后以后一定就会啦。想法就是n&n-1，这样每次就会少一个1（因为将n最后的一个1变成了0），这样看与运算的次数就行了。

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

按照Canglingye的说法上一个解法会超时而这个不会，不过分析可以知道第二种只是平均更快，而最差情况仍然是要32次循环。

不知道是否有最坏情况更好的解法，除了打表还没想到别的。如果有的话请多多指教啦！

[191 Number of 1 Bits]: https://leetcode.com/problems/number-of-1-bits/
[Canglingye]: http://blog.csdn.net/canglingye/article/details/44177479