算法的学习笔记——二进制中 1 的个数（牛客JZ15）
😀前言 在计算机科学中，二进制是计算和存储数据的基础。理解二进制中的基本运算有助于我们解决各种编程问题。一个经典的问题是：给定一个整数，如何快速计算该整数的二进制表示中1的个数。
🏠个人主页：尘觉主页
文章目录
😊二进制中 1 的个数题目链接
计算整数二进制中1的个数（位运算方法详解）题目描述示例解题思路代码实现（Java）代码解析
图示理解😄总结
😊二进制中 1 的个数
题目链接
牛客网
计算整数二进制中1的个数（位运算方法详解）
题目描述
给定一个整数 n，请输出该数在 32位二进制表示 中 1 的个数。
需要注意的是：
输入的整数可能是 正数、零或负数。负数在计算机中使用 补码表示。数据范围为：
−
2
31
≤
n
≤
2
31
−
1
-2^{31} \leq n \leq 2^{31}-1
−231≤n≤231−1
即：-2147483648 <= n <= 2147483647。
示例
示例1：
输入：10
返回值：2
解释：十进制的 10 对应的 32 位二进制表示为：
00000000 00000000 00000000 00001010
其中有 2 个 1。
示例2：
输入：-1
返回值：32
解释：负数使用补码表示，-1 的 32 位二进制为：
11111111 11111111 11111111 11111111
共有 32 个 1。
解题思路
要统计一个整数二进制中 1 的个数，可以使用多种方法：
循环判断每一位
方法：将整数右移，依次检查最低位是否为 1。时间复杂度：固定为 O(32)。缺点：即使数中只有一个 1，也要循环 32 次。 位运算优化方法（推荐）
核心技巧：n & (n-1)
原理：n & (n-1) 会将 n 的二进制表示中 最低位的 1 置为 0。
举例说明：
n = 10（二进制 1010）
n-1 = 9（二进制 1001）
n & (n-1) = 1010 & 1001 = 1000
原本最低的 1 已经被消除。重复操作，直到 n 变为 0，循环次数正好等于二进制中 1 的个数。 时间复杂度：O(M)，其中 M 是二进制中 1 的数量。
比固定循环 32 次更高效，尤其是对于稀疏的二进制数（1 很少）。
代码实现（Java）
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
count++;
n &= (n - 1); // 将最低位的1置为0
}
return count;
}
}
代码解析
初始化计数器 count = 0
循环条件：n != 0
每次循环：
count++：统计当前最低位的 1n &= (n - 1)：消掉当前最低位的 1 循环结束后返回 count
这个方法对 正数、零、负数 都适用，负数自动使用补码表示。
图示理解
以 10 为例（32位）：
初始 n = 10: 00000000 00000000 00000000 00001010
第一次操作 n & (n-1) -> 00000000 00000000 00000000 00001000
第二次操作 n & (n-1) -> 00000000 00000000 00000000 00000000
循环结束，总计 2 个 1
😄总结
位运算技巧 n & (n-1) 可以高效统计二进制中 1 的数量，时间复杂度与 1 的个数成正比。对于负数，Java 中使用补码表示，方法依然适用，无需额外处理。这种技巧在 面试和算法竞赛 中非常常见，也是理解位运算的重要基础。对新手来说，通过图示和循环理解这个算法，可以加深对 补码、位运算和二进制表示 的掌握。
😁热门专栏推荐 想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁 希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻 如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞