使用位和数学运算的 JavaScript 扑克牌分析器

介绍  

在本文中，我将解释我如何从一个暴力破解的扑克牌型分析算法，演变成一个快速而简洁的 JavaScript 实现——仅用四行代码。代码本身不被认为是可读性好的代码，因此可能不那么有优势，但编写它的过程却非常有益。我对位操作的痴迷、利用弱类型变量的愿望以及改进古老扑克算法的长期使命，将我引向了扑克牌型分析的极客天堂。

背景 

在我十几岁的时候，我在 Commodore 64 上用 BASIC 编写了一个扑克游戏。它能工作。我为此感到自豪……但它慢得令人痛苦。不仅仅是因为 Commodore 64 只有区区 1.023 MHz 的处理器，分析牌型的算法本身也很糟糕。那时候，我已经对位操作产生了好奇。当时我没有意识到，用那些 1 和 0 到底能做什么。我还没有发现，在一个像 JavaScript 这样弱类型的语言中，可以如此简洁。一种语言可以让你在浮点数、整数和布尔值之间自由切换，这有潜力满足我的使命。

“用任何语言写一个算法，主要使用位/数学运算，这样我
 就能有一天重新审视那个 BASIC 代码，并赋予它应有的更快的算法。” 

虽然这是最初的使命，但它只是起到了推动作用。我偶然发现了一个网页，标题是 Sean Eron Anderson 的位技巧。这个页面上有一些真正的“魔法”。Sean 收集了当时已知的最好的位操作和优化。这是我接触梅森数的开端，从宏观上看，它成为了算法中关键操作的一部分。

代码 

四行主要代码呈现在 rankPokerHand 函数的顶部。

function rankPokerHand(cs,ss) {
 
  var v, i, o, s = 1<<cs[0]|1<<cs[1]|1<<cs[2]|1<<cs[3]|1<<cs[4];
  for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}
  v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
  v -= (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) * ((s == 0x7c00) ? -5 : 1);
  ... 

该函数接受两个数组。cs 数组是包含五张牌的点数（等级）的整数数组，A 的点数为 14（就像许多处理牌的算法中常见的）。ss 数组是包含五张牌的花色（标记值）的整数数组。乍一看，代码可能令人望而生畏。在我逐行解释代码之前，主要概念是使用了两个位字段来存储扑克牌型的点数和点数计数。 

位字段

第一个是 s 位字段。这个位字段的目的是为每个点数记录一个 1 位——重复的会被丢失。只需要 13 位，对应于牌的点数（2 - A）。最低的两位（LSBs）不使用，以便简化此位字段的加载。没有必要将这些位移到 13 个最低位，因为这里的牌点数值并不重要。重要的是它们与其邻居的接近程度。 

牌点数 (cs)	位字段 (s)	值 (十六进制)
2,3,4,5,6	[0,0,0,0,0,0,0,0,1,1,1,1,1,0,0]	不重要
2,4,6,7,9	[0,0,0,0,0,1,0,1,1,0,1,0,1,0,0]	不重要
A,2,3,4,5	[1,0,0,0,0,0,0,0,0,1,1,1,1,0,0]	0x403C
10,J,Q,K,A	[1,1,1,1,1,0,0,0,0,0,0,0,0,0,0]	0x7C00

第二个是 v 位字段。这个位字段的目的是记录每个点数的计数。在位字段中表示此信息有多种方法，但我最终想要的，是可以使用模运算符和适当的梅森数来对每个点数求和的方法。这部分留给读者去弄清楚，但本质上，它具有并行求和位字段中每个四位字节（nibble）的能力。

我需要一个方案，能够为所有点数重复的组合产生一个唯一的值（例如，一对、两对、三条、四条、葫芦）。

这里的位字段代表牌型（A,A,Q,Q,9）。

0	0	1	1	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A				K				Q				J				10				9				8				7				6				5				4				3				2

每个四位字节（4 位）负责捕获每个点数的计数。如果找到某个点数的两张牌，则会设置该四位字节的低 2 位。如果找到某个点数的两张牌，则会设置该四位字节的低 3 位。 

这里是一个葫芦（A,A,J,J,J）。

0	0	1	1	0	0	0	0	0	0	0	0	0	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A				K				Q				J				10				9				8				7				6				5				4				3				2

这里是一个四条（K,K,K,K,7）。

0	0	0	0	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
A				K				Q				J				10				9				8				7				6				5				4				3				2

从前面的例子中，A 的四位字节的值是 3（设置了低 2 位）。因此，J 的四位字节的值是 7（设置了低 3 位），K 的四位字节的值是 15（0xF）。

现在你已经理解了位字段的结构，有趣的是，一副扑克牌有 52 张牌，而 JavaScript 的浮点数使用 52 位来存储其尾数。

JavaScript 的 52 位浮点数尾数 

我意识到浮点数的二进制表示的细节可能不会让你感兴趣。如果这样，请随时跳到“逐行代码解析”部分。否则，请继续阅读。

JavaScript 的浮点数遵循 IEEE-754 标准。这个标准定义了很多细节，但最重要的是数字以二进制形式存储的方式。对于 64 位 IEEE-754 浮点数，该标准将最高有效位（MSB）作为符号位。这对于任何带符号数字格式都是常见的做法。接下来，11 位用于记录指数，其余位（52 位）用于记录归一化的尾数。该标准在处理某些十进制数表示时存在问题（这里不讨论），但对我们来说，它非常完美。

注意：我发现了一个很棒的网页，可以帮助可视化这个概念。 

相比之下，JavaScript 中的整数使用 32 位。这些数字允许你对它们应用位运算，如 AND(&)、OR(|) 和 XOR(^)。这对于读取和设置单个位非常有用，但这个问题需要完全访问 52 位才能成功。如前所述，JavaScript 的浮点数使用 64 位。“完美”，我想——直到我意识到你不能对它们执行位运算。当你这样做时，浮点数会被截断为较低的 32 位，并隐式转换为整数。

经过一些实验，我发现可以使用标准的数学运算符来实现所需的效果。乘法、除法和模除都支持浮点数，并且可以设置以根据需要进行掩码、读取和设置位。 

逐行代码解析  

第一行代码相当直接： 

var v, i, o, s = 1<<cs[0]|1<<cs[1]|1<<cs[2]|1<<cs[3]|1<<cs[4]; 

我们初始化了四个局部变量。位字段是 v 和 s，循环迭代器是 i，位偏移量是 o。如前所述，s 位字段使用一个位来表示我们扑克牌型中的每个点数。 

下一行代码是一个循环，用于填充 v 位字段，存储我们扑克牌型中点数的计数。 

for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}  

第一次迭代是浪费的。它只是为了避免每次迭代都重复计算 o 的值。第一次迭代直接进入循环体。在这里，v 增加 0，因为乘以 o 是乘以 0。有些人可能已经注意到，在乘法的另一边是除以 0。现在有些语言能够优化，如果乘以 0，则不计算表达式的其余部分，但 JavaScript 不会。相反，JavaScript 会计算整个表达式。这导致 0/0 = NaN，然后进行按位 AND。JavaScript 会很好地将此操作结果强制转换回 0，最后加 1。 

现在是时候设置 v 位字段中的位了。这实际上是通过一系列加法实现的。原因是 JavaScript 只允许对整数进行位操作。这意味着我们只能设置最低的 32 位，但这个策略需要设置 52 位中的任意位。我发现可以通过加法来实现这一点。由于没有位会被设置两次，并且主体表达式总是产生 2 的幂，所以这样做是安全的。 

其余的迭代将 i 设置在 0-4 的范围内，这是牌数组（cs）的索引。每次迭代，我们的位偏移量 o 会使用 Math.pow(2,cs[i]*4) 而不是更传统的 1<< cs[i]*4 来设置到适当的偏移量。这是因为 JavaScript 只允许对整数进行位移。即使数字存储为浮点数，其位仍然可以被操作。主体中的表达式会将所需的四位字节很好地右移到最低的四位。在这里，它可以很容易地用 15 (0xF) 进行掩码。此步骤不关心数字是否被截断到 32 位以执行此位操作，因为它只对最低的四位感兴趣。一旦隔离了相关的位，就将 1 加到该值上。这会使四位字节中的下一个最高位被设置。例如：0000 变为 0001，0011 变为 0100，0111 变为 1000。最后，将此值乘以偏移量 o 以将其恢复到正确的位置。魔法！

实际上，真正的“魔法”在于第三行代码。 

v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1); 

第一个操作是模除。你可能想知道 v % 15 到底能实现什么？如果你之前已经弄明白了，这具有对位字段中的每个四位字节的值求和的独特属性。有趣的是，无论你有什么牌，这个操作都会根据位字段中记录的点数计数的唯一性返回相同的值。使用之前的位字段示例，你可以看到单高牌（无对子）产生值为 5，一对产生 6，两对产生 7，三条产生 9，葫芦产生 10，四条产生 1（16%15）。这些值实际上在 1 到 10 的范围内，可以用作我们扑克 hands 数组的索引。到目前为止，我们有： 

hands = ["4 of a Kind","","","","High Card","1 Pair","2 Pair","","3 of a Kind","Full House"];  

数组是 0 索引的，所以我们需要从 v 的值中减去 1。这就是我们在下一个操作中所做的。 

v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1); 

现在是时候解析 OR 条件了。这正在检查牌型中是否存在顺子。由于我们的位字段 s 为每个点数设置了一个位，因此顺子将具有 5 个连续设置的位。请注意，具有 5 个最低位设置的位字段等于 31： 

[0,0,0,0,0,0,0,0,1,1,1,1,1] = 31 

通过将 s 除以其最低有效位 (s&-s) 来归一化位字段。这留给读者去弄清楚，但一个提示是，这需要知道整数的二进制补码表示。如果存在顺子，此条件将为真。有一个例外，那就是 A 点数低的顺子。由于 A 点数默认被视为高（14），因此还需要检查 s==0x403c。回看前面展示的例子，这个特殊情况以其位字段表示显示。如果发现存在顺子，则从 v 的值中减去 3。这覆盖了 0 索引数组所需的 1，再加上额外的 2。由于只有在没有重复牌的情况下才会出现顺子，v 的值最初为 5，然后变为 2（即 5-3）。我们的 hands 数组现在看起来像这样：  

hands = ["4 of a Kind","","Straight","","High Card","1 Pair","2 Pair","","3 of a Kind","Full House"]; 

最后一行代码用于进行最后剩余的调整。现在是时候检查我们花色数组（ss）中的信息了： 

v -= (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) * ((s == 0x7c00) ? -5 : 1); 

第一个比较检查我们是否是同花。JavaScript 会很好地将这个布尔值强制转换为整数（False 为 0，True 为 1）。如果没有同花，那么 v 中的索引已经正确，我们只需减去 0。如果有同花，这意味着 v 的值只能是单高牌或顺子。从这些索引中减去 1 会将单高牌变成同花，并将顺子变成顺子同花。只剩下一种类型的同花，即皇家同花。回到前面的例子，皇家同花的值是 s==0x7c00。由于我们的 hands 数组中只剩一个空位，它现在被占用，我们将 5 加到 v 上以进行最终调整。这是最终的代码：  

hands=["4 of a Kind", "Straight Flush", "Straight", "Flush", "High Card",
       "1 Pair", "2 Pair", "Royal Flush", "3 of a Kind", "Full House" ];
var A=14, K=13, Q=12, J=11, _ = { "♠":1, "♣":2, "♥":4, "♦":8 };
 
//Calculates the Rank of a 5 card Poker hand using bit manipulations.
function rankPokerHand(cs,ss) {
  var v, i, o, s = 1<<cs[0]|1<<cs[1]|1<<cs[2]|1<<cs[3]|1<<cs[4];
  for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}
  v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
  v -= (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) * ((s == 0x7c00) ? -5 : 1);
  document.write("Hand: " + hands[v] + (s == 0x403c?" (Ace low)":"")+"<br/>");
}
 
rankPokerHand([10, J, Q, K, A], [ _["♠"], _["♠"], _["♠"], _["♠"], _["♠"] ] ); // Royal Flush
rankPokerHand([ 4, 5, 6, 7, 8], [ _["♠"], _["♠"], _["♠"], _["♠"], _["♠"] ] ); // Straight Flush
rankPokerHand([ 2, 3, 4, 5, A], [ _["♠"], _["♠"], _["♠"], _["♠"], _["♠"] ] ); // Straight Flush
rankPokerHand([ 8, 8, 8, 8, 9], [ _["♠"], _["♣"], _["♥"], _["♦"], _["♠"] ] ); // 4 of a Kind
rankPokerHand([ 7, 7, 7, 9, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] ); // Full house
rankPokerHand([10, J, 6, K, 9], [ _["♣"], _["♣"], _["♣"], _["♣"], _["♣"] ] ); // Flush
rankPokerHand([10, J, Q, K, 9], [ _["♠"], _["♣"], _["♥"], _["♣"], _["♦"] ] ); // Straight
rankPokerHand([ 2, 3, 4, 5, A], [ _["♠"], _["♣"], _["♥"], _["♣"], _["♦"] ] ); // Straight
rankPokerHand([ 4, 4, 4, 8, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] ); // 3 of a Kind
rankPokerHand([ 8, 8, J, 9, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] ); // 2 Pair
rankPokerHand([ 8, 8, 3, 5, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] ); // 1 Pair
rankPokerHand([10, 5, 4, 7, 9], [ _["♠"], _["♣"], _["♥"], _["♠"], _["♣"] ] ); // High Card

结论 

弄清楚这个算法的细节，让我深入了 JavaScript 和位操作的许多我以前从未探索过的领域。虽然我永远不会在任何项目中使用这段代码，但熟悉语言的底层细节让我有信心知道我真正理解了它的工作原理。

修订历史 

• 2013 年 3 月 31 日 - 初次修订。 
• 2013 年 4 月 1 日 - 添加了标签并修正了拼写错误。