Phép AND bitwise trên khoảng số trong C++

Cho khoảng [m, n] với 0 <= m <= n <= 2147483647. Tìm kết quả của phép AND bitwise trên tất cả các số trong khoảng này (bao gồm cả hai đầu).

Ví dụ: [5, 7] → 5 & 6 & 7 = 4.

Thuật toán giải quyết

Quan sát: phép AND bitwise trên một khoảng sẽ chỉ giữ lại các bit prefix chung của m và n. Các bit khác nhau sẽ bị loại bỏ do sự dao động trong khoảng.

1. Khởi tạo i = 0.
2. Trong khi m != n:
   • Dịch phải cả hai: m >>= 1, n >>= 1.
   • Tăng i++.
3. Kết quả = m << i (dịch trái ngược lại số lần đã dịch phải).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            i++;
        }
        return m << i;
    }
};

int main() {
    Solution ob;
    cout << ob.rangeBitwiseAnd(5, 7);
}

Đầu vào

5 7

Đầu ra

4