专栏首页大白技术控的技术自留地C#版 - Leetcode 201. 数字范围按位与(bitwise AND) - 题解

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)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++版 - 剑指Offer 面试题45:圆圈中最后剩下的数字(约瑟夫环问题,ZOJ 1088:System Overload类似)题解

    提交网址: http://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&...

    Enjoy233
  • 快速排序 数组+递归实现

    1. 用一个自定义的分割方法split()选取用来作分割的元素(也称为partition主元),最简单的分割方法是选定待排范围的第一个数为partition主元...

    Enjoy233
  • C#版(击败96.64%的提交) - Leetcode 728. 自除数 - 题解

    Leetcode 728 - Self Dividing Numbers 在线提交: https://leetcode-cn.com/problems/se...

    Enjoy233
  • 深入理解计算机系统(第三版)/ CSAPP 杂谈,第11章:网络编程

    int socket(int domain, int type, int protocol) // 创建套接字描述符,成功返回非负数描述符,失败为-1 int ...

    sickworm
  • 【码云周刊第 11 期】追踪代码大仓库? Git 的拿手好戏!

    每周为您推送最有价值的开源技术内参! 一周热门资讯回顾 ActFramework 1.0 正式发布, Java MVC 框架 TIOBE 3 月编程语言排行榜...

    码云Gitee
  • iOS UITableView 让cell分割线(Separator)从左边0的位置开始

    傅_hc
  • Android Studio集成Bug管理系统

    用户1907613
  • linux下Android7.0多用户编译问题

    0.0 WHY linux下多用户使用open-jdk8编译时会有jack-server的问题。首先要明白为什么会出现这个问题,只有明白了原因,才能对症下药。注...

    fanfan
  • CMD远程连接服务器上的MySQL

    2.输入mysql -h要远程的IP地址 -u设置的MySQL用户名 -p登录用户密码

    ydymz
  • OpenGL ES 3.0 | 围绕HelloTriangle实战案例 展开 渲染流程分析

    凌川江雪

扫码关注云+社区

领取腾讯云代金券