计算一个二进制数字中1出现次数的N种方法
1. 引言
闲来无事，在博客园里看到一篇博客。
如何统计二进制中 1 的个数
感觉解法非常新颖，分享一下。
2. 最基本的思路
这个问题描述起来很简单，一句话，实际上解决起来也很简单。
2.1. 解法及代码
想知道最右边一位是否为 1，只需要用这个数和 1 按位与，判断结果为 0 或是 1 就可以，接着，只要循环按位右移原数字，直到原数字变为 0 即可。
def NumberOf1(n):
count = 0
while n != 0:
count += n & 1
n = n >> 1
return count
if __name__ == '__main__':
print(NumberOf1(24183))运行结果：11。
2.2. 存在的问题 — 负数与补码
一旦传入的数字变成负数，就会进入死循环，原因就在于计算机对于负数的存储 — 2的补码。 计算机保存负数的方式是2的补码，简单的来说，一个整数 * -1 后的结果为该整数按位取反再加 1：
计算机为什么要这样存储呢？因为计算机只有加法器没有减法器，两个数的减法运算会被计算机转换为加法运算，而补码恰恰解决了这个问题。
在 python、php 等语言中，在数字的实际位数超过预定位数，解释器会通过字符串的方式去处理数字。 从而只要内存够大，就可以支持无限小的负数，这类语言因为不使用传统的数字存储方式，所以探讨其数字中 1 的数量是没有意义的。 针对 python 语言，在 python2 中，我们可以通过 sys.maxint 获取到上面说的“预定位数”的最大数字来计算，在 python3 中 sys.maxint 更换为了 sys.maxsize，因此我们这里只探讨数字的绝对值小于等于 maxsize 的情况。
针对上面的题目，大部分编程语言在移位操作时，会在高位补符号位，也就说，对于负数而言，右移操作会在高位补 1，于是无论怎么右移，数字 n 永远不会变成 0。 那么基本的解决思路有下面几个：
- 利用 java 语言的 >>> 操作，让解释器强制在高位补 0
- 预先定义最大移位次数变量
- 对负数的最高位直接置 0，然后使用上述程序，并在最终将结果加 1
方法 1 是最简单的，但是其他大部分语言并不支持。 方法 2 需要知道数字的位数，这在不同语言，不同编译环境中是不同的。 方法 3 可行，但是如果想要做到就要先获取最高位为 0 其他位均为 1 的数字，在 C/C++ 、java 等语言中，我们可以通过移位操作来实现，但是和上述理由相同，python、php 等语言中仍然是无法实现的。
3. 解决方案 — 不同语言中的实现
3.1. 方法1 — java
package cn.techlog.test.springboot.service;
public class NumberOfOne {
private static int numberOfOne(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n = n >>> 1;
}
return count;
}
static void main(String args[]) {
int count = numberOfOne(-3);
System.out.println(count);
}
}java 语言的 >>> 让这个问题简单了不少，不幸的是其他语言很少有这样便捷的操作。
3.2. 方法2 — python
import sys
def NumberOf1(n):
count = n & 1
maxtime = len(bin(sys.maxsize)[2:])
while n != 0 and maxtime > 0:
n = n >> 1
count += n & 1
maxtime -= 1
return count
if __name__ == '__main__':
print(NumberOf1(-3))我们通过 len(bin(sys.maxsize)[2:]) + 1 得到了最大能够移位的次数，从而限制循环次数，得到正确的结果：
63
3.3. 方法3 — C++
#include <iostream>
using namespace std;
int numberOfOne(int n)
{
int count = 0;
while (n != 0)
{
count += (n & 1);
n = (n >> 1);
}
return count;
}
int numberOfOneV2(int n)
{
int base = 1;
if (n >= 0) {
return numberOfOne(n);
}
while ((base << 1) > 0) {
base = ((base << 1) | 1);
}
n = n & base;
cout << "base: " << base << endl;
cout << "n: " << n << endl;
return numberOfOne(n) + 1;
}
int main ()
{
int count = numberOfOneV2(-3);
cout << count << endl;
return 0;
}上述代码中，我们通过将初始值为 1 的变量 base 进行移位，从而得到我们所需要的除符号位全 1 数字，从而实现对负数符号位的复位。 最终得到答案：
base: 2147483647 n: 2147483645 31
4. 更加巧妙的两种方法
4.1. 山不过来我过 — 引入测试位
上述所有方法我们都是通过对传入参数移位实现的，如果不对传入参数移位，而是使用测试位，就不会出现上述的问题了。
#include <iostream>
using namespace std;
int numberOfOneV3(int n)
{
int flag = 1;
int count = 0;
while (flag != 0) {
if ((flag & n) != 0) {
count++;
}
flag = flag << 1;
}
return count;
}
int main ()
{
int count = numberOfOneV3(-3);
cout << count << endl;
return 0;
}4.2. 高效新颖的解法
下面是最巧妙的一个方法，基本思路是把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。
那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。
public static int NumberOfOneV4(int n) {
int count = 0;
while (n > 0) {
count++;
n = (n - 1) & n;
}
return count;
}腾讯云开发者
