[剑指Offer]二进制中1的个数

本文首发于我的个人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/03/target-offer-bin-num1.html　　作者: Suixin

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

解题思路

1. 问题的关键点在于对于正数，如何得到它的二进制表示；对于负数，如何得到它的补码。负数在计算机中的二进制表示（原码、反码与补码）
2. 在Python中，进制转换的函数为：bin()（转换为二进制），oct()（转换为八进制），hex()（转换为十六进制），int()（转换为十进制）。各个进制的表示开头为：0b（二进制），0o（八进制），0x（十六进制）。
3. 在计算机中，所有的数字都是使用补码存储起来的。由于Python没有位数这个概念，所以得到二进制表示需要多一点操作，即将位数限制在32位，通过和一个32位的全1数字按位与运算即可。对于正数来说，上面的按位与操作可以不做，因为正数的符号位为0，补码即原码，所以前面的数字全为0，按位与没有意义。但对于负数来说，直接bin(-3)是不能得到其补码的，而是得到了3的原码前面加上了负号，即-0b11。则通过和一个32位的全1数字按位与运算可得到其补码（按位与运算把符号位的1视为了数字）。
4. 这个32位的全1数字可写为0xffffffff或0o37777777777或0b11111111111111111111111111111111或4294967295。

代码

Python(2.7.3)

1. 因为bin()输出为str格式，所以可以通过.count()来计数。

   # -*- coding:utf-8 -*-
   class Solution:
       def NumberOf1(self, n):
           # write code here
           return bin(n & 0xffffffff).count('1')
   

   运行时间：22ms
占用内存：5756k

2. 对于一个二进制数n，可以发现将其和n-1做按位与运算的结果是将n的二进制最右边的一个1变成了0，其它所有未变。故可以通过此方法循环来计算二进制中1的数量。

   # -*- coding:utf-8 -*-
   class Solution:
       def NumberOf1(self, n):
           # write code here
           if n < 0:
               n &= 0xffffffff
           count = 0
           while n:
               count += 1
               n &= n - 1
           return count
   

   运行时间：31ms
占用内存：5840k

参考

AlgorithmsByPython-二进制中1的个数
https://www.zhihu.com/question/314455297
https://blog.csdn.net/leonliu06/article/details/78685248