Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Builtin GCC Functions - __builtin_clz(); __builtin_ctz(); __builtin_popcount(); (http://www.go4expert.com/articles/builtin-gcc-functions-builtinclz-t29238/)

Trinity 30Oct2012 13:03

Builtin GCC Functions - __builtin_clz(); __builtin_ctz(); __builtin_popcount();
 
GCC provides quite a lot of builtin functions. These functions are part of standard C offered by the compiler and may come in various variants as per the gcc. These are also termed as hardware specific functions which are internally implemented in assembly or we can say machine instructions, with wide usage in low level programming and are generally target optimized.

These functions are prefixed with “__builtin”. There are a huge lot of builtin functions by GCC, however here in this article, we shall be learning about two such builtin functions.
Code:

__builtin_clz();
__builtin_ctz();
__builtin_popcount();

Lets learn more about these methods.

Function __builtin_clz



This builtin method is provided by GCC to count the number of leading zero’s in variable.

The Syntax:
Code:

int __builtin_clz (unsigned int x)
It takes the input parameter as a number for which the the count of leading zero’s is to be determined. It returns the count of leading zero’s as expected.

Taking for example, lets take a number 16. An int takes 4 bytes in gcc. Its binary representation is
Code:

00000000 00000000 00000000 00010000
Counting the number of leading zero’s is 27 which should be our result for this case..

Function __builtin_ctz



This builtin method by GCC determines the count of trailing zero in the binary representation of a number.

The Syntax:
Code:

int __builtin_ctz (unsigned int x)
The input parameter is the number for which the the count of trailing zero’s is to be determined. It returns the count of trailing zero’s as expected.

Taking for example, lets take the same number 16. Again, an int takes 4 bytes in gcc. Its binary representation is
Code:

00000000 00000000 00000000 00010000
Counting the number of trailing zero’s is 4 which should be our result for this case..

Function __builtin_popcount



This builtin method by GCC determines the number of one’s in the binary representation of a number.

The Syntax:
Code:

int __builtin_popcount (unsigned int x)
The input parameter is the number for which the the number of 1’s is to be determined. It returns the count of set bits as expected..

Taking for example, lets take the same number 16. Again, an int takes 4 bytes in gcc. Its binary representation is
Code:

00000000 00000000 00000000 00010000
Counting the number of one’s is just 1, which should be our result for this case..

Complete Example



Here is a complete example program which demonstrates the use of these builtin methods.
Code:

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

int main()
{
    int num = 16;
    int clz = 0;
    int ctz = 0;
    int ones = 0;

    clz = __builtin_clz(num);
    printf("Number of leading zero's in %d is %d\n", num, clz); 

    clz = __builtin_clz(-num);
    printf("Number of leading zero's in %d is %d\n", -num, clz); 

    ctz = __builtin_ctz(num); 
    printf("Number of trailing zero's in %d is %d\n", num, ctz);

    ones = __builtin_popcount(num); 
    printf("Number of one's in %d is %d\n", num, ones);   

    return 0;
}

On running the above example program, here is our output:
Code:

Number of leading zero's in 16 is 27
Number of leading zero's in -16 is 0
Number of trailing zero's in 16 is 4
Number of one's in 16 is 1

Great! it works fine as per our understanding. Note, it even worked fine for negative numbers which are stored as two’s complement.

Conclusion



These two builtin functions are really helpful for low level bitwise operations and manipulation computations. Many advanced and optimized algorithms need to count the leading or trailing zero’s of a number. However, there are many variants available for these builtin functions to cater input parameters as unsigned int, unsigned long, etc.


All times are GMT +5.5. The time now is 22:40.