Math is weird and is sometimes frustrating, but it can certainly be beautiful.
The Bit Order Shuffle. (For an explanation, keep reading.) Click for uncompressed BMP.
When I first took a Digital Electronics course years ago, the instructor started talking about what sounded like “big-Indian” and “little-Indian” formats. I wasn’t really sure what he was talking about — but then I read the textbook. (It’s actually useful, on occasion, provided that the instructor isn’t the author.) As it turns out, there are two main ways of storing binary numbers — with the “big end” first, or the “little end” first. Thus, “Big-Endian” and “Little-Endian.” Endian-ness, not “Indian-ness.”
This can’t be what the professor meant, right? (Drawing by Millard E. Carr)
In Big-Endian format, the largest bits (and bytes) of a binary number are stored first. So, the number 0100 would represent “four,” and the number 10100000 would represent “one hundred sixty.” Motorola processors (Freescale, these days) are big-endian.
In Little-Endian format, the order is reversed: the smallest bits come first. So, 0100 would represent “two,” and 10100000 would represent “five.” Intel CPUs are little-endian.
Both systems are well entrenched (although I confess I don’t understand why someone would use little-endian when most networks use big-endian), so it’s important to know about the problem of endianness, and how to convert between the two (using LIFO buffers, if dealing with serial data.)
But back to the “Bit Order Shuffle” image, above. It turns out that when you read the numbers in backwards order like this, you shuffle the value order of the numbers. 0000 will still be first in a list of four-bit numbers and 1111 will still be last — but 0001 will become 1000, jumping to the middle of the deck — and 0011 (three) will become 1100 (twelve) etc.
I decided to visualize this, and colored the numbers 0-1023 with a continuous color spectrum in the 24-bit RRGGBB space, with Red mapped to 255-(n/8), Green mapped to 255-abs(512-n)/4, and Blue mapped to n/8. (All values clamped 0-255.) In order to try to avoid the pattern being dominated by the last lines to be drawn rather than the overall pattern, the lines are drawn in random order, with the law of averages ensuring most or all lines were drawn.
As the pattern shows, an initially well-ordered set is shuffled — repeatably and reversibly — into a homogenous mix of values. It would be a good shuffle, if it wasn’t ultimately predictable.
As for my Dad’s “Indians” — they’ve found work as corporate bit-order spokespeople.
