LeetCode-201. 数字范围按位与-Java-medium

题目链接

法一

    /**
     * 法一（位运算）
     * （1）可以将问题重新表述为：给定两个整数，找到对应的二进制表示的公共前缀
     * （2）例子，比如 left = 5， right = 7
     *     5: 0 1 0 1
     *     6: 0 1 1 0
     *     7: 0 1 1 1
     *     5 和 7 的公共前缀是 0 1，offset = 2，故该范围内所有数字的按位与的结果是 0 1 0 0
     *
     *
     * @param left
     * @param right
     * @return
     */
    public int rangeBitwiseAnd(int left, int right) {
        int offset = 0;
        while (left != right) { // 找到left和right的公共前缀
            left >>= 1; // 每次都向右移动一位，再判断剩下的数字是否相等
            right >>= 1;
            offset++;   // offset记录不相等数字的个数
        }
        return left << offset; // 归位公共前缀（公共前缀后补offset个0）
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

本地测试

        /**
         * 201. 数字范围按位与
         */
        lay.showTitle(201);
        Solution201 sol201 = new Solution201();
        int left201 = 5;
        int right201 = 7;
        System.out.println(left201 + " " + right201);
        System.out.println(sol201.rangeBitwiseAnd(left201, right201));
1
2
3
4
5
6
7
8
9