题解 | #二进制中1的个数#
二进制中1的个数
http://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8
算法思路一：位运算右移
解题思路：
判断 n 最右一位是否为 11 ，根据结果计数。将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作）
算法流程：
初始化数量统计变量 res = 0。
循环逐位判断： 当 n = 0时跳出。
res += n & 1 ： 若 n & 1 = 1，则统计数 resres 加一。
n >>= 1 ： 将二进制数字 n 无符号右移一位（ Java 中无符号右移为 ">>>" ） 。
返回统计数量 res 。
初始化数量统计变量 res = 0。
循环逐位判断： 当 n = 0时跳出。
res += n & 1 ： 若 n & 1 = 1，则统计数 resres 加一。
n >>= 1 ： 将二进制数字 n 无符号右移一位（ Java 中无符号右移为 ">>>" ） 。
返回统计数量 res 。
图解：
n = 10
| 步骤 | 操作 | n二进制 | res |
| 1 | | 1010 | 0 |
| 2 | 右移1位 | 0101 | 1 |
| 3 | 右移1位 | 0010 | 1 |
| 4 | 右移1位 | 0001 | 2 |
| 5 | 右移1位 | 0000 | 2 |
代码展示：
public class Solution {
public int NumberOf1(int n) {
int cnt = 0;
// 循环直到n == 0
while(n != 0){
// 判断 n & 1 是否为0
if((n & 1)!=0)cnt++;
//将n进行无符号右移
n = n>>>1;
}
return cnt;
}
} 复杂度分析：
时间复杂度 O(logn) ： 此算法循环内部仅有 移位、与、加 等基本运算，占用 O(1) ；逐位判断需循环 logn 次，其中n 代表数字n 最高位 1 的所在位数。
空间复杂度 O(1) ： 变量 res使用常数大小额外空间。
空间复杂度 O(1) ： 变量 res使用常数大小额外空间。
算法思路二：巧用 n&(n-1)
n&(n - 1)，其预算结果恰为把 n 的二进制位中的最低位的 1 变为 0之后的结果
算法流程：
初始化数量统计变量 res
循环消去最右边的 1 ：当 n = 0时跳出。
res += 1 ： 统计变量加 1 ；
n &= n - 1 ： 消去数字 n 最右边的 1 。
返回统计数量 res。
循环消去最右边的 1 ：当 n = 0时跳出。
res += 1 ： 统计变量加 1 ；
n &= n - 1 ： 消去数字 n 最右边的 1 。
返回统计数量 res。
图解：
代码展示：
# -*- coding:utf-8 -*- class Solution: def NumberOf1(self, n): # write code here count = 0 # n < 0 则需要将其进行转换 if n<0: n = n & 0xffffffff # 循环计算，将二进制最右边的1变成0 # 统计循环次数，即为 二进制中1的数量 while n: count += 1 n = (n-1) & n return count
复杂度分析：
时间复杂度：O(log n)。循环次数等于 n 的二进制位中 1 的个数，最坏情况下 n 的二进制位全部为 1。我们需要循环 logn 次。空间复杂度：O(1)，我们只需要常数的空间保存若干变量
投递海康威视等公司10个岗位 >
查看17道真题和解析