Count unset bits in a range in C++

We are given an integer number let’s say, num and the range with left and right values. The task is to firstly calculate the binary digit of a number and then set the loop from the left digit till the right digit and then in the given range calculate the unset bits.

Unset bits in a binary number is represented by 0. Whenever we calculate the binary number of an integer value then it is formed as the combination of 0’s and 1’s. So, the digit 0 is known as unset bit in the terms of the computer.

Input − int number = 50, left = 2, right = 5

Output − Count of total unset bits in a range are − 2

Explanation −Binary representation of a number 50 is 110010 and we have a range starting from left = 2 which is having bit as 1 and ending to right = 5 which is having bit 1 and in between the range we have two 0’s. So the count of unset bits is 2.

Input − int number = 42, left = 1, right 6

Output − Count of total unset bits in a range are − 3

Explanation − Binary representation of a number 42 is 101010 and we have a range starting from left = 1 which is having bit as 1 and ending to right = 6 which is having bit 0 and in between the range we have three 0’s. So the count is 3.

Approach used in the below program is as follows

• Input the number in a variable of integer type and also the range with left and right integer values.

• Declare a variable count to store the total count of set bits of type unsigned int

• Start loop FOR from i to 1<<7 and i > 0 and i to i / 2

• Inside the loop, check num & 1 == TRUE then print 1 else print 0

• Start loop FOR from i to left till right value

• Inside the loop, increment the total number of digits between the given range

• Start loop while to calculate the total count of bits till number isn’t 0

• Inside the loop, set count = count + number & 1 and also set number >>=1

• Set a temporary variable let’s say, a with ((1 << right) - 1) ^ ((1 << (left - 1)) - 1);

• Also, set count with count & a

• In the end, set count as the total number of bits in a range - total number of set bits in a range.

Example

 Live Demo

#include<iostream> using namespace std; //Count total unset bits in a range unsigned int unset_bits(unsigned int number, unsigned int left, unsigned int right){    unsigned int count = 0;    unsigned int total_bits = 0;    unsigned i;    //display the 8-bit number    cout<<"8-bit number of "<<number<<" is: ";    for (i = 1 << 7; i > 0; i = i / 2){       (number & i)? cout<<"1": cout<<"0";    }    //calculate total number of bits in a given range    for(i = left; i<=right; i++){       total_bits++;    }    //calculate the total bits in a number    while (number){       count += number & 1;       number >>= 1;    }    //calculate the set bit in a range    int a = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1);    count = count & a;    //subtract set bits from the total bits in a range    count = total_bits - count;    cout<<"\nCount of total unset bits in a range are: "<<count; } int main(){    unsigned int number = 80;    unsigned int left = 1, right = 4;    unset_bits(number, left, right);    return 0; }

Output

If we run the above code it will generate the following output −

8-bit number of 80 is: 01010000 Count of total unset bits in a range are: 2