java - 提取整数的最右边的N位

在昨天的“代码卡纸资格鉴定”回合http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0中，存在一个名为“鲷鱼链”的问题。从竞赛分析中，我知道问题需要进行一些困惑的事情，例如提取整数的最右边的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个数字的数字。

让R = 1<<N-1。然后，表达式变为(K&R) == R。 K&R将提取最后N位，例如:

     101001010
  &        111
  ————————————
     000000010

(回想一下，当且仅当两个操作数在该数字中都为1时，按位与运算符才会在该数字中返回1。)

当且仅当最后N位全为1时，等式成立。因此，表达式检查K是否以N结尾。