How to get position of right most set Bit

In this blog post, I will teach you how to write C/C++ program to get position of right most set bit. After reading this post you able to write an efficient program to get position of right most set bit.

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)
+---+---+---+---+---+---+---+---+
                              ^
                              |
                       0th is the position of the rightmost set bit.

 

Input : n = 12

Here's a simple ASCII representation of 12 (an 8-bit integer):

  7   6   5   4   3   2   1   0    (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |  (Example bit values)
+---+---+---+---+---+---+---+---+
                      ^
                      |
               2 is the position of rightmost set bit.

 

Let’s see the problem statements for this question.

Problem Statement: Given an integer n, get the position of right most set Bit.

 

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

 

Get position of rightmost set bit using two’s complement:

The bitwise operation (n&~(n-1)) isolates the rightmost set bit in “n”. The bitwise AND operation between n and ∼(n−1) return only the rightmost set bit of n by turning off all other bits. Now the last steps to use log2((n&~(n-1))) to get the position of rightmost set bit.

Let’s understand this concept with an example, suppose n = 12.

Suppose n is 12,

n =12
"n" in binary: 00001100

Step 1: n-1 > 11
/*
n-1 would have all the bits flipped after 
the rightmost set bit (including the set bit).
*/
"n"−1 in binary: 00001011


Step 2: ∼(n−1) (Complement of n−1)

∼(n−1) in binary: 11110100



Step 3: (n & ~(n - 1)):

((00001100) & (11110100)) is 00000100
You can see in step 3 on rightmost bit is set and other bits set to 0



Step 4: log2(n & ~(n - 1)):

/* calculates the position of the 
  rightmost set bit in a given number n.
*/

If n is 12 it returns 2, See the pictorial representation
for better understanding.

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

 

C program to get position of right most set Bit:

 

#include <stdio.h>
#include <math.h>
/*
C program to get position
of right most set Bit:
*/
int getPositionRightMostSetBit(unsigned int n)
{
    unsigned int hasOnlyRightSetBit = (n&~(n-1));

    int posOfRightMostSetBit = (int)log2(hasOnlyRightSetBit);

    return posOfRightMostSetBit;
}

int main()
{
    unsigned int n = 12;

    const unsigned int pos = getPositionRightMostSetBit(n);

    printf("Position =  %d",pos);

    return 0;
}

Output:

Position = 2

 

C++ program to get position of right most set Bit:

/*
C++ program to get position
of right most set Bit:
*/
#include <iostream>
#include <math.h>

int getPositionRightMostSetBit(unsigned int n)
{
    unsigned int hasOnlyRightSetBit = (n&~(n-1));

    int posOfRightMostSetBit = static_cast<int>(log2(hasOnlyRightSetBit));

    return posOfRightMostSetBit;
}

int main()
{
    unsigned int n = 12;

    const unsigned int pos = getPositionRightMostSetBit(n);

    std::cout<<"Right Most Set Bit Position = " << pos <<std::endl;

    return 0;
}

Output:

Right Most Set Bit Position = 2

 

Position of rightmost set bit using & and >> operator:

Follow the steps below to solve the problem:

  • Initialize posOfRightMostSetBit as 0 that will be used to keep track of the rightmost set bit positions.
  • Enters in if condition when n is non-zero number.
  • If n is non-zero number, then continue the while loop until the not found the rightmost set bit. In the while loop condition, we check the least significant bit of n using the bitwise AND operation ((n & 1) == 0).
  • In the while loop, we right shift n by 1 bit position to get the next LSB and increments the variable posOfRightMostSetBit.
  • Above process repeat until not get the LSB bit set.

Consider the below C program,

#include <stdio.h>
/*
C program to get position
of right most set Bit:
*/
int getPositionRightMostSetBit(unsigned int n)
{
    // Initialize position counter
    int posOfRightMostSetBit = 0;
    if(n != 0)
    {
        // Loop until the rightmost set bit is found
        while ((n & 1) == 0)
        {
            n >>= 1; // Right shift n by 1
            posOfRightMostSetBit++; // Increment position counter
        }
    }

    return posOfRightMostSetBit;
}

int main()
{
    unsigned int n = 1;

    const unsigned int pos = getPositionRightMostSetBit(n);

    printf("Right Most Set Bit Position =  %d",pos);

    return 0;
}

 

Recommended Post