Description

给定两个整数\(lo\)和\(hi\)，表示一个区间\([lo, hi]\)，求该区间内AND操作后的结果

Constraints

\(0 \le lo \le hi \le 2^{31} - 1\)

Solution

拆成32位看，只要高位不一致，从\(hi\)到\(lo\)是要经历0-bit的

Code

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int ans = 0;
        auto highFunc = [](int v) {
            for(int b = 31; ~b; b--) {
                if(v >> b & 1) return b;
            }
            return -1;
        };
        while(left && right) {
            int posL = highFunc(left);
            int posR = highFunc(right);
            if(posL == -1 || posR == -1) break;
            else if(posL == posR) {
                ans |= 1 << posL;
                left &= ~(1<<posL);
                right &= ~(1<<posL);
            } else {
                right &= ~(1<<posR);
                break;
            }
        }
        return ans;
    }
};

Link

LeetCode-201 Bitwise AND of Numbers Range