A Java solution different than finding the left most common bit


  • 0
    Z

    My solution is to scan n from the first bit to last bit. A certain bit can only remain 1 if and only if you can meet the following situation:

    for xx1xxxx, if xx0xxxx exists in the range [m, n], that 1 will always set to 0 at the Range AND. Only if xx01111 < m, we can make sure that the 1 can be remained.

    Take a short example, [5, 7] which represented as 101, 110, 111. If we scan 111:

    1. for the 1st one, we check if 011 is in range [5, 7], that is check(4 < 5). It is not in range [5, 7], so we remain the 1st one.
    2. for the 2nd one, we check if 101 is in range [5, 7], that is check(5 < 5). It is in range [5, 7], so the 2nd one will disappear at the process of AND. Discard that one.
    3. for the 3rd one, we check if 110 is in range [5, 7], that is check(6 < 6). It is in range [5, 7], discard that one.

    public class Solution {
      public int rangeBitwiseAnd(int m, int n) {
          if(m == 0 || m == n) return m;
    
          int res = 0;
          for(int i = 31; i >= 0; i--) {
              int x = 1 << i; 
              if((x & n) > 0 && ((n & ~x) | (x - 1)) < m)
                  res |= x;
          }
          return res;
      }
    }
    

    (n & ~x) is to set i th position 0, like dealing with 2nd one above, you have to construct 101 from 111. (n & ~x) | (x - 1) is to mask the 0xxx to 0111.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.