给定两个32位数字,N和M,以及两个位,i和j.编写一种方法,将N和j之间的所有位设置为N等于M.

Question

您将获得两个32位数字,N和M,以及两个位,即i和j.编写一种方法来将N和j之间的所有位设置为N等于M(例如,M变为位于i的N的子串并从j开始).示例:输入:N = 10000000000,M = 10101,i = 2,j = 6输出: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(在你的例子中是六个)是排他的 ; 这归结为从问题的范围内是否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,等等),两者都应该总是产生相同的结果.