LeetCode 201. Bitwise AND of Numbers Range の解き方メモ

LeetCode 201. Bitwise AND of Numbers Range の解き方メモです。問題は「LeftからRightの範囲にある整数すべてをAND演算した結果を求めなさい」とたいへんシンプルなのですが、結構てこずっちゃったので、考えた過程を残しておきたいと思います。

LeftからRightの範囲にある整数すべてをAND演算した結果をAとします。Aの右からNビット目が1である条件は、LeftからRightの範囲にある整数すべてについて、右からNビット目が1であることです (N>=1)。この条件を満たすのはどのような場合でしょうか? これを見極めるため、0から15までの2進数を観察します。

10進数	2進数	1ビット目	2ビット目	3ビット目	4ビット目
0	0000	0	0	0	0
1	0001	1	0	0	0
2	0010	0	1	0	0
3	0011	1	1	0	0
4	0100	0	0	1	0
5	0101	1	0	1	0
6	0110	0	1	1	0
7	0111	1	1	1	0
8	1000	0	0	0	1
9	1001	1	0	0	1
10	1010	0	1	0	1
11	1011	1	1	0	1
12	1100	0	0	1	1
13	1101	1	0	1	1
14	1110	0	1	1	1
15	1111	1	1	1	1

この表をながめていると、ある整数Xの右からNビット目が1である条件は「Xを2^nでわったあまりが2^(n-1)以上であること」だとわかります。

(例: N=3の場合) 2^3=8でわったあまりが2^(3-1)=4以上の整数について、右から3ビット目が1。上表を見ると、8でわったあまりが4になる4と12、あまりが5になる5,13、あまりが6になる6と14、あまりが7になる7と15について、右から3ビット目が1になっていることがわかる。

したがって、Aの右からNビット目が1になるのは以下の条件を満たす場合であるとわかります。

1. LeftとRightを2^Nでわったときの商が同じ
2. LeftとRightを2^Nでわったときのあまりがどちらも2^(n-1)以上

(1.の条件が必要な理由 … LeftとRightを2^Nでわったときの商が違う場合、2^Nでわったときのあまりが0になる整数がLeftとRightの範囲に出現する)

あとは実装するだけ。すべてのNについて上記の条件を満たすかどうかチェックすればよいです。

impl Solution {
    pub fn range_bitwise_and(left: i32, right: i32) -> i32 {
        let left = left as u128;
        let right = right as u128;

        let mut ret = 0u128;
        for n in 1..=32 {
            let p = 2u128.pow(n-1);
            let q = 2u128.pow(n);
            if left/q==right/q && p<=left%q && p<=left%q {
                ret |= 1<<(n-1);
            }
        }

        ret as i32
    }
}