Find most significant set bit of a number

In this blog post, I will teach you how to write C/C++ program to find most significant set bit of a number. After reading this post you able to write an efficient program to find most significant set bit of a number.

Examples,

Input : n = 9

Here's a simple ASCII representation of 9 (an 8-bit integer):
  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |  (Example bit values)
+---+---+---+---+---+---+---+---+
                  ^
                  |
                 3rd bit most significant set bit.

Output: 8

Explanation:
You can see the binary representation of 9.
The most significant bit corresponds to decimal number 8.

 

Input : n = 19

Here's a simple ASCII representation of 19 (an 8-bit integer):
  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |  (Example bit values)
+---+---+---+---+---+---+---+---+
              ^
              |
              4th bit most significant set bit.
Output: 16

Explanation:
You can see the binary representation of 19.
The most significant bit corresponds to decimal number 16.

 

Let’s see the problem statements for this question.

Problem Statement: Given an integer n, find the greatest number less than the given a number which is the power of two or find the most significant bit number.

 

Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.

 

Approach-1:

This is a simple way to get the most significant bit of a number.  In this solution you need to divide number n by 2 until it becomes 0 and increment a count while doing this. This count actually represents the position of MSB.

C program to get most significant bit of a number:

/*
C program to Find most significant
set bit of a number
*/
#include <stdio.h>

int setBitNumber(unsigned int n)
{
    int tmp = 0;
    if(n!= 0)
    {
        unsigned char msb = 0;
        n = n / 2;
        while (n != 0)
        {
            n = n / 2;
            msb++;
        }
        tmp =  (1 << msb);
    }

    return tmp;
}


int main()
{
    unsigned int n = 257;

    int value = setBitNumber(n);

    printf("%d",value);

    return 0;
}

Output: 256

 

C++ program to get most significant bit of a number:

/*
C++ program to Find most significant.
set bit of a number
*/
#include <iostream>

int setBitNumber(unsigned int n)
{
    int tmp = 0;
    if(n!= 0)
    {
        unsigned char msb = 0;
        n = n / 2;
        while (n != 0)
        {
            n = n / 2;
            msb++;
        }
        tmp =  (1 << msb);
    }

    return tmp;
}


int main()
{
    unsigned int n = 129;

    int value = setBitNumber(n);

    std::cout<< value<<std::endl;

    return 0;
}

Output: 128

 

Approach-2:

In this approach we use the shift operator beside the arithmetic division. But the concept is same as I have discussed above in the example code.

C program to find most significant bit of a number:

/*
C program to Find most significant
set bit of a number
*/
#include <stdio.h>

int setBitNumber(unsigned int n)
{
    int tmp = 0;
    if(n!= 0)
    {
        unsigned char msb = 0;
        n = n >> 1;
        while (n != 0)
        {
            n = n >> 1;
            msb++;
        }
        tmp =  (1 << msb);
    }
    return tmp;
}


int main()
{
    int n = 257;

    int value = setBitNumber(n);

    printf("%d",value);

    return 0;
}

 

 

C++ program to find most significant bit of a number:

/*
C++ program to Find most significant.
set bit of a number
*/
#include <iostream>

int setBitNumber(unsigned int n)
{
    int tmp = 0;
    if(n!= 0)
    {
        unsigned char msb = 0;
        n = n >> 1;
        while (n != 0)
        {
            n = n >> 1;
            msb++;
        }
        tmp =  (1 << msb);
    }
    return tmp;
}


int main()
{
    int n = 67;

    int value = setBitNumber(n);

    std::cout<< value<<std::endl;

    return 0;
}

Output: 64

 

Recommended Post