BITWISE和(&)的数字范围

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)如果两个数字不相等,则它们之间的连续数字将在每个数字处包含ZERO,因此它们的按位AND将为零.

在进入示例之前,我们应该解释上面的简单算法.

1)每个除以2表示从数字右侧删除一个二进制数字.(这是如何用二进制除以两种方式).2)每次分割时,我们将步长变量加倍.简单来说,步变量更像是一个计数器,它在两个数字相等之前保持最高位数值.

假设我们有以下示例:

L:11110001 R:11110011

S = 1(二进制00000001)

将算法应用于这些值:

由于L和R不相等,从每个中断一个二进制数字(每个除以2)并将S乘以2; 在第一轮他们成为

L:1111000 R:1111001

S = 2(二进制00000010)

由于它们不相等,所以再做一次,结果是:

L:111100 R:111100

现在他们是平等的,循环中断和结果

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

当我们在Binary中加倍时,我们在右边添加一个零.这里我们需要3个零,因为S是00000010

11110000这是预期的.

结论:通过分割保持切碎直到两者相等并且它们之间没有任何东西.当你这样做时,不断更新你在哪一步:)

Answer 2

首先让我们考虑一下对两个数字进行按位 AND 的操作，例如（0b 表示基数为 2）

4 & 7 = 0b100 & 0b111 = 0b100
5 & 7 = 0b101 & 0b111 = 0b101
5 & 6 = 0b101 & 0b110 = 0b100

运算符 & 保留在两个数字中设置的那些位。

对于多个数字，运算符 & 将保留每个数字中为 1 的那些位。

换句话说，任何数字中的位为 0 将导致答案的相应位为 0。

现在考虑一个范围

[m = 0bxyz0acd, n=0bxyz1rst] 这里的 xyzpacdrst 都是以 2 为底的数字。

我们可以在 [m, n] 范围内找到两个特殊的数字

(1) m' = 0bxyz0111 (2) n' = 0bxyz1000 [m, n] 范围内所有数的按位与就是两个特殊数的按位与

rangeBitwiseAnd(m, n) = m' & n' = 0bxyz0000 这告诉我们，范围的按位和是从左到右保持 m 和 n 的公共位，直到它们不同的第一个位，为休息。