本文首发于我的个人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/03/target-offer-bin-num1.html 作者: Suixin
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路
- 问题的关键点在于对于正数，如何得到它的二进制表示；对于负数，如何得到它的补码。负数在计算机中的二进制表示（原码、反码与补码）
- 在Python中，进制转换的函数为：
bin()（转换为二进制），oct()（转换为八进制），hex()（转换为十六进制），int()（转换为十进制）。各个进制的表示开头为：0b（二进制），0o（八进制），0x（十六进制）。 - 在计算机中，所有的数字都是使用补码存储起来的。由于Python没有位数这个概念，所以得到二进制表示需要多一点操作，即将位数限制在32位，通过和一个32位的全1数字按位与运算即可。对于正数来说，上面的按位与操作可以不做，因为正数的符号位为0，补码即原码，所以前面的数字全为0，按位与没有意义。但对于负数来说，直接
bin(-3)是不能得到其补码的，而是得到了3的原码前面加上了负号，即-0b11。则通过和一个32位的全1数字按位与运算可得到其补码（按位与运算把符号位的1视为了数字）。 - 这个32位的全1数字可写为
0xffffffff或0o37777777777或0b11111111111111111111111111111111或4294967295。
代码
Python(2.7.3)
-
因为
bin()输出为str格式，所以可以通过.count()来计数。# -*- coding:utf-8 -*- class Solution: def NumberOf1(self, n): # write code here return bin(n & 0xffffffff).count('1')运行时间：22ms
占用内存：5756k -
对于一个二进制数
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
