# Bitwise AND of Numbers Range

__Introduction__

__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:__

__Problem Statement:__You are given two integers, * L *and

*representing the range of numbers, from left to right. You have to find the bitwise*

**R,***of all the numbers in this range where*

**AND***and*

**L***should also be included.*

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

__Example__

__Example__

**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__

__Brute Force Approach__

__Algorithm__

__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:**

**Implementation:**

__Program:__

__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:__

__Input:__```
Enter the 2 numbers specifying the range:
11 14
```

__Output:__

__Output:__`The bitwise AND of the numbers in this range is 8.`

**Time Complexity**

**Time Complexity**

The time complexity is * O(K) *where

*is the number of numbers lying in the given range.*

**K**We are going through all the numbers from * L* to

*and finding the bitwise AND as we proceed. So the time complexity is given by*

**R***or simply*

**O(R - L + 1)****O(K)**where

**K = R - L + 1.****Space Complexity**

**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)__

__Bit Manipulation (Considering LSB)__

__Algorithm__

__Algorithm__- For every pair of continuous numbers, the last bit is different from the previous one(one is always
and the other is always**0**because continuous numbers form an even-odd pair or vice-versa). Hence, until both numbers are not equal, the resultant bitwise**1****AND**of the rightmost bit is always zero. - So we check if the bits of
are equal to that of**L**or not.**R** - 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
to the remaining number.**2**^{COUNT} - 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 * 2 ^{COUNT}**

^{ } = 1 * 2^{3}

** = 8**

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

**8.****Implementation:**

**Implementation:**

__Program:__

__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:__

__Input:__```
Enter the 2 numbers specifying the range:
5 7
```

__Output:__

__Output:__`The bitwise AND of the numbers in this range is 4.`

**Time Complexity**

**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**

**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)__

__Bit Manipulation (Considering MSB)__

__Algorithm__

__Algorithm__- Find the
of both the numbers,**MSB**and**L**.**R** - If the position of
differs, the result is**MSB**.**0** - If the positions are the same, say
,**MSB1**is added to the final answer, and it is subtracted from both**2**^{MSB1}and**L**.**R** - The above step is repeated for the new values of
and**L**until the position of**R**differs.**MSB**

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**^{2 }** = ANS + 4 **

** = 0 + 4 **

** = 4**

**L = 5 - 2 ^{2 }= 5 - 4 = 1**

**R = 7 - 2 ^{2} = 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:**

**Implementation:**

__Program:__

__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:__

__Input:__```
Enter the 2 numbers specifying the range:
5 7
```

__Output:__

__Output:__`The bitwise AND of the numbers in this range is 4.`

**Time Complexity**

**Time Complexity**

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

Since there are

*bits in a number and we are going through all the bits one by one, the time complexity of this approach is*

**log(L)**

**O(log(L)).****Space Complexity**

**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__

__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

*and*

__Brute Force__*and crack your interviews like a Ninja!*

__Bit Manipulation__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.

Comments

## No comments yet

## Be the first to share what you think