leetcode201. Bitwise AND of Numbers Range

wapeyang 发布于2019-08-15 13:59 / 735人阅读

摘要：题目要求给一个闭区间，对该闭区间的所有数字进行与运算。在计算机底层所有的十进制数都是以二进制数进行存储的。因此，当我们同时左移时，一定会有一个时刻，使得与相等。这意味着，从该位起前面的所有位数值均相等。

题目要求

Given a range [m, n] where 0 <= m <= n <= 2147483647,
return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

给一个闭区间[m,n]，对该闭区间的所有数字进行与（and）运算。
与预算是指 1 and 1 = 0, 1 and 0 = 0, 0 and 1 = 0, 0 and 0 = 0。
这里都是以二进制为基础进行与运算。在计算机底层所有的十进制数都是以二进制数进行存储的。写这道题目之前需要先去了解十进制转二进制以及未操作符>>,>>>和<<。

思路和代码

其实可以想到，如果一个区间含有偶数，那么这个区间中一定有一个数，其二进制的末位为0，那么就意味着这些数在该位上的与运算结果一定为0。
计算完末位后，我们来计算倒数第二位的与运算。这就相当于将[m, n]区间转化为[m/2,n/2]区间，在该区间上我们再来判断是否包含偶数。
在一番尝试之后，我们会发现，如果一个区间[m,n]，当m不等于n时，其中一定包含偶数，即该末位的和运算一定为0。
因此，当我们同时左移m,n时，一定会有一个时刻，使得m与n相等。这意味着，从该位起前面的所有位数值均相等。它们进行任何与运算一定等于它们本身。我们可以直接将这些位的内容添加到结果集开头。

代码如下：

    public int rangeBitwiseAnd(int m, int n) {
        if(m==n) return m;
        int count = 0;
        while(m>>= 1 ;
            n >>>= 1;
        }
        return m<<=count;
    }

优化后代码如下：

    public int rangeBitwiseAnd2(int m, int n) {
        if(m==n) return m;
        int count = 1;
        while(m>>= 1 ;
            n >>>= 1;
        }
        return m * count;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68437.html

[LeetCode] 628. Maximum Product of Three Numbers

Problem Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1:Input: [1,2,3]Output: 6Example 2:Input: [1,2,3,4]Output: 24Note:The length of the ...

jindong 2019-08-16 13:39 评论0 收藏0
Python基础练习100题 ( 71~ 80）

摘要：刷题继续昨天和大家分享了题，今天继续来刷题解法一解法二解法一解法一解法二解法一解法一解法二解法一解法一解法二解法一解法二解法一解法二解法三解法一解法二源代码下载这十道题的代码在我的上，如果大家想看一下每道题的输出结果，可以点击以下链接下刷题继续昨天和大家分享了61-70题，今天继续来刷71~80题 Question 71: Please write a program to out...

Jeff 2019-07-31 10:31 评论0 收藏0
[LeetCode] 724. Find Pivot Index

Problem Given an array of integers nums, write a method that returns the pivot index of this array. We define the pivot index as the index where the sum of the numbers to the left of the index is equa...

vibiu 2019-08-16 13:49 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

张春雷 2019-08-16 18:29 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

Me_Kun 2019-07-31 11:26 评论0 收藏0