一种计算整数位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
1
2
3
4
5
6
7
8
9
10
11

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

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

其中v3是为了解释v4.

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

原理

这个方法基于下面的一个式子:(从二进制表示形式更容易理解)
$$n=\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots =\sum _{k=0}^{+\infty }\frac{n}{2^k}$$
其中$n$是实数.

当$n$为正整数的时候, 公式就退化成:
$$\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots \approx n$$
只能找到一个最接近的项数, 使值最接近$n$.

从二进制角度, 我们从最低位开始,

• 如果最低位是0, 右移之后剩下的数与原来的数相比仅仅是做了除以2的操作, 不会留下1, 所以直接加和即可.
• 如果是$1$, 那么当进行了右移一位操作后, 剩下的数(非零)二进制表示中就少了一个位1, 这个1在右移的过程中被舍弃了, 这也正是我们要统计的数.

所以, 保留每次右移运算之后剩下的数之和, 然后与原数n相减, 那么就能得到位1的个数了.

这里剩下的数其实也可以理解为余数, 因为右移本质上是整除2.

v3

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

例如, 对于$n=11$, 其二进制表示为1011,

• 第一次右移, tmp=5, total=5,
• 第二次tmp=2, total=7,
• 最后一次tmp=1, total=8,
• 用n减去total, 这就得到了数11的位1个数为3.

v4

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

ref

---

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