时间戳

首页 > 解决方案 > 是否有使用掩码打开和关闭位组的非迭代方法？

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

问题描述

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

runs   : 1111011010100011
toggler: 1010001010010110

是否存在一种方法来屏蔽这两个位字符串，或者以其他方式在迭代之外利用 c++ 的任何特性（尽管越通用/独立于语言越好），来生成一个result位字符串，其中包含runs具有1 的每一次运行至少一位有相应的 1 in toggler？使用提供的示例值的一个工作示例如下所示：

runs   : 1111011010100011
toggler: 1010001010010110
result : 1111011010000011

其中第一个、第二个、第三个和第四个 1runs都具有至少一个 1 对应于它们在 中的组成位toggler。

到目前为止，我很明显可以识别一些 0 的位置，即对应于 的位。很明显，一些1 的位置可以识别为。给定此信息，如果在未知位运行的任一端的位为零，则任何剩余的未知位（相当于满足条件的位）都可以确定为 0。这可以在下面的位串中再次看到：result~runs resultruns & togglerruns & ~togglerunknown

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

标签： c++algorithmbit-manipulation

解决方案

这似乎是可能的，但充满了烦人的边缘情况和一些并不完全“好”的操作，即使它们在技术上避免了迭代。

首先是好的部分。对于每个“组”，获取一个指示是否为该组打开了任何切换的位。一种方法可能是：使用切换开关，在一组之后的位中放入一个“阻塞器”1，然后减去每个组的起点。然后，如果没有在组中设置切换，则借用重置“阻塞器”。否则，如果有一个切换设置，该切换位会“吃掉”借位，阻止程序继续存在。在代码中：

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

如果这些组是固定长度的，那么现在将这些单个位标志扩展为整个组掩码将很容易。或者如果该位位于组的开头，那也很容易。反转位给出了一个解决方案，使用减法技巧：

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)

但即使是“有效的反向”也不是那么有效，除非有直接的硬件支持（例如rbit在 ARM 上，grevi在带有扩展 B 的 RISC-V 上）。

推荐阅读