Bitwise AND of Numbers range

Problem:
Given a range [m,n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5,7], you should return 4.

Solution:
The key to solving this problem is bitwise AND consecutive number. You can use the following the example to walk through the code.

———————————————————————————
  8    4    3    2
———————————————————————————
 5 | 0 1 0 1
 6 | 0 1 1 0
 7 | 0 1 1 1
———————————————————————————

package com.algorithm.bitwise;

public class BitwiseAND {

    public static void main(String[] args) {
        System.out.println(rangeBitwiseAnd(5, 7));
    }

    public static int rangeBitwiseAnd(int m, int n) {
        while (n > m) {
            n = n & n - 1;
        }
        return m & n;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s