leetcode 201. Bitwise AND of Numbers Range | 201. 数字范围按位与（Java）

偏执的太偏执、 2022-10-05 08:57 279阅读 0赞

题目

https://leetcode.com/problems/bitwise-and-of-numbers-range/
在这里插入图片描述

题解

（这题暴力法超时了，最后还是参考了答案的思路）

最直观的解决方案就是：迭代范围内的每个数字，依次执行按位与运算，得到结果，但此方法在 [m,n] 范围较大的测试用例中超时。

正解如下：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  1. class Solution { 
  2.     public int rangeBitwiseAnd(int left, int right) { 
  3.         int shift = 0; // 同时右移 shift 位后，两数第一次相等
  4.         while (left >> shift != right >> shift) { 
  5.             if (left >> shift == 0 && right >> shift != 0) return 0; // 如果最高位不能对齐的话，则必无公共前缀
  6.             shift++;
  7.         }
  8.         return left >> shift << shift; // 见图1，目标是将虚线后面的位置0
  9.     }
  10. }

图1：
在这里插入图片描述

方法二：Brian Kernighan 算法

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，279人围观）

还没有评论，来说两句吧...

相关阅读