C Program to Count the Number of Trailing Zeros in a Binary Number

In this article, we will discuss different ways to count the number of trailing in a given integer in its binary form.

What are Trailing Zeros?

Trailing zeros are a sequence of zeros starting from the least significant place in a number, after which no other digit follows. For example, the number of trailing zeros in 100100 is 2, the number of trailing zeros in 1000 is 3.

Our program will accept the input in decimal form and output the number of trailing zeros in its binary.

For example,

Input
32
Output
5
Explaination
Binary string of 32 = 100000
Number of trailing zeros = 5

We can solve this problem in 3 ways

  1. Using Bitwise Operators
  2. Without Using Bitwise Operators
  3. Using itoa()

Count the Number of Trailing Zeros in a Binary Number using Bitwise Operators

Steps

  1. Take input from the user. Let the input be N.
  2. Initialize a variable count = 0 to store the trailing zeros count.
  3. Repeat the following steps while N is greater than zero and the rightmost bit of N is zero.
    1. Increment count by one.
    2. Since we have counted the right-most zero in the above step, we right-shift N by one to move to the next bit.
  4. The number of trailing zero is equal to count.
#include <stdio.h>
#include <math.h>

// returns the number of trailing zeros in n
int trailing_zeros(int n) {

	int count = 0;

	// the following loop runs while
	// n is greater than zero and right most bit of n is 0
	// ( n & 1 ) performs bitwise AND of n and 1
	// if the rightmost digit of n is 1, ( n & 1 ) outputs 1
	// if the rightmost digit of n is 0, ( n & 1 ) outputs 0
	while (n > 0 && (n & 1) == 0) {

		count = count + 1;	// increment count
		n = n >> 1; 		// rightshift n by one

	}

	return count;

}

int main() {

	int n;
	printf("Enter a Number: ");
	scanf("%d", &n);
	printf("Number of trailing zeros in %d = %d", n, trailing_zeros(n));

}

Output

Enter a Number: 16
Number of trailing zeros in 16 = 4

Count the Number of Trailing Zeros in a Binary Number using without Bitwise Operators

This method is very similar to the previous one. The only difference is instead of using bitwise operators, we use arithmetic operators to perform RIGHT SHIFT and BITWISE AND.

To RIGHT SHIFT a number by one bit, we simply divide the number by 2. To check if the rightmost bit is 1 or 0, we use the MOD ( % ) operator. If a number is divisible by 2, then the rightmost bit is zero otherwise the right most bit is one.

#include <stdio.h>
#include <math.h>

// returns the number of trailing zeros in n
int trailing_zeros(int n) {

	int count = 0;

	// the following loop runs while
	// n is greater than zero and rightmost bit of n is 0
	// if the rightmost digit of n is 1, ( n % 2 ) outputs 1
	// if the rightmost digit of n is 0, ( n % 2 ) outputs 0
	while (n > 0 && (n % 2) == 0) {

		count = count + 1;	// increment count
		n = n / 2; 			// rightshift n by one

	}

	return count;

}

int main() {

	int n;
	printf("Enter a Number: ");
	scanf("%d", &n);

	printf("Number of trailing zeros in %d = %d", n, trailing_zeros(n));

}

Output

Enter a Number: 20
Number of trailing zeros in 20 = 2

Count the Number of Trailing Zeros in a Binary Number using itoa()

In this method, we use itoa() to convert the input integer to it’s corresponding binary string. After that, we use a loop to count the number of trailing zeros.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// returns the number of trailing zeros in n
int trailing_zeros(int n) {

	int count = 0;
	char buffer[64]; // buffer to store binary string

	itoa(n, buffer, 2); // convert n to binary and store the binary string of n in buffer

	for (int i = strlen(buffer) - 1; i >= 0; --i) {

		// break the loop on encountering a '1'
		if (buffer[i] == '1')
			break;
		count = count + 1;

	}

	return count;

}

int main() {

	int n;
	printf("Enter a Number: ");
	scanf("%d", &n);

	printf("Number of trailing zeros in %d = %d", n, trailing_zeros(n));

}

Ouput

Enter a Number: 192
Number of trailing zeros in 192 = 6

Read

Leave a Comment

Your email address will not be published. Required fields are marked *