Calculates the number of paths in a n*n (square) lattice

lattice-paths.c

#import <stdio.h>
#import <stdlib.h>
#import <math.h>

// Retuns the number of paths in a n*n (square) lattice
// Paths can only move rightward or downward
// Paths start at top left and end at bottom right
// Receives an argument `n` which is the length of one side of the square lattice

/* Visual examples:

2x2 lattice
######----+   ######----+
|    #    |   |    #    |
+----######   +----#----+
|    |    #   |    #    |
+----+----#   +----######
R D R D       R D D R
0 1 0 1       0 1 1 0

3x3 lattice:
######----+----+    ######----+----+
|    #    |    |    |    #    |    |
+----###########    +----#----+----+
|    |    |    #    |    #    |    |
+----+----+----#    +----#----+----+
|    |    |    #    |    #    |    |
+----+----+----#    +----###########
R D R R D D         R D D D R R
0 1 0 0 1 1         0 1 1 1 0 0
*/

unsigned long long int latticePaths(unsigned int n)
{
	// Paths can be represented as permutations of R and D (right and down).
	// We only want paths that have the same number of rightward
	// and downward movements (they end up at the opposite corner).
	// Therefore, we only want permutations of R and D where
	// the count of R is equal to the count of D.
	// We express R as 0 and D as 1.

	// Length of each permutation
	unsigned int len = n + n;

	// Number of downward moves (maximum n)
	unsigned int ones;

	// Number of paths found (might be big)
	unsigned long long int count = 0;

	// Where to start permutations
	// (we will not find any valid permutations before 2^n - 1)
	unsigned int start = (1 << n) - 1;

	// Where to end permutations
	// should stop at halfway through permutations: 2^(len-1)
	// We only need to check half, since the other half
	// are just flipped versions of the first half.
	unsigned int end = (1 << (len - 1)) - (1 << (n - 1)) + 1;

	// Main counting loop
	unsigned int i;
	for (i = start; i < end; i++)
	{
		// Count the number of ones in the binary representation of this number
		// int num = i;
		// for (ones = 0; num > 0; ones++) num &= num - 1;

		// Wow this is fast: (GCC only, compile with -O3 for optimizations)
		ones = __builtin_popcount(i);

		// Increase count if no. of ones is exactly n
		// (equal amounts of zeros and ones)
		if (ones == n) count++;
	}

	// We only found half, the other half are just inverses
	// so we return twice the number we counted
	return count << 1;
}

int main(int argc, char const *argv[])
{
	// The counted paths
	unsigned long long int count;

	// The total number of permutations for this lattice
	unsigned long long int permutations;

	// The fraction of permutations which are valid paths in this lattice
	float fraction;

	// Read the size of the lattice from arguments list
	unsigned int size = atoi(argv[1]);;

	// total permutations = 2^(size + size)
	permutations = 1 << (size << 1);

	// Count the valid paths
	count = latticePaths(size);

	fraction = (float) count / permutations;

	printf("latticePaths(%d) = %llu\n", size, count);
	printf("fraction (%llu / %llu) = %f\n", count, permutations, fraction);

	return 0;
}