Fast binary GCD using trailing zero count.

gcd.c

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

// Everyone says "oh I know about double evaluation, it's no problem" and a few months down the road, you'll be debugging the silliest problems for hours on end.
#define max(a, b) ({ \
        __typeof__ (a) _a = (a); \
        __typeof__ (b) _b = (b); \
        _a > _b ? _a : _b; \
    })
#define min(a, b) ({ \
        __typeof__ (a) _a = (a); \
        __typeof__ (b) _b = (b); \
        _a < _b ? _a : _b; \
    })

int numberOfTrailingZeros(unsigned int num) __attribute__((always_inline,const));

unsigned int gcd(unsigned int first, unsigned int second) {
    /*
     * Find the GCD via the binary GCD algorithim, based on Euclid's algorithm.
     * See wikipedia to details: https://en.wikipedia.org/wiki/Binary_GCD_algorithm.
     * Agressively hand-optimized because YOLO.
     */
    // gcd(0,second) -> second, gcd(first,0) -> first, gcd() 
    if (first == 0 | second == 0) return max(first, second);
    // Compute the common powers of two
    int shift = min(numberOfTrailingZeros(first), numberOfTrailingZeros(second));
    // Discard any trailing zero bits to ensure 'first' is odd (strips all powers of two)
    first >>= numberOfTrailingZeros(first);
    do {
		// strip all factors of 2 in the second num, since they aren't common
		second >>= numberOfTrailingZeros(second);
        /*
         * Now the first and second are both odd numbers.
         * Ensure that second >= first, then subtract the first from the second.
         * NOTE: Uses min/max instead of an if-check to avoid branching.
         */
        int oldFirst = first;
        first = min(first, second);
        second = max(oldFirst, second);
        second -= first;
    } while (second != 0L);
    return first << shift;
}


int main(void) {
    // Disable stdout buffering
    setvbuf(stdout, NULL, _IONBF, 0);

    unsigned int first, second;
    puts("Enter ctrl-d (EOF) to exit at any time");
    do {
        printf("Numbers to find the GCD of: ");
        errno = 0;
        int i = scanf("%u %u", &first, &second);
        if (errno != 0) {
            perror("scanf");
            return 1;
        } else if (i == EOF) {
            puts("Encountered EOF, exiting program.");
            break;
        }
        printf("GCD of %d and %d: %d\n", first, second, gcd(first, second));
    } while (true);

    return 0;
}

//
// Utilities
//

inline int numberOfTrailingZeros(unsigned int num) {
    int result;
    __asm__(
        "tzcntl %[num], %[result]" // Trailing zeros count
        : [result] "=g"(result)
        : [num] "g"(num)
        : "cc" // AFAIK, tzcnt messes up condition codes
    );
    return result;
}