具有换档操作的二进制掩模,无循环

Question

我们有一些大的二进制数N(大意味着数百万的数字).我们还有二进制掩码M,其中1表示我们必须删除数字N中此位置的数字,并将所有较高位移到一个位置右侧.

例:

N = 100011101110
M = 000010001000
Res   1000110110

是否有可能在没有一些逻辑或算术运算的循环的情况下解决这个问题？我们可以假设我们可以在Python中访问bignum算法.

感觉它应该是这样的:Res = N - (N xor M)但它不起作用

UPD:我目前的循环解决方案如下:

def prepare_reduced_arrays(dict_of_N, mask):
    '''
    mask: string '0000011000'
    each element of dict_of_N - big python integer
    '''

    capacity = len(mask)
    answer = dict()
    for el in dict_of_N:
        answer[el] = 0

    new_capacity = 0
    for i in range(capacity - 1, -1, -1):
        if mask[i] == '1':
            continue
        cap2 = (1 << new_capacity)
        pos = (capacity - i - 1)
        for el in dict_of_N:
            current_bit = (dict_of_N[el] >> pos) & 1
            if current_bit:
                answer[el] |= cap2
        new_capacity += 1

    return answer, new_capacity

Answer 1

据我所知，当且仅当M是 2 的幂时，这可以在不使用循环的情况下完成。

让我们以您的示例为例，并将M其修改为 2 的幂：

N = 0b100011101110 = 2286
M = 0b000000001000 = 8

删除第四个最低位N并将较高位向右移动将导致：

N = 0b10001110110 = 1142

我们使用以下算法实现了这一目标：

• 首先N = 0b100011101110 = 2286
• 从最高有效位迭代到最低有效位M。
• 如果当前位M设置为 1，则将低位存储在某个变量中x：
  • x = 0b1101110
• M然后，减去from中直到当前位（包括当前位）的每一位N，最终得到以下结果：
  • N - (0b10000000 + x) = N - (0b10000000 + 0b1101110) = 0b100011101110 - 0b11101110 = 0b100000000000
  • 此步骤也可以通过对位进行 和运算来实现0，这可能会更有效。
• 接下来，我们将结果右移一次：
  • 0b100000000000 >> 1 = 0b10000000000
• 最后，我们将x移位后的结果加回：
  • 0b10000000000 + x = 0b10000000000 + 0b1101110 = 0b10001101110 = 1142

这可能可以在没有循环的情况下以某种方式完成，但如果您只是简单地迭代（从最高有效位到最低有效位）并在每个设置位上执行此过程，那么实际上会很有效M，因为时间复杂度是O(M.bit_length())。

我也写了这个算法的代码，我相信它相对有效，但我没有任何大的二进制数来测试它：

def remove_bits(N, M):
    bit = 2 ** (M.bit_length() - 1)

    while bit != 0:
        if M & bit:
            ones = bit - 1

            # Store lower `bit` bits.
            temp = N & ones

            # Clear lower `bit` bits.
            N &= ~ones

            # Shift once to the right.
            N >>= 1

            # Set stored lower `bit` bits.
            N |= temp

        bit >>= 1

    return N

if __name__ == '__main__':
    N = 0b100011101110
    M = 0b000010001000

    print(bin(remove_bits(N, M)))

使用您的示例，这将返回您的结果：0b1000110110