检查一个字符是否等于多个其他字符，分支越少越好
Checking if a char is equal to multiple other chars, with as little branching as possible
我正在编写一些处理字符比较的对性能敏感的 C# 代码。我最近发现了一个技巧，如果它们之间的差异是 2 的幂，你可以在没有分支的情况下判断一个 char 是否等于一个或多个其他字符。
例如，假设您要检查一个字符是 U+0020 (space) 还是 U+00A0（不间断 space）。由于两者相差0x80，所以可以这样做：
public static bool Is20OrA0(char c) => (c | 0x80) == 0xA0;
与这个天真的实现相反，如果字符不是 space:
，它会添加一个额外的分支
public static bool Is20OrA0(char c) => c == 0x20 || c == 0xA0;
第一个是如何工作的，因为两个字符之间的差异是 2 的幂，所以它正好设置了一位。因此，这意味着当您将它与字符进行“或”运算并导致某个结果时，恰好有 2 ^ 1 个不同的字符可能导致该结果。
无论如何，我的问题是，这个技巧能否以某种方式扩展到差异不是 2 的倍数的字符？例如，如果我有字符 # 和 0（顺便说一句，它们相差 13），是否有任何类型的位旋转 hack 我可以用来检查一个字符是否是等于其中任何一个，没有分支？
感谢您的帮助。
编辑： 作为参考，here 是我在 .NET Framework 源代码中第一次偶然发现这个技巧的地方，在 char.IsLetter 中。他们利用 a - A == 97 - 65 == 32 这一事实，并简单地将其与 0x20 进行 OR 以将字符大写（而不是调用 ToUpper）。
您可以使用相同的技巧与一组 2^N 个值进行比较，前提是它们的所有其他位都相等，但 N 位除外。例如，如果值集是 0x01、0x03、0x81、0x83，则 N=2，您可以使用 (c | 0x82) == 0x83。请注意，集合中的值仅在位 1 and/or 7 上不同。所有其他位都相同。可以应用这种优化的情况并不多，但是当它可以应用并且每一点额外的速度都很重要时，它就是一个很好的优化。
这与优化布尔表达式的方式相同（例如，在编译 VHDL 时）。您可能还想查找卡诺图。
也就是说，对字符值进行这种比较是非常糟糕的做法，尤其是使用 Unicode 时，除非您知道自己在做什么并且正在做非常底层的事情（例如驱动程序、内核代码等） .比较字符（与字节相对）必须考虑语言特征（例如 uppercase/lowercase、连字、重音、复合字符等）
另一方面，如果您只需要二进制比较（或分类），则可以使用查找表。对于单字节字符集，这些字符集可以相当小而且非常快。
如果您可以容忍乘法而不是分支，并且您测试的值只占用您正在使用的数据类型的低位（因此在乘以一个较小的常量时不会溢出，请考虑强制转换为更大的数据类型并使用相应更大的掩码值（如果这是一个问题），那么您可以将该值乘以一个常数以强制这两个值相隔 2 的幂。
例如，在#和0（十进制值35和48）的情况下，值相差13。向下舍入，最接近 2 到 13 的幂是 8，即 13 的 0.615384615。将其乘以 256 并向上舍入，得到 8.8 定点值得到 158。
这里是 35 和 48 的二进制值，乘以 158，以及它们的邻居：
34 * 158 = 5372 = 0001 0100 1111 1100
35 * 158 = 5530 = 0001 0101 1001 1010
36 * 158 = 5688 = 0001 0110 0011 1000
47 * 158 = 7426 = 0001 1101 0000 0010
48 * 158 = 7548 = 0001 1101 1010 0000
49 * 158 = 7742 = 0001 1110 0011 1110
可以忽略低 7 位，因为它们不是将任何相邻值彼此分开所必需的，除此之外，值 5530 和 7548 仅在第 11 位不同，因此您可以使用掩码和比较技术，但使用 AND 而不是 OR。二进制的掩码值为1111 0111 1000 0000（63360），比较值为0001 0101 1000 0000（5504），因此可以使用此代码：
public static bool Is23Or30(char c) => ((c * 158) & 63360) == 5504;
我没有分析过这个，所以我不能保证它比简单的比较更快。
如果您确实实现了这样的功能，请务必编写一些测试代码来循环遍历可以传递给函数的每个可能值，以验证它是否按预期工作。
如果没有分支确实是您最关心的问题，您可以这样做：
if ( (x-c0|c0-x) & (x-c1|c1-x) & ... & (x-cn|cn-x) & 0x80) {
// x is not equal to any ci
如果 x 不等于特定的 c，则 x-c 或 c-x 将为负，因此 x-c|c-x 将设置第 7 位。这应该适用于有符号和无符号的字符。如果你 & 它为所有 c's，只有当它为每个 c 设置时，结果才会设置第 7 位（即 x 不等于它们中的任何一个）
我正在编写一些处理字符比较的对性能敏感的 C# 代码。我最近发现了一个技巧，如果它们之间的差异是 2 的幂，你可以在没有分支的情况下判断一个 char 是否等于一个或多个其他字符。
例如，假设您要检查一个字符是 U+0020 (space) 还是 U+00A0（不间断 space）。由于两者相差0x80，所以可以这样做：
public static bool Is20OrA0(char c) => (c | 0x80) == 0xA0;
与这个天真的实现相反，如果字符不是 space:
，它会添加一个额外的分支public static bool Is20OrA0(char c) => c == 0x20 || c == 0xA0;
第一个是如何工作的，因为两个字符之间的差异是 2 的幂，所以它正好设置了一位。因此，这意味着当您将它与字符进行“或”运算并导致某个结果时，恰好有 2 ^ 1 个不同的字符可能导致该结果。
无论如何，我的问题是，这个技巧能否以某种方式扩展到差异不是 2 的倍数的字符？例如，如果我有字符 # 和 0（顺便说一句，它们相差 13），是否有任何类型的位旋转 hack 我可以用来检查一个字符是否是等于其中任何一个，没有分支？
感谢您的帮助。
编辑： 作为参考，here 是我在 .NET Framework 源代码中第一次偶然发现这个技巧的地方，在 char.IsLetter 中。他们利用 a - A == 97 - 65 == 32 这一事实，并简单地将其与 0x20 进行 OR 以将字符大写（而不是调用 ToUpper）。
您可以使用相同的技巧与一组 2^N 个值进行比较，前提是它们的所有其他位都相等，但 N 位除外。例如，如果值集是 0x01、0x03、0x81、0x83，则 N=2，您可以使用 (c | 0x82) == 0x83。请注意，集合中的值仅在位 1 and/or 7 上不同。所有其他位都相同。可以应用这种优化的情况并不多，但是当它可以应用并且每一点额外的速度都很重要时，它就是一个很好的优化。
这与优化布尔表达式的方式相同（例如，在编译 VHDL 时）。您可能还想查找卡诺图。
也就是说，对字符值进行这种比较是非常糟糕的做法，尤其是使用 Unicode 时，除非您知道自己在做什么并且正在做非常底层的事情（例如驱动程序、内核代码等） .比较字符（与字节相对）必须考虑语言特征（例如 uppercase/lowercase、连字、重音、复合字符等）
另一方面，如果您只需要二进制比较（或分类），则可以使用查找表。对于单字节字符集，这些字符集可以相当小而且非常快。
如果您可以容忍乘法而不是分支，并且您测试的值只占用您正在使用的数据类型的低位（因此在乘以一个较小的常量时不会溢出，请考虑强制转换为更大的数据类型并使用相应更大的掩码值（如果这是一个问题），那么您可以将该值乘以一个常数以强制这两个值相隔 2 的幂。
例如，在#和0（十进制值35和48）的情况下，值相差13。向下舍入，最接近 2 到 13 的幂是 8，即 13 的 0.615384615。将其乘以 256 并向上舍入，得到 8.8 定点值得到 158。
这里是 35 和 48 的二进制值，乘以 158，以及它们的邻居：
34 * 158 = 5372 = 0001 0100 1111 1100
35 * 158 = 5530 = 0001 0101 1001 1010
36 * 158 = 5688 = 0001 0110 0011 1000
47 * 158 = 7426 = 0001 1101 0000 0010
48 * 158 = 7548 = 0001 1101 1010 0000
49 * 158 = 7742 = 0001 1110 0011 1110
可以忽略低 7 位，因为它们不是将任何相邻值彼此分开所必需的，除此之外，值 5530 和 7548 仅在第 11 位不同，因此您可以使用掩码和比较技术，但使用 AND 而不是 OR。二进制的掩码值为1111 0111 1000 0000（63360），比较值为0001 0101 1000 0000（5504），因此可以使用此代码：
public static bool Is23Or30(char c) => ((c * 158) & 63360) == 5504;
我没有分析过这个，所以我不能保证它比简单的比较更快。
如果您确实实现了这样的功能，请务必编写一些测试代码来循环遍历可以传递给函数的每个可能值，以验证它是否按预期工作。
如果没有分支确实是您最关心的问题，您可以这样做：
if ( (x-c0|c0-x) & (x-c1|c1-x) & ... & (x-cn|cn-x) & 0x80) {
// x is not equal to any ci
如果 x 不等于特定的 c，则 x-c 或 c-x 将为负，因此 x-c|c-x 将设置第 7 位。这应该适用于有符号和无符号的字符。如果你 & 它为所有 c's，只有当它为每个 c 设置时，结果才会设置第 7 位（即 x 不等于它们中的任何一个）