Home » C programs » C bitwise operators programs

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 0^th 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    

C Bitwise Operators Programs »

---