剑指15：二进制中1的个数

传送门

nowcoder
leetcode

题目描述

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

C++ 代码 - nowcoder

/*
    bitset 的用法：
    将 n 转化为 32位表示，int 最大是 2^32次方。
    使用 bitset.count 函数，返回其中 1 的数量。
    
    bitset<4> bitset1; // 无参构造，长度为４，默认每一位为０
*/
class Solution {
public:
    int NumberOf1(int n) {
        return bitset<32>(n).count();
    }
};

/*
    每次操作先判断 n 的最低位是否为 1，然后将 n 右移一位。
    总共操作 32 次。

    时间复杂度：O(k)
        其中 k 是 int 型的二进制位数，k = 32。
        需要检查 n 的二进制位的每一位，一共需要检查 32 位，
        每次操作的计算量是 O(1)，总的时间复杂度是 O(k)。
    空间复杂度：O(1)
        常数级别空间，保存若干变量。
*/
class Solution {
public:
    int NumberOf1(int n) {
        int count = 0;
        for (int i = 0; i < 32; i ++) {
            if (n & (1 << i)) {
                count ++;
            }
        }
        return count;
    }
};

/*
    n = n & (n - 1)：消除 n 的二进制表示中的最后一个 1

    时间复杂度：O(logn)
        循环次数等于 n 的二进制位中 1 的个数，
        最坏情况下 n 的二进制位全部为 1，需要循环 logn 次。
    空间复杂度：O(1)
    	常数级别空间，保存若干变量。
*/
class Solution {
public:
    int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count ++;
        }
        return count;
    }
};

C++ 代码 - leetcode

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