位于 A 和 B（包括两者）之间的所有自然数中的位与

Question

我在一个竞争性问题网站上遇到了这个问题。这是问题所在：-

问题陈述

你将得到两个整数 A 和 B。你需要计算 A 和 B 之间（包括两者）之间的所有自然数的按位与。

修复编辑器中的代码，使其解决上述问题。您需要完成由“~~Fill this line”标记的缺失行。不要修改或插入任何其他行，否则即使您的代码正确，您也会得到错误的答案。

输入格式

输入的第一行包含 T，即要遵循的测试用例数。换行符中的每个测试用例包含由单个 space.

分隔的 A 和 B

约束：

1<=T<=200
0≤A≤B<2^32

输出格式 每个测试用例输出一行，需要按位与。

示例输入

3

12 15

2 3

8 13

示例输出

12

2

8

这是我们必须填充缺失行的代码：

import java.math.BigInteger;
import java.util.Scanner;

public class Magic4 {

   public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);

      int T = scanner.nextInt();

      for (int t = 0; t < T; t++) {
         long l = scanner.nextLong();
         long r = scanner.nextLong();
         long res = 0;
         for (long i = 0; i < 32; i++) {// I can make out that we are dealing with 32 bit numbers hence we are setting the condition as i < 32, but after that the proceedings in the loop are vague.
            if ((r - l + 1 == 1))
               if(l%2==1)
                  ~~Fill this line~~
            l >>= 1; r >>= 1;
         }
         System.out.println(res);
      }

      scanner.close();
   }
}

问题我就是没法解决，就是花了一些时间才填上正确的行。我可以看出我们正在处理 32 位数字，因此我们将条件设置为 i < 32，但之后循环中的程序是模糊的。如果你能辨认出什么，请告诉我。

Answer 1

res = res | (1 << i);

循环的每次迭代测试两个数字（A 和 B，或代码中的 l 和 r）最左边的 32-i 位是否等于彼此。如果是，则 A 和 B 之间所有数字的按位 AND 的结果必须包含 1，因为 A（或 B）的每个 32-i 位包含 1.

因此，如果 r - l + 1 == 1（即 r==l）和 l%2==1，结果的第 i 位必须为 1。

Answer 2

优化代码（在 Hackerrank 上测试）

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int nTestCases;
    unsigned int nStart, nEnd;

    scanf("%d", &nTestCases);

    while (nTestCases--)
    {
        scanf("%u %u", &nStart, &nEnd);
        unsigned int nWalk = (nEnd - nStart);
        unsigned int nMask = 1;
        while (nWalk)
        {
            nWalk >>= 1;
            nMask <<= 1;
        }
        nMask = nMask - 1;

        printf("%u\n", (nStart & ~nMask & nEnd));
    }
    return 0;
}

位于 A 和 B（包括两者）之间的所有自然数中的位与

Bit AND amongst all natural numbers lying between A and B (both inclusive)

java

algorithm

bit-manipulation