{"id":9038,"date":"2021-12-05T18:38:22","date_gmt":"2021-12-06T02:38:22","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9038"},"modified":"2021-12-05T18:39:28","modified_gmt":"2021-12-06T02:39:28","slug":"leetcode-201-bitwise-and-of-numbers-range","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/bit\/leetcode-201-bitwise-and-of-numbers-range\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 201. Bitwise AND of Numbers Range"},"content":{"rendered":"\n<p>Given two integers&nbsp;<code>left<\/code>&nbsp;and&nbsp;<code>right<\/code>&nbsp;that represent the range&nbsp;<code>[left, right]<\/code>, return&nbsp;<em>the bitwise AND of all numbers in this range, inclusive<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> left = 5, right = 7\n<strong>Output:<\/strong> 4\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> left = 0, right = 0\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> left = 1, right = 2147483647\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>0 &lt;= left &lt;= right &lt;= 2<sup>31<\/sup>&nbsp;- 1<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Bit operation<\/strong><\/h2>\n\n\n\n<p>Bitwise AND all the numbers between left and right will clear out all the <strong>low bits<\/strong>. Basically this question is asking to find the common prefix of left and right in the binary format.<\/p>\n\n\n\n<p><br>5 = 0b0101<br>7 = 0b0111<br>the common prefix is 0b0100 which is 4.<\/p>\n\n\n\n<p>Time complexity: O(logn)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\/\/ Author: Huahua\nclass Solution {\npublic:\n  int rangeBitwiseAnd(int left, int right) {\n    while (right > left)\n      right &= (right - 1); \/\/ clears the lowest set bit.\n    return right;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two integers&nbsp;left&nbsp;and&nbsp;right&nbsp;that represent the range&nbsp;[left, right], return&nbsp;the bitwise AND of all numbers in this range, inclusive. Example 1: Input: left = 5, right =&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126],"tags":[16,31,177,97],"class_list":["post-9038","post","type-post","status-publish","format-standard","hentry","category-bit","tag-bit","tag-math","tag-medium","tag-prefix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9038","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9038"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9038\/revisions"}],"predecessor-version":[{"id":9042,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9038\/revisions\/9042"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9038"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9038"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9038"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}