Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Sample Example
4.
Brute Force Approach
4.1.
Algorithm
4.2.
Implementation in C++
5.
Bit Manipulation (Considering Rightmost Set Bit)
5.1.
Algorithm
5.2.
Dry Run
5.3.
Implementation in C++
6.
Bit Manipulation (Considering Leftmost Set Bit)
6.1.
Algorithm
6.2.
Dry Run
6.3.
Implementation in C++
7.
Frequently Asked Questions
7.1.
What is C++?
7.2.
List different arithmetic operators in C++.
7.3.
What is STL in C++?
7.4.
What does bitwise AND do?
7.5.
What is the garbage value in C and C++?
8.
Conclusion
Last Updated: Mar 27, 2024

Bitwise AND of Numbers Range

Author Ishita Chawla
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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 use binary operators to switch on/off individual data bits and make our task more manageable. To conduct operations and alter data bits conveniently.

OG image

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

Problem Statement

You are given two integers, L 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, including L and R.

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Sample Example

1. Consider this case where L=5 and R=7; here, the result of AND of the numbers in the range [5,7] would be 4.

image for sample example 1

2. Now, let us consider a case where L=11 and R=14. Here the AND value of the numbers in this range would be 8.

image for sample example-2

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 in C++

// C++ program to find the bitwise AND of number's range.
#include <bits/stdc++.h>
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=8, y=12;

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

    return 0;
}

 

Output

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

Time Complexity

The time complexity is O(N), where N is the count of numbers in the given range (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).

Bit Manipulation (Considering Rightmost Set Bit)

Though the brute force approach might seem easy, this approach will not give A.C. (Accepted) due to the high constraints. So we will be using the optimal approach to solve this problem. In this approach, we will use the concept of the Rightmost Set Bit in the Bit Manipulation.

Algorithm

1. For every pair of continuous numbers, the last bit differs 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.

2. So we check if the bits of L is equal to that of R.

3.  If they are not equal, we right-shift our numbers, removing the rightmost bit from them.

4. We keep a count of the number of shifts, say COUNT.

5. If the numbers are equal, we multiply 2COUNT with the remaining number. 

6. This gives us the required answer.

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

Dry Run

Let us consider the range as [9,15] here L=9 and R=15,

Step-1

dry run image for step-1

Step-2

Since L!=R so, we right shift both the numbers by 1 (i.e, we remove the last bit) and the COUNT will be increased.

dry run image for step-2

Step-3 

Again, L!=R (4!=7), so again, we right-shift the numbers by 1, and the COUNT is increased by 1.

dry run image for step-3

Step-4 

Repeat the above step since L!=R, 

dry run image for step-4

After performing the above step, L becomes equal to R. So now, COUNT becomes 3.

Now we will multiply the remaining number (i.e. 1) with 2COUNT, so now our answer becomes 2which is 8.

Implementation in C++

// C++ program to find the bitwise AND of the 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=4, y=7;

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

    return 0;
}

 

Output

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

Time Complexity

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

Space Complexity

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

Bit Manipulation (Considering Leftmost Set Bit)

This approach is an alternative to the above approach, here we will be using the concept of Leftmost Set Bit of Bit manipulation to solve this question.

Algorithm

1. We will first find the Leftmost set bit of both the numbers, L and R.

2. If the position of the Leftmost set bit differs, the result is 0 and we will return.

3. Else if the positions are the same, say LSB1, 2LSB1 is added to the answer, and it is subtracted from both L and R.

4. The above step will be repeated for the new values of L and R until the position of the Leftmost set bit differs. 

Let us understand this with the help of an example 

Dry Run

Let us consider the range as [5,7] here L=5 and R=7, then initially,

Step-1 

dry run image for step-1

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)

The position of MSB is the same, so ANS = ANS + 4  = 0 + 4 = 4

L = 5 - 22 = 5 - 4 = 1

R = 7 - 22 = 7 - 4 = 3

 

Step-2

Now the new L and R would be [1,3], again we will repeat the same process.

step-2 image

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

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

The position of MSB differs, so the answer, ANS = ANS + 0 = 4 + 0 = 4

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

Implementation in C++

// 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=8, y=16;

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

    return 0;
}

 

Output

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

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).

Read about Bitwise Operators in C here.

Also Read - Strong number in c

Frequently Asked Questions

What is C++?

C++ is a general-purpose programming language created by Bjarne Stroustrup at Bell Labs in the early 1980s. C++ is quite similar to C, and it is so compatible with C that it can run 99 percent of C programs without changing any source code.

List different arithmetic operators in C++.

The different arithmetic operators are +,-,/,%,*.

What is STL in C++?

STL is an acronym for Standard Template Library that provide generic classes and functions in C++ that can be used to implement data structures.

What does bitwise AND do?

It takes two bits and gives output as 1 when both the bits are set to 1 else if either or both the bits are set to 0 then it gives output as 0.

What is the garbage value in C and C++?

When we allocate a variable, some memory for that variable is reserved. If a variable is declared but not allocated any value, it has a garbage value, which means that the computer's storage keeps any random data.

Conclusion

In this blog, we have discussed the problem of Bitwise AND of numbers in a range using 3 different approaches, we have also discussed each approach's time and space complexity.

To learn more, head over right now to Coding Ninjas Studio to practice problems on topics like Bit Manipulation and visit the library 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.

Live masterclass