Question

• https://leetcode.com/problems/bitwise-and-of-numbers-range/

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Approach

• Difference based approach :

  class Solution {
  public:
      int rangeBitwiseAnd(int left, int right) {
          int diff = right - left;
          int curr = 1;
          int ans = 0;
          int c = 0;
          while(left!=0) {
              if (left%2 == 1 && curr > diff) {
                  int temp = 1<<c;
                  ans = ans + temp;
              } 
              cout<<ans<<endl;
              curr = 2*curr;
              left = left/2;
              c++;
          }
          return ans;
      }
  };
  

  Problem here : case : [3,4]

• https://www.geeksforgeeks.org/bitwise-and-or-of-a-range/

  1) Find position of Most Significant Bit (MSB) in both numbers. 2) If positions of MSB are different, then result is 0. 3) If positions are same. Let positions be msb_p. ……a) We add 2msb_p to result. ……b) We subtract 2msb_p from x and y, ……c) Repeat steps 1, 2 and 3 for new values of x and y.

Solution

class Solution {
public:
    int msbPos(int n)
    {
        int msb_p = -1;
        while (n)
        {
            n = n>>1;
            msb_p++;
        }
        return msb_p;
    }
    
    int rangeBitwiseAnd(int left, int right) {
        int res = 0;
        int x = left;
        int y = right;
        
        while (x && y)
        {
            // Find positions of MSB in x and y
            int msb_p1 = msbPos(x);
            int msb_p2 = msbPos(y);
  
            // If positions are not same, return
            if (msb_p1 != msb_p2)
                break;
  
            // Add 2^msb_p1 to result
            int msb_val =  (1 << msb_p1);
            res = res + msb_val;
  
            // subtract 2^msb_p1 from x and y.
            x = x - msb_val;
            y = y - msb_val;
        }
  
        return res;
    }
};