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

Question

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

12 & 13 & 14 & 15 = 12

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

我尝试过使用笔和纸的方法用小的 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

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，以八为单位进行计数。