Bitwise AND of Numbers Range

Ishita Chawla
Last Updated: May 13, 2022

Introduction

Bitwise Algorithms are used to carry out operations at the bit level or manipulate bits in various ways. Bitwise operations are substantially faster and are sometimes utilized to increase a program's efficiency.

It's occasionally vital to think about data at the bit level, and we'll have to work with each data bit individually. We may also need to employ binary operators to switch on/off individual data bits and make our task more manageable. To conveniently conduct operations and alter data bits, there are six major binary operators.

In this blog, we will be discussing one such problem, Bitwise AND of Numbers Range, which can be easily solved by using the basic concepts of bit manipulation.

Problem Statement:

You are given two integers, and R, representing the range of numbers, from left to right. You have to find the bitwise AND of all the numbers in this range whereand R should also be included.

So basically we need to find the value of L & (L + 1) & (L + 2) & ….& (R - 2) & (R - 1) & R

Example

  1. L = 5 

    R = 7

    ANS = 5 & 6 & 7

            = (5 & 6) & 7

  = 4 & 7

            = 4

 

2. L = 11 

    R = 14

    ANS = 11 & 12 & 13 & 14

  = (11 & 12) & 13 & 14

  = (8 & 13) & 14

  = 8 & 14

            = 8

 

3. L = 2

    R = 4

    ANS = 2 & 3 & 4

             = (2 & 3) & 4

             = 0 & 4

             = 0

Brute Force Approach

Algorithm

The naive approach would be to traverse all the numbers from left to right, compute the AND, and subsequently store it as we proceed. 

Implementation:

Program:

// C++ program to find the bitwise AND of number's range.
#include <iostream>
using namespace std;

// Function to find the bitwise AND of numbers between left and right.
int findANDofRange(int left, int right)
{
    int answer = left;
    for (int i = left + 1; i <= right; i++)
    {
        answer = answer & i;
    }
    return answer;
}
int main()
{
    long long int x, y;

    // Taking user input.
    cout << "Enter the 2 numbers specifying the range: ";
    cin >> x >> y;

    // Calling the function to print the answer.
    cout << "The bitwise and of the numbers in this range is " << findANDofRange(x, y);

    return 0;
}

Input:

Enter the 2 numbers specifying the range:
11 14

Output:

The bitwise AND of the numbers in this range is 8.

Time Complexity

The time complexity is O(K) where K is the number of numbers lying in the given range.

We are going through all the numbers from L to R and finding the bitwise AND as we proceed. So the time complexity is given by O(R - L + 1) or simply O(K) where K = R - L + 1.

Space Complexity

The space complexity is O(1).

We are not using any extra space so the space complexity is constant, i.e., O(1).

Though this approach might seem easy, this is not acceptable most of the time due to the high constraints given. So we need to find other ways that can be accepted as the solution to the problem.

Bit Manipulation (Considering LSB)

Algorithm

  • For every pair of continuous numbers, the last bit is different from the previous one(one is always 0 and the other is always 1 because continuous numbers form an even-odd pair or vice-versa). Hence, until both numbers are not equal, the resultant bitwise AND of the rightmost bit is always zero.
  • So we check if the bits of L are equal to that of R or not.
  • If they are not equal, we right shift our numbers, which basically removes the rightmost bit from the numbers.
  • We keep a count of the number of shifts,say COUNT.
  • If the numbers are equal, we add 2COUNT to the remaining number. 
  • This gives us the required answer.


Let’s try to understand this with the help of an example:

  • L = 11 = 1011

    R = 14 = 1110 

    Let the number of right shifts be equal to ‘COUNT’.

                L != R  

     So,     L = 101

               R = 111

              COUNT = 1

 

               L != R  

    So,     L =10

               R = 11

              COUNT = 2

 

               L != R  

    So,     L =1

               R = 1

              COUNT = 3

 

    Now, L = R 

   So answer = R * 2COUNT

                         = 1 * 23

  = 8

So, the bitwise AND of Numbers Range in the range [11, 14] is 8.

Implementation:

Program:

// C++ program to find the bitwise AND of number's range.
#include <iostream>
using namespace std;
 
// Function to find the bitwise AND of numbers between left and right.
int findANDofRange(int left, int right)
{
    int count = 0;
 
    // The loop runs until 'LEFT' and 'RIGHT' are unequal.
    while (left != right)
    {
        // At every step, the numbers are shifted right, which means the rightmost bit is removed.
        left >>= 1;
        right >>= 1;
        count++;
    }
 
    // The remaining bits are multiplied with the count of right shifts and this is the answer.
    return right <<= count;
}
int main()
{
    long long int x, y;
 
    // Taking user input.
    cout << "Enter the 2 numbers specifying the range: ";
    cin >> x >> y;
 
    // Calling the function to print the answer.
    cout << "The bitwise AND of the numbers in this range is " << findANDofRange(x, y);
 
    return 0;
}

Input:

Enter the 2 numbers specifying the range:
5 7

Output:

The bitwise AND of the numbers in this range is 4.

Time Complexity

The time complexity is given by O(log(L)), where L is the minimum number.

Since there are log(L) bits in a number and we are going through all the bits one by one, the time complexity of this approach is O(log(L)).

Space Complexity

The space complexity is O(1).

We are not using any extra space so the space complexity is constant, i.e., O(1).

Bit Manipulation (Considering MSB)

Algorithm

  • Find the MSB of both the numbers, L and R.
  • If the position of MSB differs, the result is 0.
  • If the positions are the same, say MSB12MSB1 is added to the final answer, and it is subtracted from both L and R.
  • The above step is repeated for the new values of L and R until the position of MSB differs. 

Let us understand this with the help of an example:

  • L = 3

R = 7

Let the answer be ‘ANS’. 

Position of MSB in L = 1 ( 3 = 0 1 1)

Position of MSB in R = 2 (7 = 1 1 1)

Position of MSB differs, so answer, ANS = 0

 

  • L = 5

R = 7

Let the answer be ‘ANS’. 

Position of MSB in L = 2 ( 5 = 1 0 1)

Position of MSB in R = 2 (7 = 1 1 1)

Position of MSB is same, so ANS = ANS + 2

              = ANS + 4 

    = 0 + 4 

    = 4
 

L = 5 - 2= 5 - 4 = 1

R = 7 - 22 = 7 - 4 = 3

Position of MSB in L = 0 ( 1 = 0 0 1)

Position of MSB in R = 1 (3 = 0 1 1)

Position of MSB differs, so answer, ANS = ANS + 0

                                                                  = 4 + 0

                                                                  = 4

So, the bitwise AND of Numbers Range in the range [5, 7] is 4.

Implementation:

Program:

// C++ program to find the bitwise AND of numbers range using bit manipulation.
#include <iostream>
using namespace std;
 
// Function to find the position of the MSB in a number.
int positionOfMSB(int n)
{
    int posOfMSB = -1;
    while (n)
    {
        n = n >> 1;
        posOfMSB++;
    }
    return posOfMSB;
}
 
// Function to find the bitwise AND of numbers between left and right.
int findANDofRange(int left, int right)
{
    int ans = 0;
 
    while (left && right)
    {
        // Finding the position of MSB on the 'LEFT' and 'RIGHT'.
        int msb1 = positionOfMSB(left);
        int msb2 = positionOfMSB(right);
 
        // If the positions are not the same, return.
        if (msb1 != msb2)
            break;
 
        // 2 ^ msb1 is added to the result and subtracted from both 'LEFT' and 'RIGHT'.
        int msbVal = (1 << msb1);
        ans = ans + msbVal;
 
        left = left - msbVal;
        right = right - msbVal;
    }
    return ans;
}
 
int main()
{
    long long int x, y;
 
    // Taking user input.
    cout << "Enter the 2 numbers specifying the range: ";
    cin >> x >> y;
 
    // Calling the function to print the answer.
    cout << "The bitwise and of the numbers in this range is " << findANDofRange(x, y);
 
    return 0;
}

Input:

Enter the 2 numbers specifying the range:
5 7

Output:

The bitwise AND of the numbers in this range is 4.

Time Complexity

The time complexity is given by O(log(L)), where ‘L’ is the minimum number.
Since there are log(L) bits in a number and we are going through all the bits one by one, the time complexity of this approach is O(log(L)).

Space Complexity

The space complexity is O(1).

We are not using any extra space so the space complexity is constant, i.e., O(1).

Key Takeaways

So, this blog discussed the problem of Bitwise AND of numbers range using 3 different approaches, discussing each approach's time and space complexity.

To learn more, head over right now to CodeStudio to practice problems on topics like Brute Force and Bit Manipulation and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think