提取整数的最右边N位

Question

在yester Code Jam Qualification round 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个的数字.

我们R = 1<<N-1.然后表达式变为(K&R) == R.所述K&R将提取的最后N个比特,例如:

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

(回想一下,当且仅当两个操作数在该数字中都有1时,按位AND将返回一位数字.)

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