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

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

1) 每除以二意味着从数字的右边删除一个二进制数字。（这就是二进制中除以二的方式）。 2) 每次除法，我们都会将 step 变量加倍。很简单，step 变量更像是一个计数器，在两个数字相等之前保存最上面的数字值。

假设我们有以下例子：

大号：11110001 R : 11110011

S=1（二进制为00000001）

在这些值上应用您的算法：

因为L和R还不相等，所以从每一个中截取一个二进制数（每个都除以2）并将S乘以2；第一轮他们变成了

大号：1111000 R : 1111001

S=2（二进制为00000010）

还不相等，再做一遍，结果为：

大号：111100 R : 111100

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

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

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

11110000 符合预期。

结论：通过除法不断切分，直到两者相等，并且它们之间没有任何东西。当你这样做时，不断更新你所处的步骤:)

Answer 2

首先让我们考虑一下按位与对两个数字执行什么操作，例如（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 的公共位从左到右保留到第一个不同的位，其余的补零。

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

BITWISE AND(&) 用于数字范围

BITWISE AND(&) for Range of Numbers

bit-manipulation

bitwise-operators

bitwise-and