提取整数最右边的 N 位

algorithm java bit-manipulation

2022-09-02 20:52:43

在 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分钟内提交。提前致谢。

答案 1

让我们以 N=3 为例。在二进制中，.所以。1<<3 == 0b10001<<3 - 1 == 0b111

通常，创建一个具有 N 个二进制形式的数字。1<<N - 1

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

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

（回想一下，按位 AND 将在一个数字中返回 1，当且仅当两个操作数在该数字中都有一个 1。

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

答案 2

例如：N=3，K=101010

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