Home » C programs » C bitwise operators 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 program to Count the Number of Trailing Zeroes in an Integer

#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

C Bitwise Operators Programs »