通过位运算检查数字是否在特定范围内

Question

我在ICU库（国际Unicode组件）的"source\common\unicode\utf.h"文件中发现了一些有趣的位操作技巧。这些位操作技巧旨在检查一个数值是否在特定范围内。

// Is a code point in a range of U+d800..U+dbff?
#define U_IS_LEAD(c) (((c)&0xfffffc00)==0xd800)

我已经解决了这个魔数（0xfffffc00）的来源：

MagicNumber = 0xffffffff - (HighBound - LowBound)

然而，我也发现这个公式并不适用于任意范围。这里是否有人知道在什么情况下该公式有效？

是否有其他位运算方法可以检查一个数字是否在特定范围内？

- Astaroth

---

对于任意范围，您需要使用不同的方法：确定一个整数是否在两个已知值之间（包括边界）的最快方法。 - phuclv

Answer 1

为了使用这些技巧，这些数字必须在它们的二进制表示中具有一些共同的特征。

0xD800 == 0b1101_1000_0000_0000
0xDBFF == 0b1101_1011_1111_1111

这个测试实际上是屏蔽掉最低的10位。通常会写成：

onlyHighBits = x & ~0x03FF

在这个操作（"and not"）之后，onlyHighBits 的最低十位被保证为零。这意味着，如果这个数字现在等于区间的下限，那么它之前一定在区间内部。

这个技巧适用于所有情况下，区间的下限和上限在二进制中以相同的数字开头，并且在某个时候，下限只有零而上限只有1。在您的示例中，这是从右边数第十个位置开始的。

- Roland Illig

---

你能提供“通常写作”的任何参考资料吗？就个人而言，我发现使用a &~ b代替a & ~b不太直观，而且a & b == c比a & ~d == e更直观，因为即使只是我的个人偏好，也有更少的操作。 - CB Bailey

请注意，a & b == c不意味着您可能认为它意味着什么（它意味着a & (b == c)）。 a＆〜b在词法上与a＆〜b完全相同，我同意后者更好一些，仅因为这通常是这样做的方式。 - Barry Kelly

Answer 2

如果您没有2的x次方的边界类型，可以使用以下技巧：

如果x >= 0且x < N，您可以通过以下方式检查两者：

  if Longword( x ) < Longword( N ) then ...

这是因为有符号数中的负数对应于无符号数据类型中的最大数值。当范围检查被禁用时，您可以将此扩展为：

  if Longword( x - A ) < Longword ( ( B - A ) ) then ...

现在，您已经将两个测试（范围[A，B>）放入了SUB和CMP中，再加上一个单独的Jcc，假设（B-A）已经预先计算好了。

我只在真正需要时使用这些优化；例如，它们倾向于使您的代码不太可读，并且每个测试只能节省几个时钟周期。

注：对于像C语言一样的语言读者：Longword是Delphi的无符号32位数据类型。

- Ritsaert Hornstra

Answer 3

如果你要查找的范围从2的幂次方倍数开始（也就是，在二进制形式的数字的末尾有1或多个0），并且范围的大小为2的n次方-1（也就是，low&high == low and low|high == high），那么这个公式就适用。

- Vatine

---

你测试过了吗？假设数字是9，范围是8..8+(2^14-1)，这个公式不适用于这种情况。 - Astaroth

嗯... N 需要小于基础数字末尾的 0 的个数（因此对于 8，N 可以在 1-3 的范围内）。我认为这太明显了，不值得一提。 - Vatine