A Math solution.

  • 8
    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

    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.