在昨天的Code Jam预选赛中http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0，有一个名为Snapper Chain的问题。从比赛分析中我了解到，这个问题需要位运算技巧，如提取整数的右侧N位并检查它们是否都为1。我看到了一个参赛者（Eireksten）的代码，他使用以下方式执行上述操作：
(((K&(1<<N)-1))==(1<<N)-1)
我无法理解这是如何工作的。在比较中-1有什么用？如果有人能解释一下，对于我们这些新手来说会非常有用。另外，任何关于识别此类问题的提示都将不胜感激。我使用了一个简单的算法来解决这个问题，最终只解决了较小的数据集。(编译所需的更大数据集花了很长时间，而提交要求在8分钟内完成)。提前致谢。
以N=3为例，在二进制中，1<<3 == 0b1000。所以1<<3 - 1 == 0b111。
一般来说，1<<N-1会生成一个二进制形式中有N个1的数字。
设R = 1<<N-1。然后表达式变成了(K&R) == R。其中K&R将提取出最后N位，例如：
101001010
& 111
————————————
000000010
（回想一下，如果两个操作数在某位都为1，则按位AND运算将在该位返回1。）
当且仅当最后N位都为1时，等式成立。 因此，这个表达式检查K是否以N个1结尾。
1. (1<<N) = 001000 (shift function)
2. (1<<N)-1 = 000111 (http://en.wikipedia.org/wiki/Two's_complement)
3. K&(1<<N)-1 = 0000010 (Bitmask)
4. K&(1<<N)-1 == (1<<N)-1) = (0000010 == 000111) = FALSE
我正在解决Snapper Chain问题，来到这里寻找一个关于位操作算法的解释，我在解决方案中遇到了它。我找到了一些好的信息，但是对于一个位运算新手来说，我仍然花了很长时间才弄明白它。
以下是我尝试解释该算法及其如何得出的过程。如果我们枚举链中每个快门的所有可能的电源和开/关状态，我们会发现一种模式。以测试用例N=3，K=7（3个快门，7次快照）为例，我们展示了每个kth快照的每个快门的电源和开/关状态：
1 2 3
0b:1 1 1.1 1.0 0.0 -> ON for n=1
0b:10 2 1.0 0.1 0.0
0b:11 3 1.1 1.1 1.0 -> ON for n=1, n=2
0b:100 4 1.0 0.0 1.0
0b:101 5 1.1 1.0 1.0 -> ON for n=1
0b:110 6 1.0 0.1 0.1
0b:111 7 1.1 1.1 1.1 -> ON for n=2, n=3
当所有的snappers都开启并接收电源时，或者我们有一个第k个快照导致n个1时，灯泡就会亮起来。更简单地说，只要所有的snappers都是ON状态，灯泡就会亮起来，因为它们都必须接收电源才能保持ON状态（从而点亮灯泡）。这意味着对于每个k次快照，我们需要n个1。
此外，您可以注意到，k不仅对于满足n=3的k=7是所有二进制1，而且对于满足n=2的k=3和满足n=1的k=1也是如此。此外，对于n = 1或2，我们看到打开灯泡的每个快照数，k的最后n位数字始终为1。我们可以尝试推广，所有满足n个snappers的ks都将是以n个1结尾的二进制数。
我们可以使用早期帖子中提到的表达式，即1 << n - 1总是给我们n个二进制1，或在这种情况下，1 << 3 - 1 = 0b111。如果我们将n个snappers的链视为每个数字表示开/关的二进制数，并且我们想要n个1，则这给出了我们的表示形式。
现在我们想要找到那些1 << n - 1等于以n个二进制位为结尾的k的情况，我们可以通过执行按位与操作来实现： k & (1 << n - 1)获取k的最后n位，然后将其与1 << n - 1进行比较。
我想这种思维方式在处理这些类型的问题后会更自然，但对我来说仍然很吓人，我怀疑我永远不会靠自己想出这样的解决方案！
这是我的Perl解决方案：
$tests = <>;
for (1..$tests) {
($n, $k) = split / /, <>;
$m = 1 << $n - 1;
printf "Case #%d: %s\n", $_, (($k & $m) == $m) ? 'ON' : 'OFF';
}
我认为我们可以通过先手动计算一些 N 的系列（例如1,2,3,…）的答案来识别这种问题。之后，我们将识别出状态变化，然后编写一个自动化过程的函数（第一个函数）。运行程序以获取一些输入，并注意模式。
当我们获得模式时，编写表示模式的函数（第二个函数），并比较第一个函数和第二个函数的输出。
对于 Code Jam 情况，我们可以对小数据集运行两个函数，并验证输出。如果输出相同，则我们有很高的可能性使第二个函数能够及时解决大数据集。
10000 - 1 = 9999的计算过程，同样的过程也会出现在二进制中。 - Anycorn