Python编程题19--比特位计数

2021/10/17 20:12:12

本文主要是介绍Python编程题19--比特位计数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

给定一个整数 n ,对于 0 ≤ i ≤ n 中的每个 i ,计算其二进制表示中 1 的个数并把它们返回。

例如:

给定一个整数:n = 2,返回结果:[0, 1, 1]

给定一个整数:n = 5,返回结果:[0, 1, 1, 2, 1, 2]

n的范围说明:0 ≤ n ≤ 10^5

实现思路1

  • 设置一个列表res,用于存储 0 ≤ i ≤ n 中的每个 i 对应二进制数中1的个数
  • 遍历1到n+1,利用 Python 里的内置函数 bin() 把 i 转换为字符串格式的二进制数,比如 8 转为二进制数为 0b1000
  • 利用 Python 里的内置函数 count() 统计字符串中出现1的次数,并依次把出现次数添加到res中,最后进行返回

代码实现

def countBits(n):
    res = [0]
    for i in range(1, n + 1):
        res.append(bin(i).count("1"))
    return res

实现思路2

  • 针对二进制数,左移一位,代表乘以2;右移一位,代表除以2;
  • 对于偶数 i ,其二进制数最低位肯定为0,所以其二进制数整体向右移动一位后并不会影响1的个数。其二进制中1的个数,也就肯定等于 i // 2
    所对应的二进制数中1的个数;
  • 对于奇数 i ,其二进制数最低位肯定为1,其二进制中1的个数,也就肯定等于前一个数中1的个数再加1

代码实现

def countBits(n):
    res = [0]
    for i in range(1, n + 1):
        if i % 2 != 0: 
            res.append(res[i - 1] + 1)
        else: 
            res.append(res[i // 2])
    return res

实现思路3

我们还可以利用 Python 里的 位运算符 来实现,其大致与实现思路2的逻辑一致,但通过位运算符,我们可以让代码更简化。

  • & 按位与运算符:参与运算的两个二进制数, 如果两个相应位都为1, 则该位的结果为1, 否则为0;
  • >> 右移动运算符:如 i >> 1,表示将 i 对应的二进制数整体右移一位,其实也就相当于 i // 2
  • 如果 i 为偶数,其二进制数最低位肯定为0,所以 i & 1 的结果必为 0;
  • 如果 i 为奇数,其二进制数最低位肯定为1,所以 i & 1 的结果必为 1。

代码实现

def countBits(n):
    res = [0]
    for i in range(1, n + 1):
        res.append(res[i >> 1] + (i & 1))
    return res


这篇关于Python编程题19--比特位计数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程