判断二进制中1的个数,可通过位运算高效实现。以下是主要方法及分析:
一、高效位运算方法(推荐)
核心思想:通过`n & (n - 1)`操作消除最低位的1,统计循环次数即为1的个数。该方法时间复杂度为O(k),其中k为二进制中1的个数。
实现步骤:
1. 初始化计数器`count`为0;
2. 当`n`不为0时,执行`n = n & (n - 1)`,并将`count`加1;
3. 循环结束后返回`count`。
示例:
输入`n = 7`(二进制`0111`),循环两次后`n`变为0,返回2。
二、其他方法
逐位检查法 通过右移操作逐位判断,时间复杂度为O(m),其中m为二进制位数(32位整数)。
左移与与运算法
通过左移和与运算判断每一位是否为1,需循环32次(针对32位整数)。
除法与取余法
将数字转换为二进制字符串,统计1的个数,适用于任意位数但效率较低。
三、适用场景
高效场景:
优先使用`n & (n - 1)`方法,尤其适用于32位整数或需要快速统计的场景;
通用场景:其他方法可作为补充,但需注意位数限制(如32位无符号整数)。
四、注意事项
负数处理:上述方法仅适用于非负整数,若需处理负数,需先转换为无符号数;
位数限制:32位整数时,循环次数固定为32次,避免溢出。