Bitwise Set bit questions

Problem Statement:

In this chapter we shall solve few problems related to Bitwise Set bit.

1. Find the total number of set bits from 1 to N
2. Find the position of the only set bit
3. Find if two numbers differ at one bit position only

Find the total number of set bits from 1 to N

Input: n = 3
Output: 4

Explanation:

As N = 3.

1 = 0001
2 = 0010
3 = 0011

So total number of set bits = 4.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_set>
#include <queue>

using namespace std;

int count_set_bits_util(unsigned int x)
{
    if (x <= 0)
        return 0;
    return (x % 2 == 0 ? 0 : 1) + count_set_bits_util(x / 2);
}

int countSetBits(int n)
{
    int bitCount = 0; 
 
    for (int i = 1; i <= n; i++)
        bitCount += count_set_bits_util(i);
 
    return bitCount;
}
 
int main()
{
    int n = 4;
    cout<<"Total set bit count is = "<< countSetBits(n)<<endl;
    return 0;
}

Output:

Total set bit count is = 5

2. Find the position of the only set bit

You are given a number that has only one set bit and all other bits are 0 in its binary representation. Find the only set bit.

Solution in very simple.

First we will check if the number is a power of 2. If it is not, we return a error message. Because only the numbers that are power of 2, will have only one set bit in its binary form.

Then if the number is a power of 2, then we start form the right most bit and start searching for set bit.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_set>
#include <queue>

using namespace std;

int is_num_power_of_two(unsigned n) 
{ 
    return n && (!(n & (n - 1))); 
} 
  
int find_set_bit(unsigned n) 
{ 
    if (!is_num_power_of_two(n)) 
        return -1; 
  
    unsigned i = 1, pos = 1; 

    while (!(i & n)) 
    { 
        i = i << 1; 
        ++pos; 
    } 
  
    return pos; 
} 
  
int main(void) 
{ 
    int n = 16; 
    int pos = find_set_bit(n); 
    if (pos == -1) 
      cout << "n = " << n << ", Invalid number" << endl;
    else 
      cout << "n = " << n << ", Position " << pos << endl; 

    return 0; 
} 

Output:

n = 16, Position 5

3. Find if two numbers differ at one bit position only

Input : a = 2, b = 3
2 in binary = 0010
3 in binary = 0011

Output : Yes

The solution is very simple.
Then we check if the number is a power of 2.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_set>
#include <queue>

using namespace std;

bool check_if_num_power_of_two(unsigned int x) 
{ 

    return x && (!(x & (x - 1))); 
} 
  

bool check_if_num_differ_by_one_bit( int a, int b) 
{ 
    return check_if_num_power_of_two(a ^ b); 
} 
  
int main() 
{ 
   int a = 2;
   int b = 3; 
    if (check_if_num_differ_by_one_bit(a, b)) 
        cout << "Yes"<<endl; 
    else
        cout << "No"<<endl; 
    return 0; 
}

Output:

yes