数字范围的BITWISE和(&)

Question

给定两个数字L&R，找到位于L和R之间的所有数字的逐位AND

Constraints 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意味着从数字的右边移去一个二进制数。(这是如何在二进制中除以两个方法)。2)每次除法时，我们将步长变量加倍。简单地说，step变量更像是一个计数器，它在两个数字相等之前保存最顶端的数字值。

假设我们有以下示例：

L: 11110001 R: 11110011

S=1 (二进制为00000001)

对以下值应用您的算法：

由于L和R还不相等，所以从每个数字中切下一个二进制数字(每个数字除以2)，然后将S乘以2；在第一轮中，它们变成

L: 1111000 R: 1111001

S=2 (二进制为00000010)

因为它们还不相等，所以再做一次，结果是：

L: 111100 R: 111100

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

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

当我们在二进制中乘法时，我们在右边加一个零。这里我们需要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这告诉我们，范围的逐位and从左到右保持m和n的公共位，直到它们不同的第一位，其余的填充零。

Answer 3

当我们在结果答案中对一个数字范围做'&‘时，如果一个位是0，这意味着该位曾经是0。所以我们可以向右移位每一位，直到两个值不同的点，然后向左移位different.The编码的总比特数

    class Solution {
        public int rangeBitwiseAnd(int m, int n) {

            // if m !==n that means one of the bits is 0 so keep right shifting 
           //untill all the bits in both are same  and when they are same number of 
           //shift will be equal to number of bits not same just right shift it then

            int s = 0;
            while(m !=n){
                m =  m>>1;
                n = n>>1;

                s++;
            }
             return (m<<s);
        }
    }