本文共 859 字，大约阅读时间需要 2 分钟。

题目描述

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中1的个数。例如，将9表示为二进制是1001，有两位是1。因此，如果输入9，函数应输出2。

示例1：

输入：00000000000000000000000000001011

输出：3

解释：输入的二进制串00000000000000000000000000001011中共有三位为'1'。

示例2：

输入：00000000000000000000000010000000

输出：1

解释：输入的二进制串00000000000000000000000010000000中共有一位为'1'。

示例3：

输入：11111111111111111111111111111101

输出：31

解释：输入的二进制串11111111111111111111111111111101中共有31位为'1'。

解题思路

逐位判断法

通过与运算判断每一位是否为1，并统计1的总数。这是一种常见的位操作方法，具体步骤如下：

(1) 初始化统计变量res为0。

(2) 当处理的数n不为0时，执行以下步骤：

• 检查n的最低有效位是否为1：若n&1等于1，就将res加一。

• 将n右移一位（这里需要使用无符号右移操作）。

(3) 当n变为0时，循环结束，返回res即为1的总数。

算法流程

代码示例（Java）：

```javapublic class Solution { public int hammingWeight(int n) { int res = 0; while (n != 0) { res += n & 1; n >>= 1; } return res; }}```

(注：在Java中，`n >>= 1` 是无符号右移操作，确保处理时作为无符号数进行计算。)

复杂度分析

时间复杂度：O(log n)，因为每次循环处理一次二进制位，最多处理30次（对于32位数字而言）。

空间复杂度：O(1)，只使用了一个变量res进行计数，无额外空间需求。

转载地址：http://wvchz.baihongyu.com/