tags: DSA Python

前言

最近看阮一峰老师的每周科技周刊, 发现一个有意思的算法¹, 具体的方法文章中都写了, 不过这里还是介绍一下具体的思路以及其Python版的实现.

算法

一般来说, 计算位1 的个数可以通过下面的两种方法:

def calcbit1_v1(n):return bin(n).count("1")def calcbit1_v2(n):ans = 0while n:tmp = n & 1  # 取最末位ans += tmpn >>= 1return ans

文中给出的方法是下面这样的:

def calcbit1_v3(n):total = 0tmp = nwhile tmp:tmp >>= 1total += tmpreturn n - totaldef calcbit1_v4(n):diff = nwhile n:n >>= 1diff -= nreturn diff

其中v4是为了解释v3.

下面来看一下为什么这样可以计算出整数二进制表示中1的个数.

原理

这个方法基于下面的一个式子:
n=n2+n4+n8+⋯=∑k=0+∞n2kn=\frac n2+\frac n4+\frac n8+\cdots=\sum_{k=0}^{+\infty}\frac n{2^k} n=2n​+4n​+8n​+⋯=k=0∑+∞​2kn​
其中nnn是实数.

当nnn为正整数的时候, 公式就退化成:
n2+n4+n8+⋯≈n\frac n2+\frac n4+\frac n8+\cdots\approx n 2n​+4n​+8n​+⋯≈n
只能找到一个最接近的项数, 使其最接近nnn.

这样一来最低位如果是1, 那么当进行了右移一位操作后, 剩下的数中就一定包含了一个1, 这个1并不会被右移运算去掉, 反而会保留下来, 于是我们每次保留这个右移运算之后的余数(因为右移本质上是整除2), 那么就能得到位1的个数了.

v3

因为整数的右移一位就相当于整除2, 每移出一个位，总和就减少1。这意味着计算和与数学和之间的差等于设定位的数量。

例如, 对于n=11n=11n=11, 其二进制表示为1011, 当第一次作右移, tmp变成了5, 然后total+=5, 第二次tmp=2, total+=2, 最后一次tmp=1, total最后变成了8, 再用n减去total, 这就得到了位1个数3.

v4

这个方法更加简便, 省去了一步减的操作, 除此之外在思路上与v3一致.

ref