C program to count leading zeros in a binary number

Write a C program to input any number from user and find total number of leading zeros of the given number. How to find total leading zeros of a given number (in binary representation) using bitwise operator in C programming. Logic to count total leading zeros of a given number using C programming.

Input any number: 22

Output leading zeros: 27 (using 4 byte signed integer)

Required knowledge

Bitwise operators, Data types, Variables and Expressions, Basic input/output, If else, For loop

Logic to count leading zeros in a binary number

Leading zeros in a binary number is equal to zeros preceding the highest order set bit of the number.

Step by step descriptive logic to count leading zeros in a binary number.

1. Input number from user. Store it in some variable say, num.
2. Find total bits required to store an integer in memory say, INT_SIZE = sizeof(int) * 8.
   

   Must know – How to find size of a data type using sizeof() operator.

3. Initialize a variable and set its MSB to 1, say msb = 1 << (INT_SIZE - 1);.
4. Initialize a variable to store leading zeros count, say count = 0;.
5. Run a loop from 0 to INT_SIZE. The loop structure should look like for(i=0; i<INT_SIZE; i++).
6. Inside the loop, left shift num, i times and check its MSB is set or not. If its MSB is set i.e. if((num << i) & msb) then terminate the loop; otherwise increment count by 1.

Program to count leading zeros in a binary number

/**
 * C program to count leading zeros in a binary number using bitwise operator
 */

#include <stdio.h>
#define INT_SIZE sizeof(int) * 8

int main()
{
    int num, count, msb, i;

    /* Input number from user */
    printf("Enter any number: ");
    scanf("%d", &num);

    // Equivalent to
    // 10000000 00000000 00000000 00000000
    msb = 1 << (INT_SIZE - 1);

    count = 0;

    /* Iterate over each bit */
    for(i=0; i<INT_SIZE; i++)
    {
        /* If leading set bit is found */
        if((num << i) & msb)
        {
            /* Terminate the loop */
            break;
        }

        count++;
    }

    printf("Total number of leading zeros in %d is %d", num, count);

    return 0;
}

Below is another short and effective approach to solve the program.

Program to count leading zeros in a binary number using while loop

/**
 * C program to count leading zeros in a binary number using bitwise operator
 */

#include <stdio.h>
#include <limits.h> // Used for INT_MAX

int main()
{
    int num, count;

    /* Input number from user */
    printf("Enter any number: ");
    scanf("%d", &num);

    count = 0;
    while(!(num & (~INT_MAX)))
    {
        count++;
        num <<= 1;
    }

    printf("Total number of leading zeros = %d", count);

    return 0;
}

INT_MAX is a constant defined in limits.h header file. It is used to get maximum range of integer.

The statement num <<= 1; is a shorthand assignment operator equivalent to num = num << 1;

Enter any number: 22
Total number of leading zeros in 22 is 27

Important Note: Different compilers may yield different output. Since, data types size is machine dependent.

Happy coding 😉