2

当尝试在没有循环的情况下测试直线上的可达性时，您可以使用 Bitboard 表示。想象一下国际象棋，棋盘的一行或一列表示为一个字节，以及一个问题，如果 X 方格上的 Rook 可以捕获方格 T 上的目标。

设 T：Target，X：Start，O：其他占用方格，_：空方格

我发现使用这些符号来可视化可能的场景很方便：

// __OXO___ -> X is between others on both sides
// __XOO___ -> X is leftmost of others
// __OOX___ -> X is rightmost of other others
//A: T_OOX___ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//B: T_XOO___ -> Target left of X, X leftmost    -> T > X and O < X -> reachable
//C: __OXO_T_ -> Target right of X, X embedded   -> T < X and ???? -> NOT reachable
//D: __OOX_T_ -> Target right of X, X rightmost  -> T < X and ???? -> reachable

这里有 4 个感兴趣的案例 - 来自 AD。情况 A 和 B 很容易处理。

但情况 C 和 D 不是。您不能简单地测试 > 或 < 来确定目标是否可达或路径是否被阻塞。

不过，可以做的是通过镜像字节中的位将 C、D 转换为 A、B。所以位 0 -> 位 7，位 1 -> 位 6，...

有谁知道是否有优化的实现来进行翻转？

编辑：我刚刚注意到另一种情况是：E：OT__X___ ...我的理论变坏了，但问题仍然存在。:)

4

4 回答 4

2

您可以在不反转的情况下进行此测试。如果x、t和o是您的示例中的位掩码（其中x和t仅设置了一个位，并且这些位未在 中设置o），那么您可以创建一个位掩码，其中包含 和 之间的位t，x如下所示：

tx = t | x
txhi = tx & (tx - 1)
return (txhi - 1) ^ (tx - 1)

这使用减 1 用“011...111”替换以“100...000”结尾的位模式。然后，您可以简单地检查此掩码是否与o.

于 2015-01-23T21:25:02.450 回答
1

代替

// __OXO___ -> X is between others on both sides
// __XOO___ -> X is leftmost of others
// __OOX___ -> X is rightmost of other others
//A: T_OOX___ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//B: T_XOO___ -> Target left of X, X leftmost    -> T > X and O < X -> reachable
//C: __OXO_T_ -> Target right of X, X embedded   -> T < X and ???? -> NOT reachable
//D: __OOX_T_ -> Target right of X, X rightmost  -> T < X and ???? -> reachable

在情况 C 和 D 中颠倒 X 和 T 似乎是合乎逻辑的：

//C: __OTO_X_ -> Target left of X x not leftmost -> T > X and O > X -> NOT reachable
//D: __OOT_X_ -> Target left of X, X leftmost    -> T > X and O < X -> reachable

我意识到如果 T 是主教而 X 是 Rook，那么 T 可能不会像 X 那样移动，但我们所做的只是看看 T 是否是 Rook 是否可以移动到 X。回答这个问题是一样的当 X 移动到 T 时。它可以或它不能回答相反的情况（X 可以移动到 T）。

于 2015-01-22T20:27:41.330 回答
0

对此有一些比特黑客解决方案（下面列出了一个示例），但如果您只处理单个字节，那么简单的 256 条目查找表可能是最有效的。

这是我在 FFT 黑客时代的个人代码库中的一个示例（不保证它符合现代 C 标准或任何东西 - 特别uint8是typedeffor unsigned char，但现代 C 有 IIRC，一个uint8_t可以达到目的的本机）：

inline uint8 bitrev8(uint8 n)
{ uint8 tmp = 0x55;
  n = (((n >> 1) & tmp) | ((n & tmp) << 1));

  tmp = 0x33;
  n = (((n >> 2) & tmp) | ((n & tmp) << 2));

  return ((n >> 4) | (n << 4));
}

由于大型查找表的不切实际，16 位、32 位和 64 位数据的相应例程比 8 位版本更胜一筹，这显然比简单的v = reversed[n];会解析更多的指令。 .

于 2015-01-22T20:27:29.647 回答
0

为每个字节制作一个 256 字节的查找表并使用它来代替执行任何计算。

于 2015-01-22T20:27:43.567 回答