难以理解数字序列的按位与，提供的代码

Question

如果给定两个整数 A 和 B，其中 0 <= A <=B <= 2^32。计算 (A,B) 范围内整数的按位与。例如，A=12 和 B=15，

12 & 13 & 14 & 15 = 12

我的助教没有做太多解释如何解决问题，而是在办公时间结束时给每个人留下了解决方案，现在，我无法解决这个问题，但我也不会不懂解决办法。在下面的代码中，我标出了我理解和不理解的行。

我已经尝试用笔和纸的方法用小的 A 和 B 做我自己的例子，虽然我可以想象代码的工作，但我无法理解代码工作背后的理论。

private void run() {
        Scanner in = new Scanner(System.in);

        long a = in.nextLong();
        long b = in.nextLong();
        long diff = Math.max(((long) (Math.log(b - a) / Math.log(2)) - 1), 0);
        //what does diff represent?

        long shiftA = a >> diff;    //right shift by diff okay
        long shiftB = b >> diff;    // " "
        long result = shiftA;
        for (long j = shiftA; j <= shiftB; j++) {
            result = result & j;    //don't understand the loop
        }
        result = result << diff;    //left shift, but why?
        System.out.println(result);
    }
}

Answer 1

更简单，也更容易理解：

 long result = firstValue;
 for ( long i=result+1; i <= lastValue; i++ ) {
   result &= i;
 }

Answer 2

what does diff represent?

diff 使用 change of base formula for logarithms 来计算表示差异 b-a 的位数。如果差值用 K 位来表示，那么 [a..b] 范围内的一个数的结果的最后 K-1 位将全部设置为零，这意味着您可以清除结果出来了。因此最后左移 diff：它将 diff 零移到结果中。

I don't understand the loop

循环通过减少 2^diff 次的位表示，即仅使用 a 和 b 的高位。由于较低的 diff 位无论如何都会设置为零，因此此解决方案按 2^diff 计数而不是按 1 计数，从而减少了到达所需的时间结果。

考虑 a=23 和 b=39 的示例。 diff 等于 3。以下是表示，用逗号分隔最后 3 位：

d       b
-- -------
23 010,111
24 011,000
25 011,001
26 011,010
27 011,011
28 011,100
29 011,101
30 011,110
31 011,111
32 100,000 <<-- The last diff bits will be set to zero somewhere in the range
33 100,001
34 100,010
35 100,011
36 100,100
37 100,101
38 100,110
39 100,111

由于保证最后三位全部为零，因此循环可以按八计数，而不是按一计数。这将执行速度降低了八倍。以八为单位计数是先将数字右移 diff，然后以一计数，然后向左移动 diff。

Answer 3

diff 部分只是一个优化，使代码更加复杂和棘手（在某些边缘情况下可能是错误的）以节省一些运行时间。（一般来说，只有当性能很重要并且只有经过良好的测试时，这才是一个好主意。在这里，我们可以很容易地花更多的时间来理解优化并使其正确，而不是保存运行未优化的程序几次。）

让我们首先讨论基本循环，设置diff = 0。所以 a >> diff == a 和 result << diff == result，所以我们可以忽略所有这些。

主循环直接执行解决方案：

long result = a;
for (long j = a; j <= b; j++) {
    result = result & j;
}

也就是说，位和 (&) 范围 [a .. b] 中的每个值一起。给定 a = 12 和 b = 15，即 12 & 13 & 14 & 15。（实际上，如果你仔细地手动模拟它，你会注意到它计算 12 & 12 & 13 & 14 & 15，得到相同的结果。）这是理解的重要部分，基本循环和按位数学。

diff 部分通过丢弃低位使代码更快。例如。如果某些输入值计算 diff == 4，则 a >> 4 移出 a 的低 4 位，本质上是 a / 16，因为 2⁴ == 16. 然后循环将运行 1/16 次。然后代码将结果向上移动 result << 4，移入 0 位，本质上是 a * 16.

关于diff的值，注意Math.log(b - a) / Math.log(2) == log₂(b - a)，也就是[中的位数=29=]。它正在计算最终将变为零的低阶位的数量，以便它可以将它们移出，循环更少的次数，然后在最后移入零。

难以理解数字序列的按位与，提供的代码

Trouble understanding bitwise AND of number sequence, code provided

java

bit-manipulation

bitwise-operators