python - 给定两个 32 位数字 N 和 M，以及两个位位置 i 和 j。写一个方法让 N 中 i 和 j 之间的所有位都等于 M

Question

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j). EXAMPLE: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100

这个问题来自 Cracking the Coding 采访。我能够使用以下 O(j - i) 算法解决它:

def set_bits(a, b, i, j):
    if not b: return a
    while i <= j:
        if b & 1 == 1:
            last_bit = (b & 1) << i
            a |= last_bit
        else:
            set_bit = ~(1 << i)
            a &= set_bit
        b >>= 1
        i += 1
    return a

作者给出了这个O(1)的算法作为解决方案:

def update_bits(n, m, i, j):
    max = ~0 # All 1s

    # 1s through position j, then zeroes
    left = max - ((1 << j) - 1)

    # 1s after position i
    right = ((1 << i) - 1)

    # 1’s, with 0s between i and j
    mask = left | right

    #  Clear i through j, then put m in there 
    return (n & mask) | (m << i)

我注意到对于某些测试用例，作者的算法似乎输出了错误的答案。例如，对于 N = 488、M = 5、i = 2、j = 6，它输出 468。当输出应该是 404 时，就像我的 O(j - i) 算法一样。

问题:有没有办法得到适用于所有情况的恒定时间算法？

Answer 1

我认为该算法的作者假定 j(在您的示例中为 6)的界限不包含；这归结为一个问题，从 2 到 6 的范围是否应该包括 6(在 Python 中不是这样)。也就是说，如果将算法修改为:

def update_bits(n, m, i, j):
    max = ~0 # All 1s

    # 1s through position j, then zeroes
    left = max - ((1 << (j+1)) - 1)

    # 1s after position i
    right = ((1 << i) - 1)

    # 1’s, with 0s between i and j
    mask = left | right

    #  Clear i through j, then put m in there 
    return (n & mask) | (m << i)

有效。

尽管如此，您可以按以下方式加快速度:

def update_bits(n, m, i, j):
    # 1s through position j, then zeroes
    left = (~0) << (j+1)

    # 1s after position i
    right = ((1 << i) - 1)

    # 1’s, with 0s between i and j
    mask = left | right

    #  Clear i through j, then put m in there 
    return (n & mask) | (m << i)

在这个例子中，我们只是简单地将那些移出寄存器。

请注意，您在自己的算法中犯了一个错误，如果是 b = 0 ，这并不意味着您可以简单地返回 a ，因为对于该范围，这些位应该被清除。说 a = '0b1011001111101111' 和 b = '0b0' 和 i 和 j 分别是 6 和 8，人们期望结果是 '0b1011001000101111' 。因此算法应该是:

def set_bits(a, b, i, j):
    while i <= j:
        if b & 1 == 1:
            last_bit = (b & 1) << i
            a |= last_bit
        else:
            set_bit = ~(1 << i)
            a &= set_bit
        b >>= 1
        i += 1
    return a

如果我进行此修改并使用 10'000'000 个随机输入测试程序，两种算法总是产生相同的结果:

for i in range(10000000):
    m = randint(0,65536)
    i = randint(0,15)
    j = randint(i,16)
    n = randint(0,2**(j-i))
    if set_bits(m,n,i,j) != update_bits(m,n,i,j):
        print((bin(m),bin(n),i,j,bin(set_bits(m,n,i,j)),bin(update_bits(m,n,i,j)))) #This line is never printed.

当然这不是证明这两种算法是等价的(也许它们之间存在微小的差异)，但我非常有信心对于有效输入(i 和 j 为正，i < j等)两者应该始终产生相同的结果。