In this blog post, I will teach you how to write C/C++ program to find position of the only set bit. After reading this post you able to write an efficient program to find position of the only set bit.
Examples,
Input : n = 8
Here's a simple ASCII representation of 8 (an 8-bit integer):
7 6 5 4 3 2 1 0 (Bit position)
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | (Example bit values)
+---+---+---+---+---+---+---+---+
^
|
3rd is the position of the only set bit.
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) +---+---+---+---+---+---+---+---+ Invalid input have more than 1 bit set
Let’s see the problem statements for this question.
Problem Statement: Given a number “n” having only one ‘1’ and all other ’0’s in its binary representation, find position of the only set bit. If “n” is 0 or have more than 1 set bit, then the number would be invalid. The position of set bit ‘1’ must be counted from the LSB side in the binary representation of the number.
Disclaimer: Try to solve the problem yourself first otherwise it would be not worth solving this problem.
Get position of the only set bit using the log2():
The approach is very simple, you have to first check number is power of 2’s or not. I have already written an article on how to check whether a given number is power of two or not. If the number is power of two, then you can find the position of the bits using the log2() function.
C program to get position of right most set Bit:
/*
C program to get position
of only set Bit:
*/
#include <stdio.h>
#include <math.h>
//C Function to check if num is power of 2
int checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
const int ret = (num > 0)?
((num != 0)&&((num & (num-1)) == 0)):0;
return ret ;
}
int getPositionOnlySetBit(int n)
{
const int isPowerOfTwo = checkPowerOfTwo(n);
int posSetBit = 0;
if(isPowerOfTwo)
{
posSetBit = log2(n);
}
return posSetBit;
}
int main()
{
int n = 8;
const int pos = getPositionOnlySetBit(n);
if(pos!= 0)
{
printf("Set Bit Position = %d\n",pos);
}
else
{
printf("Invalid number\n");
}
return 0;
}
Output:
Set Bit Position = 3
C++ program to get position of right most set Bit:
/*
C++ program to get position
of only set Bit:
*/
#include <math.h>
#include <iostream>
//C++ Function to check if num is power of 2
int checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
const int ret = (num > 0)?
((num != 0)&&((num & (num-1)) == 0)):0;
return ret ;
}
int getPositionOnlySetBit(int n)
{
const int isPowerOfTwo = checkPowerOfTwo(n);
int posSetBit = 0;
if(isPowerOfTwo)
{
posSetBit = log2(n);
}
return posSetBit;
}
int main()
{
int n = 8;
const int pos = getPositionOnlySetBit(n);
if(pos!= 0)
{
std::cout <<"Set Bit Position = " << pos <<std::endl;
}
else
{
std::cout << "Invalid number\n" << std::endl;
}
return 0;
}
Output:
Set Bit Position = 3
Using the De-Bruijn sequence:
If you already know that given number ‘n’ is a power of 2, then beside using log2() you can use DeBruijn sequence to find the only set bit. Consider the below code.
The below code computes the position of only set bit for a 32-bit integer with the help of a small lookup table. It requires only requires the fewest operations, but this offers a reasonable compromise between table size and speed.
/*
Reference:
https://graphics.stanford.edu/~seander/bithacks.html
C program to get position
of only set Bit:
*/
#include <stdio.h>
#include <stdint.h>
//C Function to check if num is power of 2
int checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
const int ret = (num > 0)?
((num != 0)&&((num & (num-1)) == 0)):0;
return ret ;
}
static const int table[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
int getPositionOnlySetBit(uint32_t n)
{
const int isPowerOfTwo = checkPowerOfTwo(n);
int posSetBit = 0;
if(isPowerOfTwo)
{
posSetBit = table[((uint32_t)((n & -n) * 0x077CB531U)) >> 27];
}
return posSetBit;
}
int main()
{
uint32_t n = 32;
const int pos = getPositionOnlySetBit(n);
if(pos!= 0)
{
printf("Set Bit Position = %d\n",pos);
}
else
{
printf("Invalid number\n");
}
return 0;
}
Output:
Set Bit Position = 5
Get position of the only set bit using the right shift operator (>>):
Using the right shift operator, you can also find the position of the set bit. In this approach we will right shift the number ‘n’ one by one until ‘n’ becomes 0. Also, inside the loop we will increment the variable posSetBit to track the count we shifted ‘n’ to make it zero. The value of count represents the position of set bit in ‘n’.
/*
C program to get position
of only set Bit:
*/
#include <stdio.h>
//C Function to check if num is power of 2
int checkPowerOfTwo(int num)
{
/* Zero and negative numbers
are not powers of two*/
const int ret = (num > 0)?
((num != 0)&&((num & (num-1)) == 0)):0;
return ret ;
}
int getPositionOnlySetBit(int n)
{
const int isPowerOfTwo = checkPowerOfTwo(n);
int posSetBit = 0;
if(isPowerOfTwo)
{
/* One by one move the only
set bit to right till n become 0
*/
while (n)
{
n = n >> 1;
// increment posSetBit of shifts
++posSetBit;
}
/*Bit position start with 0, so
subtracting 1
*/
posSetBit-=1;
}
return posSetBit;
}
int main()
{
int n = 8;
const int pos = getPositionOnlySetBit(n);
if(pos!= 0)
{
printf("Set Bit Position = %d\n",pos);
}
else
{
printf("Invalid number\n");
}
return 0;
}
Output:
Set Bit Position = 3
Recommended Post
- Turn off the rightmost set bit.
- Count Set bits in an Integer.
- Count Set bits in an Integer using the lookup table.
- Rotate bits of a number.
- How to set, clear or toggle a single bit in C/C++?
- Macros for Bit Manipulation in C/C++.
- 5 Ways to Check if Two Integers have Opposite Signs.
- C Program to Find whether a given integer is a power of three or not.
- Operator Precedence And Associativity In C.
- Operators in C language