使用相邻单元格值的按位运算确定单元格值

Question

一个 r*c 网格只有 0 和 1。在每次迭代中，如果有任何相邻的单元格（上，下，左，右）与其相同，则当前单元格的值将被翻转。现在，如何想出一个按位公式来做到这一点。它可以用一个简单的 if 条件来完成，但我想知道执行此操作的按位运算，以便整个操作可以每行完成一次。

我说的是 this problem . I saw a solution using this concept here。但我不明白这是如何通过异或运算来确定单元格值的。

ans[i] ^= ((l ^ r) | (r ^ u) | (u ^ d)) | (~s[i] ^ l);
ans[i] &= prefix;

任何帮助将不胜感激:D

Answer 1

首先，将 s[i]、l、r、u 和 d 视为单位，即布尔变量.

s[i]（在这个答案中缩写为s）是要更新的单元格的旧颜色。
l、r、u、d是相邻单元格left、right、上面( up)，以及要更新的单元格下方 (down)。
ans[i]（本回答简写为ans）是更新后单元格的新颜色。
我们初始化 ans = s 并仅在需要时更新它。

回忆一下单格 C 的游戏规则：

如果与 C 相邻的所有单元格都具有与 C 相反的颜色，则 C 保持其颜色。
否则（如果与C相邻的单元格与C具有相同的颜色），C改变其颜色。

是否有各种相邻颜色？

对于第一个条件，您可以使用快速失败的方法。无论 C 的颜色如何，如果相邻的单元格有不同的颜色（有些是 0，有些是 1），那么 C 会改变它的颜色。要检查相邻单元格l、r、u和d是否有不同的颜色，你只需要三个检查✱:

various_adjacent_colors = (l != r) || (r != u) || (u != d)

按位表示，这是
various_adjacent_colors = (l ^ r) | (r ^ u) | (u ^ d)

_{✱ 不需要像 r != d 这样的 "missing" 检查。换个角度想：如果所有三个检查都失败了，那么我们就知道 (l == r) && (r == u) && (u == d)。在这种情况下，从 == 的传递性可以得出 (l == u)、(l == d) 和 (r == d)。所以，所有的颜色都是一样的。}

各种相邻颜色的快速失败

如果我们找到各种相邻的颜色，那么我们改变s：

if (various_adjacent_colors)
  ans = !s

按位表示，这是
ans ^= various_adjacent_colors

所有颜色都一样吗？

如果我们没有快速失败，我们知道所有相邻颜色彼此相等，但如果它们等于 s 则不是。如果 s == all_adjacent_colors 那么我们改变 s 如果 s != all_adjacent_colors 那么我们保留 s.

if (!various_adjacent_colors && s == l) // l can be replaced by either r, u, or d
  ans = !s

按位表示，这是
ans ^= ~various_adjacent_colors & ~(s ^ l) 或
ans ^= ~various_adjacent_colors & (~s ^ l)

把所有东西放在一起

现在让我们内联（并稍微简化）所有按位表示法：

vari = (l ^ r) | (r ^ u) | (u ^ d); ans ^= vari; ans ^= ~vari & (~s ^ l) 等同于
vari = (l ^ r) | (r ^ u) | (u ^ d); ans ^= vari | (~s ^ l) 等同于
ans ^= ((l ^ r) | (r ^ u) | (u ^ d)) | (~s ^ l)

似曾相识，对吧？ :)

从单个位到位向量

到目前为止，我们只考虑了单个位。 linked solution 使用位向量来同时更新 2D 游戏板一行中的所有 bits/cells。这种方法只在游戏板的边界处失败：

从 r = s[i] << 1 开始，游戏板最终可能会比应有的更大。 ans[i] &= prefix 通过屏蔽突出的位来修复大小。
在顶部和底部行更新不起作用，因为 u = s[i-1] 和 d = s[i+i] 不存在。作者在 for 循环中更新这些行 "manually"。
每行中最左边和最右边的单元格的更新可能是错误的，因为 r = s[i] << 1 和 l = s[i] >> 1 在 "adjacent" 个彩色单元格中移动 0 这实际上并不在游戏中。作者在另一个 for 循环中更新这些单元格 "manually"。

顺便说一下：除了上述 "manual" 边框更新之外，还有一个（更好？）替代方案，即通过额外 稍微扩大游戏板virtual row/column 在每个边界。在每次游戏迭代之前，虚拟 rows/columns 都会被初始化，这样它们就不会影响更新。然后像往常一样更新实际游戏板。虚拟 rows/columns 不必存储，而是使用 ...

// define once for the game
bitset<N> maskMsb, maskLsb;
maskMsb[m-1] = 1;
maskLsb[0] = 1;
// define for each row when updating the game board
bitset<N> l = (s[i] >> 1) | (~s[i] & maskMsb);
bitset<N> r = (s[i] << 1) | (~s[i] & maskLsb);
bitset<N> u = i+1 <= n-1 ? s[i+1] : ~s[n-1];
bitset<N> d = i-1 >= 0   ? s[i-1] : ~s[0];

使用相邻单元格值的按位运算确定单元格值

Determining cell value using bitwise operation with adjacent cell values

c++

bit-manipulation

bit

bitwise-operators

是否有各种相邻颜色？

各种相邻颜色的快速失败

所有颜色都一样吗？

把所有东西放在一起

从单个位到位向量