C Program to count trailing zeros using bitwise operator

In this article, we have designed and implemented a C Program to count trailing zeros using bitwise operators only. This will involve AND and Left Shift bitwise operation.

Table of contents:

1. Problem Statement
2. Approach 1
3. C Program to count trailing zeros using bitwise operator

Learn:

• Basic Bitwise Operations: AND, OR, XOR, NOT, LEFT and more

Problem Statement

The problem is to count the number of trailing zeroes in a binary format representation of a given Integer. The challenge is to use only bitwise operations.

If the integer is 160, then binary representation will be 0b10100000. The number of trailing zeroes will be 5.

160 = 0b10100000

In this problem, we need not convert the number to binary format.

Implement the approach in C Programming Language.

Approach 1

The key idea to count trailing zeros using bitwise operations are:

• Check the lowest significant bit and if it is 0, increase count by 1.
• Check next bit from left to right (increasing significance).
• If you encounter a bit to be 1, end the process and return the count.

To check the lowest significant bit, you can do AND with 1.

N & 1

Similarly:

• 1: Lowest significant bit is set to 1 only
• 1 << 1: 2nd lowest significant bit is set to 1 only
• 1 << 2: 3rd lowest significant bit is set to 1 only
• and so on.

Only, AND and Left Shift bitwise operations are used in this approach.

C Program to count trailing zeros using bitwise operator

Following is the complete C Program to count trailing zeros using bitwise operator:

// Part of iq.opengenus.org
#include<stdio.h>
int countTrailingZeros(int num)
{
   int mask = 1;
   int count = 0;
   while (mask != 0) {
      if ((num & mask) == 0) {
          ++ count;
      }
      else {
          break;
      }
      mask = mask << 1;
   }
   return count;
}
 
int main() {
   int integer_number = 160;
   printf("Number of trailing zeros in %d in binary format is: %d", 
          integer_number, countTrailingZeros(integer_number));
   return 0;
}

Output:

Number of trailing zeros in 160 in binary format is: 5

With this article at OpenGenus, you must have the complete idea of how to implement a C Program to count trailing zeros using bitwise operator.