bit-manipulation - 数字范围的 BITWISE AND(&)

Question

给定两个数字 L & R ，查找 L 和 R 之间的所有数字的按位与

约束 1<= L,R <= (2^32) .

LL step = 1;
    while(L!=R)
    {
        L/=2; R/=2; step*=2;
    }
    cout<<L*step<<endl;

任何人都可以帮助我解释上述代码背后的解释或逻辑吗？

Answer 1

所以是的，这有点难，需要在纸上画草图。一旦你有了这个想法，这很简单。我将从英文解释开始，然后是简单的例子。最重要的是让您从我们正在对两个数字进行位运算这一事实中解脱出来，并考虑它们之间的数字。

首先，让我们说一些规则:
1) 如果两个数相等，则它们之间不会有数。
2) 如果两个数不相等，则它们之间的连续数将在每个数字处包含零，因此它们的按位 AND 将为零。

在进入示例之前，我们应该解释一下上面的简单算法。

1) 每次除以二从数字右边去掉一个二进制数字。 (这是在二进制中除以两种方式的方式)。
2) 每次除法时，我们都将步长变量加倍。很简单， step 变量更像是一个计数器，它保存两个数字相等之前的最高数字值。

假设我们有以下示例:

电话:11110001
电话:11110011

S=1(二进制 00000001)

将您的算法应用于这些值:

由于 L 和 R 还不相等，因此从每个数字中截取一个二进制数字(每个都除以 2)并将 S 乘以 2；
在第一轮他们变成

电话:1111000
电话:1111001

S=2(二进制 00000010)

既然还不相等，那就再做一次，结果是:

电话:111100
电话:111100

现在它们相等，循环中断，结果

是左数(或右数，因为它们相等)* S 值。

当我们在二进制中乘数时，我们在右边添加一个零。这里我们需要 3 个零，因为 S 是 00000010

11110000 符合预期。

结论:通过除法继续斩波，直到两者相等并且它们之间没有任何东西。当您这样做时，请不断更新您所在的步骤:)