Just Do IT !

Python算法学习day5:剑指offer：二进制中1的个数

Python算法
字数统计: 520阅读时长: 2 min
2020/01/16 Share

剑指offer：二进制中1的个数

(1) 运用Python函数

代码详细:

1
2
3
4
5
def numberOf1(n):
    if n >= 0:
        return bin(n).count('1')
    else:
        return bin(n & 0xffffffff).count('1')

或者:

1
2
def numberOf1(n):
    return bin(n & 0xffffffff).count('1')

这里bin函数将数字转换为二进制,count为Python内置函数,计算1的个数

(2) 基础数据类型

1
2
3
4
5
6
def countOnes(x):
	count = 0
	while x > 0:
		count += 1
		x &= (x-1)
	return count

or

1
2
3
4
5
6
7
# 负数
def countOnes(x):
	count = 0
	while x&0xffffffff != 0:
		count += 1
		x &= (x-1)
	return count

补充

Python中为什么可以通过bin(n & 0xffffffff)来获得负数的补码？

链接知乎

python通过bin(n & 0xffffffff)获得的并不是这个负数的补码，只是形式与负数的32位二进制补码相同罢了。

举个例子：

1
2
n = -3
n = n & 0xffffffff #n=4294967293

bin(n)查看二进制形式：'0b11111111111111111111111111111101'由于python中没有位数这一概念
所以python认为'0b11111111111111111111111111111101'是正数。
不要看它首位是1。
你看1和-1的二进制表示：

1
2
bin(1)#'0b1'
bin(-1)#'-0b1'

所以二进制中1的个数的题目利用了这个技巧，将负数转化为正数，而它们的二进制形式是相同的，而对正数的二进制进行操作非常简单清晰，统计到这个正数二进制形式中1的个数就是原来负数的二进制形式中1的个数，这样就可以消除负数的影响。

python中，对于负数，无论是右移操作，还是n&（n-1）操作，都会陷入死循环。右移操作是由于负数的最高位总要设为1，最终会变为0xffffffff而陷入死循环。n&(n-1)操作，由于python没有位数概念，负数最左边的1不知道在第几位（觉得这是个坑，具体原理不太清楚），n&(n-1)会不断将最右边的1变为0，也将陷入死循环。

Python3，当长度超过32位或64位之后，Python3会自动将其转为长整型，长整型理论上没有长度限制。

原文作者：浩翰

原文链接：https://plutoacharon.github.io/2020/01/16/Python算法学习day5-剑指offer：二进制中1的个数/

发表日期：January 16th 2020, 8:49:17 pm

更新日期：January 16th 2020, 8:49:29 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 剑指offer：二进制中1的个数
    1. 1.1. (1) 运用Python函数
    2. 1.2. (2) 基础数据类型
    3. 1.3. 补充
Total : 190
2020
2019
CTF Liunx 高可用负载均衡 Java Hadoop Docker Esxi Dokcer Flume GitHub Kafka Golang Golang日志收集系统 Hbase Hive Git Kali Kubernetes Shell Python算法 Spark Sqoop Vmware 机器学习 Zookeeper PHP Hexo 安全 Python PySpark Maven 网络 数据采集 CDN AWD ZooKeeper
CTF Liunx Hadoop Docker GitHub Golang Golang日志收集系统 高可用负载均衡 Hive Java Kubernetes 其他 Python算法 Spark Vmware 机器学习 博客 Python 网络 CDN