是否有使用掩码打开和关闭位组的非迭代方法？

Question

假设我有两个位串：runs 和 toggler，其中运行是一组连续的类似位。这两个位串都可以任意排列 1 和 0（分别为开和关）。为了这个问题，我将使用下面的示例值：

runs   : 1111011010100011
toggler: 1010001010010110

是否存在一种方法来屏蔽这两个位字符串，或者在迭代之外利用 c++ 的任何功能（尽管越通用/语言无关越好）来生成 result 位包含 runs 中每个运行个 1 的字符串，它至少拥有一位在 toggler 中有相应 1 的位？使用提供的示例值的一个有效示例如下所示：

runs   : 1111011010100011
toggler: 1010001010010110
result : 1111011010000011

其中runs中1的第一、二、三、四运行个在toggler中的组成位都至少有一个1对应。[=26] =]

到目前为止，我已经很明显可以识别result中的一些0的位置，即对应于[=21的位=]. 中result的1的位置也可以确定为runs & toggler。鉴于此信息，任何剩余的未知位（相当于满足条件 runs & ~toggler 的位）都可以确定为 0，前提是未知位运行两端的位为零。这可以在下面的位串 unknown:

中再次看到

runs   : 1111011010100011
toggler: 1010001010010110
unknown: 1_1_0_1010_0001_ // 1 = runs & toggler, 0 = ~runs, _(unknown) = runs & ~toggler
result : 1111011010000011

Answer 1

这似乎是可能的，但充满了恼人的边缘情况和一些不完全 "nice" 的操作，尽管它们在技术上避免了迭代。

首先是精彩部分。对于每个 "group"，获取一个指示是否为该组打开了任何切换的位。一种方法可能是：进行切换，在一组后面的位中放入 "blocker" 1，然后减去每个组的起点。然后，如果组中没有设置切换，则 "blocker" 由借位重置。否则，如果设置了切换位，则该切换位 "eats" 借用和阻止程序将继续存在。在代码中：

runs_first = runs & ~(runs << 1);
runs_after = ~runs & (runs << 1);
toggles_blocked = toggles | runs_after;
selected_groups = runs_after & (toggles_blocked - runs_first);

您的数字示例（前置零，以避免不幸的边缘情况）：

runs           : 01111011010100011
toggles        : 01010001010010110
runs_first     : 00001001010100001
runs_after     : 10000100101000100
toggles_blocked: 11010101111010110
difference     : 11001100100110101
selected_groups: 10000100100000100

如果组是固定长度的，现在可以很容易地将这些单位标志扩展为整个组掩码。或者如果该位位于组的开头，它也可以放轻松。 Reversing the bits 使用减法技巧给出了解决方案：

rev_selected = reverse(selected_groups >> 1);
rev_runs = reverse(runs);
rev_runs_after = ~rev_runs & (rev_runs << 1);
rev_groupmask = (rev_runs_after - rev_selected) & rev_runs;
groupmask = reverse(rev_groupmask)

但即使 "efficient reverse" 也不是那么有效，除非有直接的硬件支持（例如 rbit 在 ARM 上，grevi 在 RISC-V 上扩展 B） .

是否有使用掩码打开和关闭位组的非迭代方法？

Is there a non-iterative method of toggling groups of bits on and off using a mask?

c++

algorithm

bit-manipulation