按位与(&)用于数字范围内的操作。

Question

给定两个数L和R，找出所有介于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;

有人能帮我解释一下上述代码背后的逻辑吗？

- naveensangtani

Answer 1

所以是的，这有点难，需要在纸上画草图。一旦理解了就很简单了。我将从英语解释开始，然后提供一个简单的例子。最重要的是，让自己从二进制位运算中解放出来，思考两个数之间的数字。

首先，让我们规定一些规则： 1）如果两个数相等，则它们之间没有数字。 2）如果两个数不相同，则它们之间的连续数字在每个二进制位上都包含零，因此它们的按位 AND 将为零。

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

1）每次除以二意味着从数字右侧删除一个二进制位。(这就是在二进制中除以二的含义) 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值。

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

11110000，正如预期的那样。

结论：不断将它们除以二，直到它们都相等且之间没有数字。在这样做的同时，保持更新您正在执行的步骤:)

- Omar Zaarour

Answer 2

首先让我们思考一下按位与运算对两个数字的作用，例如（0b表示二进制）

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

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

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

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

现在考虑一个范围

[m = 0bxyz0acd，n = 0bxyz1rst] 这里的xyzpacdrst都是二进制数字。

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

(1) m' = 0bxyz0111 (2) n' = 0bxyz1000 范围[m，n]中所有数字的按位AND操作只是两个特殊数字的按位AND操作

rangeBitwiseAnd（m，n）= m' & n'= 0bxyz0000 这告诉我们，范围的按位与保留从左到右相同的m和n的公共位，直到它们不同的第一位，其余补零。

- Aswin Prasad

Answer 3

当我们对一系列数字执行'＆'操作时，如果结果中的某个二进制位是0，则表示该二进制位曾经为0。因此，我们可以将每个二进制位向右移，直到两个值不同。当两个值相同时，左移不同的位数。代码如下：

    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);
        }
    }

- Kirti Chaturvedi