ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Bitwise and of number range

prodevelopertutorial March 30, 2020

You are given a number range, you need to find the bitwise and of all the numbers in the range.

 

Example:

 

[5, 7]

 

The bitwise and of 5, 6, 7 will be 4.

 

The solution is very simple, once you understand the concept below:

 

Let’s take small example and try to understand.

We shall find bitwise & of the range 4, 5, 6, 7.

 

Bitwise and of number range

 

As you see that bitwise and will return 1 if all the bits are 1.

 

Again consider the range 8, 9, 10, 11, 12

 

Here also the pattern is the same. You see that except the most significant bit, all other bits are zero.

 

Once solution can be doing bit by bit & operation. But this is not efficient.

 

And the only time we get 1, is if both the numbers m and n are same.

 

So what we can do is, we can right shift both the digits by 1, till both of the digits become same. We should also keep track of how much shift has been done.

 

Then, when both the numbers become same, we can left shift the number of times we performed right shift. Hence we arrive at the solution.

 

Solution in C++

 

#include<iostream>
using namespace std;

int range_bitwise_and(int m, int n) 
{
    int shift = 0;
     
    while (m != n) 
    {
        shift++;
        m = m >> 1;
        n = n >> 1;
    }
 
return m << shift;
}

int main()
{
    int num_1 = 5;
    int num_2 = 7;

    cout<<"solution = "<<range_bitwise_and(num_1, num_2)<<endl;
}

Output:

 

solution = 4

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io