191. 位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

Solution1：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cot = 0;
        while(n){
            cot += n&1;
            n >>= 1; 
        }
        return cot;
    }
};

思路：

将每一位移到最后一位检查是否为1，到0为止，最后返回个数。

由于是无符号整型，每次都会执行32次，所以时间复杂度是O(1)。

Solution2（优化）：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cot = 0;
        while(n){
            n &= (n-1);
            cot++;
        }
        return cot;
    }
};

看了官方题解，这种方法是每一次将最后一个1给消除。这样顶多执行k次，k就为1的个数。这样就又优化了一点点计算。

eg：

11010 & 11001 = 11000

11000 & 10111 = 10000

10000 & 01111 = 0

231. 2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

有了上面的思路：

这道题就可以写成这样：

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && !(n & (n-1));
    }
};

2的n次方在二进制中就是只有1个位置是1，其他全是0（对于正数）。