/*
 * Interleave bits by Binary Magic Numbers
 */
#include <stdio.h>
#include <stdint.h>

#define u64(x) ((uint64_t)x)

static const uint64_t B[] = {
	0x5555555555555555ULL,
	0x3333333333333333ULL,
	0x0f0f0f0f0f0f0f0fULL,
	0x00ff00ff00ff00ffULL,
	0x0000ffff0000ffffULL,
};
static const uint64_t S[] = {
	1,
	1<<1,
	1<<2,
	1<<3,
	1<<4
};

unsigned int x; // Interleave lower 16 bits of x and y, so the bits of x
unsigned int y; // are in the even positions and bits from y in the odd;
unsigned int z; // z gets the resulting 32-bit Morton Number.  
                // x and y must initially be less than 65536.
		//
void
print_bits(uint64_t number) {
        uint64_t mask = u64(1) << 63;

        while (mask) {
		printf("%d", !!(mask&number));
                mask >>= 1;
        }
}

#define p(x)				\
	do {				\
		printf("%s=", #x);	\
		print_bits(x);		\
		printf("\n");		\
	} while(0)



/**
 * Zero Morton.
 *
 * "Traditional" bit-wise number interleaving are called Morton numbers, but in
 * our case, one of the numbers is _always_ zero
 */
uint64_t zmort(uint32_t n)
{
	uint64_t x = u64(n);

	p(x);
	x = (x | (x << S[4])) & B[4];
	p(x);
	x = (x | (x << S[3])) & B[3];
	p(x);
	x = (x | (x << S[2])) & B[2];
	p(x);
	x = (x | (x << S[1])) & B[1];
	p(x);
	x = (x | (x << S[0])) & B[0];
	p(x);
	x <<= 1;

	p(x);
	return x;
}

int main()
{
	uint32_t x = (uint32_t)~0;
	zmort(x);
	return 0;
}