Home » C programs » C bitwise operator's programs

C program to Count the Number of Trailing Zeroes in an Integer

Count the number of trailing zeroes in an integer in C: Here, we are going to see how to use bitwise operators for counting number of trailing zeros in the binary representation of an integer?
Submitted by Radib Kar, on December 21, 2018

Problem statement: Write a C program to Count the Number of Trailing Zeroes in the binary representation of an Integer.

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

Pre-requisite: Input number n

Algorithm:

1)  Set count=0
2)  Do bit wise AND with 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 0 then the Integer has trailing zero else don’t have
    Thus,
    IF
        n& 1 = =0
        count++
    ELSE
        Break; //no more trailing zero since current LSB is 1
    END IF-ELSE
3)  Right shift n by 1
    n=n>>1
4)  IF n==0
        Break
    ELSE
        REPEAT step 2, 3
5)  Print

Example with Explanation:

Trailing zeroes in 12: 12 → 00001100

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

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

    So third iteration:
    n=3 //00000011
    n & 1 =1 
    break
    print count=2
    No of trailing zeroes: 2

C implementation

#include <stdio.h>

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

	printf("no of trailing zero ");
	//print no of trailing zero
	printf("in its binary representation: %d \n",count); 

	return 0;
}

Output (first run)

enter the integer
12
no of trailing zero in its binary representation: 2

Output (second run)

enter the integer
13
no of trailing zero in its binary representation: 0




Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.



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

© https://www.includehelp.com some rights reserved.