查找区间内有效位数最少的数字

Question

给定下限和上限，这些边界内有效位数最少的数字是多少？ 有效位数是最高有效位和最低有效位的位置之差 (MSB - LSB)。

示例：

def sig_bits(x: int) -> int:
    """Count the span of significant bits in an integer."""
    assert 0 < x < 2**64
    as_str = "{:064b}".format(x)
    msb, lsb = as_str.index("1"), len(as_str) - as_str.rindex("1") - 1
    return msb - lsb + 1

def min_sig(a: int, b: int) -> int:
    assert a <= b
    return min((sig_bits(i), i) for i in range(a, b+1))[1]
        
min_sig(5, 10) = 8  # only 1 significant bit: bit 4
min_sig(5, 7) = 6  # bits 2 and 3 are significant

有没有更有效的方法？

Answer 1

不使用字符串，而是计算 MSB/LSB 的

log2

，可以获得一点加速：

from math import log2

def sig_bits(x: int) -> int:
    assert 0 < x < 2**64
    return int(63 - log2(x) - log2(x & -x) + 1)

---

perfplot

基准：

import perfplot
from math import log2


def sig_bits(x: int) -> int:
    """Count the span of significant bits in an integer."""
    assert 0 < x < 2**64
    as_str = "{:064b}".format(x)
    msb, lsb = as_str.index("1"), len(as_str) - as_str.rindex("1") - 1
    return msb - lsb + 1


def sig_bits_andrej(x: int) -> int:
    assert 0 < x < 2**64
    return int(63 - log2(x) - log2(x & -x) + 1)


def min_sig(a: int, b: int) -> int:
    assert a <= b
    return min((sig_bits(i), i) for i in range(a, b + 1))[1]


def min_sig_andrej(a: int, b: int) -> int:
    assert a <= b
    return min((sig_bits_andrej(i), i) for i in range(a, b + 1))[1]



perfplot.show(
    setup=lambda n: [(10, 100), (20, 200), (100, 10_000), (100_000, 1_000_000)][n],
    kernels=[
        lambda a, b: min_sig(a, b),
        lambda a, b: min_sig_andrej(a, b),
    ],
    labels=[
        "original",
        "andrej",
    ],
    n_range=[0, 1, 2, 3],
    xlabel="N (* len(df))",
    logx=True,
    logy=True,
)

产生这个结果：