A Math solution.


  • 8
    H
    public class Solution {
        public int rangeBitwiseAnd(int m, int n) {
            if (m == n){
                return m;
            }
            //The highest bit of 1 in diff is the highest changed bit.
            int diff = m ^ n;
            //Index is the index of the highest changed bit. Starting at 1.
            int index = (int)(Math.log(diff) / Math.log(2)) + 1;
            //Eliminate the changed part.
            m = m >> index;
            return m << index;
        }
    }
    

    I think this is fast since it doesn't involve loops.


  • 0
    S

    I like this explanation


  • 5

    Nice one. In Python we have a method to get the bit length of integers so it becomes this:

    def rangeBitwiseAnd(self, m, n):
        b = (m ^ n).bit_length()
        return m >> b << b

Log in to reply
 

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