algorithm - 将范围分割成可以被位掩码的片段

Question

我有 2 个任意 16 位整数。举个例子：

start: 0010000000000000 (8192)
end:   1111111111111111 (65535)

我想将范围 8192-65535 拆分为可以用位掩码表示的内容。所以在这种情况下，我希望能够识别：

start: 0001000000000000 (8192)
end:   0011111111111111 (16383)

start: 0100000000000000 (16384)
end:   0111111111111111 (32767)

start: 1000000000000000 (32768)
end:   1111111111111111 (65535)

我该怎么做呢？不是特定于语言的，只需要一些想法。

Answer 1

这里的想法是找到所有2^n - 1介于低值和高值之间的值。这是因为所有块位掩码（如您所追求的那种）都是2^n - 1. 这是一些python来实现这一点：

def split_range(low, high):
    yield low
    for mask in [(1 << k) - 1 for k in xrange(0, 16) if (1 << k) > low and (1 << k) < high]:
        yield mask
    yield high

为你举例

In [5]: list(split_range.split_range(8192, 65535))
Out[5]: [8192, 16383, 32767, 65535]

Answer 2

假设num总是至少 8192 ......

if num & 0xc000 == 0:
    # bitmask 0xc000 == 1100000000000000
    # first partition if the first two bits are 0
elif num & 0x8000 == 0:
    # bitmask 0x8000 == 1000000000000000
    # second partition if only the first bit is 0
else:
    # third partition