201. Bitwise AND of Numbers Range

Description

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

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: [5, 7]

Output: 4

Example 2

Input: [0, 1]

Output: 0

Solutions

Solution 1

/**
 * Time complexity : O(1). Although there is a loop in the algorithm, 
 *    the number of iterations is bounded by the number of bits that an 
 *    integer has, which is fixed.
 * Space complexity : O(1). The consumption of the memory for our algorithm 
 *    is constant, regardless the input.
 */

class Solution {
  public int rangeBitwiseAnd(int m, int n) {
    int shift = 0;
    // find the common 1-bits
    while (m < n) {
      m >>= 1;
      n >>= 1;
      ++shift;
    }
    return m << shift;
  }
}

Solution 2

/**
 * Time complexity : O(1). Although there is a loop in the algorithm, 
 *    the number of iterations is bounded by the number of bits that an 
 *    integer has, which is fixed.
 * Space complexity : O(1). The consumption of the memory for our algorithm 
 *    is constant, regardless the input.
 */
 
 class Solution {
  public int rangeBitwiseAnd(int m, int n) {
    while (m < n) {
      // turn off rightmost 1-bit
      n = n & (n - 1);
    }
    return m & n;
  }
}

Follow up