2022年 11月 9日

Python 二进制常用方法总结

题目要求,查看二进制中1的个数

1. 转换二进制统计

bin转化为二进制

def countBinary(n):
	return bin(n).count('1')
  • 1
  • 2

2. 二进制移位

# int val; // input data
ans = 0
while val != 0:
    if val & 1:
    	ans += 1
    val >>= 1
    return ans
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

代码中val & 1表示val 与 0x000…0001(其中有31个0)进行 & 操作。
val >>= 1表示,如果val的二进制是110,则操作之后会变成011,也就是舍去最低位,然后最高位补0.
但是如果val为负数,最高位会补1,所以对于负数还是有点问题。
我们可以转换一下思路,让一个数0x01从右向左与val的每一位进行&操作来判断

def binary2(num):
    mark = 0b01
    ans = 0
    while mark <= num:
        if mark & num:
            ans += 1
        mark <<= 1
    return ans
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

0b二进制 0x十进制 0o二进制

3. 技巧法

对于上一种解法中,无用操作是,如果当前位是0, 还是会做判断,然后一位一位的移动。
如果,给你一种超能力,你一下可以对从右向左的第一位1直接判断,遇到0直接略过,那效率是不是很快。

现考虑二进制数:val :1101000, val-1: 1100111 那么val & (val-1) : 1100000

def countN(num):
	ans = 0
	while num:
		ans += 1
		num &= (num-1)
	return ans
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6