题目

题目链接

解题思路

计算32位整数二进制表示中1的个数，有几种常用方法：

位运算法：

使用 \(\text{n} \& \text{1}\) 判断最低位是否为1

右移 \(\text{n}\)，继续判断

统计所有为1的位

n & (n-1) 法：

每次操作会消除最右边的1

统计操作次数即为1的个数

这种方法更高效，因为只需要处理1的个数次

查表法：

预处理所有8位数的1的个数

将32位数分成4个8位处理

适合处理大量数据

代码

#include

using namespace std;

class Solution {

public:

// 方法1：位运算统计

int countOnes1(int n) {

int count = 0;

while (n) {

count += n & 1;

n >>= 1;

}

return count;

}

// 方法2：n & (n-1)

int countOnes2(int n) {

int count = 0;

while (n) {

n &= (n - 1);

count++;

}

return count;

}

};

int main() {

int n;

cin >> n;

Solution solution;

cout << solution.countOnes2(n) << endl;

return 0;

}

import java.util.*;

public class Main {

static class Solution {

// 方法1：位运算统计

public int countOnes1(int n) {

int count = 0;

while (n != 0) {

count += n & 1;

n >>>= 1; // 使用无符号右移

}

return count;

}

// 方法2：n & (n-1)

public int countOnes2(int n) {

int count = 0;

while (n != 0) {

n &= (n - 1);

count++;

}

return count;

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

Solution solution = new Solution();

System.out.println(solution.countOnes2(n));

}

}

def count_ones_1(n: int) -> int:

"""方法1：位运算统计"""

count = 0

while n:

count += n & 1

n >>= 1

return count

def count_ones_2(n: int) -> int:

"""方法2：n & (n-1)"""

count = 0

while n:

n &= (n - 1)

count += 1

return count

if __name__ == "__main__":

n = int(input())

print(count_ones_2(n))

算法及复杂度

算法：位运算

时间复杂度：

方法1：\(\mathcal{O}(32)\) = \(\mathcal{O}(1)\)

方法2：\(\mathcal{O}(k)\)，\(k\) 为1的个数

空间复杂度：\(\mathcal{O}(1)\)