C program to find the Highest Bit Set for any given Integer

Find the highest bit set of a number in C: Here, we are going to see how to use bitwise operators to find the highest bit set in the binary representation of given integer?
Submitted by Radib Kar, on December 21, 2018

Problem statement: Write a C program to find the Highest Bit Set for any given Integer.

Solution: We can use bitwise operator here to solve the problem.

Pre-requisite: Input number n

Algorithm:

```1)  Set count=0 & store= -1
2)  Do bit wise AND between n and 1.
n & 1

let n be a7a6a5a4a3a2a1a0
1->00000001
So doing bitwise AND (refer to published article on bitwise operators)
will result in all bits 0 except the LSB which will be a0.
If a0 is 1 then it is set, else not set.
If a0 is 1 then the bitwise AND results in 00000001 (1) else 00000000 (0)

Thus,
IF
n& 1 ==1 //current bit is set
update store to current count value.
END IF

3)  count++;
4)  Right shift n by 1
n = n >> 1
5)  IF n==0
Break
ELSE
REPEAT step 2, 3, 4
6)  IF store==-1
No set bit
Else
Print store
```

Example with Explanation:

Highest set bit in 12 (0-index based position, i.e., LSB is 0th bit): 12 → 00001100

```Initially,
Count=0
Store=-1

So first iteration:
n=12 //00001100
n& 1 =0
store=-1
count=1
n=n>>1 (n=6) //00000110

So second iteration:
n=6 //00000110
n& 1 =0
store=-1
count=2
n=n>>1 (n=3) //00000011

So third iteration:
n=3 //00000011
n& 1 =1
store=2
count=3
n=n>>1 (n=1) //00000001

So fourth iteration:
n=1 //00000001
n& 1 =1
store=3
count=4
n=n>>1 (n=0) //00000000
program terminates
Print store, 3

Highest bit set: 3
```

C implementation

```#include <stdio.h>

int main()
{
unsigned int n;
printf("enter the integer\n");
scanf("%d",&n);
int count=0,store=-1;
while(n!=0){
if(n & 1 == 1) //if current bit is set
store=count; //update store
n=n>>1; //right shift
count++; //increase count
}

if(store==-1){//if store not updated
printf("No bit is set\n"); //no set bit present at all
return 0;
}
printf("Highest bit set ");
//printing highest set bit
printf("in its binary representation: %d \n",store);

return 0;
}
```

Output

```enter the integer
12
Highest bit set in its binary representation: 3
```

TOP Interview Coding Problems/Challenges

Learn PCB Designing: PCB DESIGNING TUTORIAL

 Recommended posts C Tips & Tricks, C++ Tips & Tricks Introduction to Linux (Its modes, Safety, Most popular Applications) Linux Best Distros of 2018 C programming optimization techniques Differences b/w C & Embedded C? Embedded C Interview Q. & A. C programming tips for Embedded Development Basic rules of writing a C program Important points (rules) to remember while writing C/C++ program Top 5 Websites for solving programming challenges Read more...

 Others... Computer G.K. (MCQ) Most viewed pages... Categories...

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates