C#版 - Leetcode 201. 数字范围按位与(bitwise AND) - 题解

C#版 - Leetcode 201. 数字范围按位与(bitwise AND) - 题解

在线提交: https://leetcode.com/problems/bitwise-and-of-numbers-range/

题目描述

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1:

输入: [5,7]
输出: 4

示例 2:

输入: [0,1]
输出: 0

• 题目难度：Medium

• 通过次数：139

• 提交次数：449

• 贡献者：amrsaqr

• 相关话题 位运算

思路:
两个数按位与的结果为相同的部分保持不变，不相同的部分会被置为零，多个数的按位与的结果与之类似。
根据按位与的性质可知，如果数字m != n，则在m, n范围内的数的最后一位必然同时存在1和0，因此最后一位的按位与&的结果必为0。而如果m=0，所有数按位与的结果必然为0。

举例而言:

例1. [9, 11]，其范围内的数字的二进制表示依次为：

1 001

1 010

1 011

这些数按位相与后的结果为1 000。

例2.[20, 23]，其范围内的数字的二进制表示依次为：

101 00

…

101 11

这些数按位相与后的结果为101 00。

例3.[4, 23]，其范围内的数字的二进制表示依次为：

00100

…

10111

这些数按位相与后的结果为00000，因为高位没有共同字符串。

因此，m,n范围内的数的按位与的结果就是各个数的各位对齐后高位共同数字串末尾全补0的值。

已AC代码:

public class Solution
{
    public int RangeBitwiseAnd(int m, int n)
    {
        // 题中规定数据范围: m, n中较大值<=31s = 2147483647
        int shiftCount = 0;
        int common = 0;
        GetCommonDigits(m, n, ref common, ref shiftCount);
        var res = common << shiftCount;  // 末位补0

        return res;
    }

    public void GetCommonDigits(int a, int b, ref int common, ref int shiftCount)
    {
        shiftCount = 0;
        while (a != b)
        {
            a = a >> 1;
            b = b >> 1;
            shiftCount++;
        }
        common = a;
    }
}

当然也可使用递归解法：

public static int RangeBitwiseAnd(int m, int n)
{
    if (m < n)
        return (RangeBitwiseAnd(m >> 1, n >> 1) << 1);
    else return m;
}

Rank:

You are here! Your runtime beats 96.88% of csharp submissions.

Refrence:
https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/56789/C-Solution-with-bit-shifting-(Beats-90)