Bitwise AND of Numbers Range ใน C++: หา AND ของช่วงตัวเลข

โจทย์

กำหนดช่วง [m, n] โดยที่ 0 ≤ m ≤ n ≤ 2,147,483,647 หาค่า Bitwise AND ของทุกตัวเลขในช่วงนี้รวมปลายทาง

ตัวอย่าง: [5, 7] → 5 & 6 & 7 = 4

แนวคิด: หาบิตร่วมทั่วไป (Common Prefix)

Bitwise AND ของช่วงจะเก็บเฉพาะบิตที่เหมือนกันทั้งหมดตั้งแต่ MSB จนกว่าจะเจอบิตที่ต่างกัน บิตที่ต่างกันและบิตต่ำกว่าจะกลายเป็น 0

วิธีง่าย: เลื่อน m และ n ขวาไปเรื่อยๆ จนเท่ากัน นับจำนวนครั้งที่เลื่อน แล้วเลื่อนซ้ายกลับไป

ขั้นตอน

1. i = 0
2. while m != n: m >>= 1, n >>= 1, i++
3. คืน m << i

ตัวอย่างโค้ด C++

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

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

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

อินพุต / เอาต์พุต

Input: 5 7

Output: 4

ความซับซ้อน

• Time: O(log max(m,n)) ≤ O(31)
• Space: O(1)

เหตุผลที่ทำงานได้

เมื่อเลื่อนขวา จำนวนครั้งที่เลื่อน = จำนวนบิตขวาสุดที่จะกลายเป็น 0 บิตที่เหลือ (common prefix) คือบิตที่ทุกตัวเลขในช่วงมีเหมือนกัน