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

Question

在昨天的 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 分钟内提交的较大数据集花了很多时间。)。提前致谢。

Answer 1

让我们以 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 时，按位与将返回 1。)

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