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.

Example

Input

Input any number: 22

Output

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.

Leading zeros in a binary 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;

Output

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 😉

About Pankaj

Pankaj Prakash is the founder, editor and blogger at Codeforwin. He loves to learn new techs and write programming articles especially for beginners. He works at Vasudhaika Software Sols as a Software Design Engineer and manages Codeforwin. In short Pankaj is Web developer, Blogger, Learner, Tech and Music lover.

Comments and discussion
Have a doubt, write here. I will help my best.
Before commenting you must escape your source code before commenting. Paste your source code inside
<pre><code> ----Your Source Code---- </code></pre>