一种计算整数位1个数的新方法

tags: DSA Python

前言

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

算法

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

def calcbit1_v1(n):
    return bin(n).count("1")


def calcbit1_v2(n):
    ans = 0
    while n:
        tmp = n & 1  # 取最末位
        ans += tmp
        n >>= 1
    return ans

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

def calcbit1_v3(n):
    total = 0
    tmp = n
    while tmp:
        tmp >>= 1
        total += tmp
    return n - total


def calcbit1_v4(n):
    diff = n
    while n:
        n >>= 1
        diff -= n
    return diff

其中​​v4​​​是为了解释​​v3​​.

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

原理

这个方法基于下面的一个式子:

其中是实数.

当为正整数的时候, 公式就退化成:

只能找到一个最接近的项数, 使其最接近.

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

v3

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

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

v4

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

ref

1. ​​www.robalni.org/posts/20220428-counting-set-bits-in-an-interesting-way.txt​​; ↩︎