Bitwise AND of Numbers Range

Problem: Given a range [low, high] where low and high are positive integers and low < = high, return the bitwise AND of all numbers in this range, inclusive.

Example:

Input: [26,30]
Output: 24

Approach: One trivial way is we can use a loop from low to high and do the AND but we want to do better. Lets have a close look, say for number 26 to 30 -

26 - 11010

27 - 11011

28 - 11100

29 - 11101

30 - 11110

As per AND operator property, AND of numbers will produce a set bit(1) at position i only if all the numbers have set bit at position i otherwise it will be 0. As these numbers are in increasing order and the difference between numbers is 1, it can be easily observed that the numbers with in this range except low and high are not important and if the AND of these numbers is not zero then some bits till position j from left in low and high are going to be same that means if we keep right shifting low and high, at some point low and high are going to be same. Here in our case we will keep right shifting the 26 and 30 by 1 till they become same which is 00011(3) after 3 right shifts so what we can say that AND of range (26,30) is 00011 << 3 = 11000 (24).

Implementation in C#:

        public int RangeBitwiseAnd(int low, int high)

        {

            int count = 0;

            while (low != high)

            {

                low >>= 1;

                high >>= 1;

                ++count;

            }

            return low << count;

        }  

Complexity: O(n) where n is the number of bits.