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。
那么基本的解决思路有下面几个：

1. 利用 java 语言的 >>> 操作，让解释器强制在高位补 0
2. 预先定义最大移位次数变量
3. 对负数的最高位直接置 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++

 
上述代码中，我们通过将初始值为 1 的变量 base 进行移位，从而得到我们所需要的除符号位全 1 数字，从而实现对负数符号位的复位。
最终得到答案：
 
   
 
    
base: 2147483647
n: 2147483645
31
 
   
 
4. 更加巧妙的两种方法
 
4.1. 山不过来我过 — 引入测试位
 
上述所有方法我们都是通过对传入参数移位实现的，如果不对传入参数移位，而是使用测试位，就不会出现上述的问题了。
 
 
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;
}
5. 微信公众号
欢迎关注微信公众号，以技术为主，涉及历史、人文等多领域的学习与感悟，每周三到七篇推文，全部原创，只有干货没有鸡汤。

 阅读原文
 
                                                        
《计算一个二进制数字中1出现次数的N种方法》来自互联网，仅为收藏学习，如侵权请联系删除。本文URL：http://www.bookhoes.com/158.html