Alien Art Drawn With Surprisingly Simple Math

April 13, 2021 by Michael Shaub 20 Comments

Programmer [aemkei] Tweeted the formula (x ^ y) % 9 alongside code for more “alien art”. But how can a formula as simple as (x ^ y) % 9 result in a complex design? The combination of Bitwise XOR (^) and Modulo (%) generate a repeating pattern that’s still complex enough to satisfy the eye, and it’s ok if that doesn’t sound like an explanation. Bitwise operations are useful when working with memory and shift registers, but also worth learning if you want to drive lines or matrices of LEDs or interpret combinations of multiple switches, or in this case a great way to throw an interesting test pattern up on a new flip-dot display or low-res LED matrix. Are you into it? We are, so let’s jump in.

XOR Truth Table
	0b00	0b01	0b10	0b11
0b00	0b00	0b01	0b10	0b11
0b01	0b01	0b00	0b11	0b10
0b10	0b10	0b11	0b00	0b01
0b11	0b11	0b10	0b01	0b00

Bitwise XOR compares each binary digit of the two inputs. The XOR returns a 1 when only one of the two digits is a 1, otherwise, it returns a zero for that position. Let’s say the coordinates were 3, 2. Converted to binary we have 0b11 and 0b10. From this truth table, we can see the most-significant digits are both 1, returning a 0, while only one of the least-significant digits is a 1, so the comparison returns a 1.

Moving onto the %, which is the Modulo operator has nothing to do with percentages. This operator divides two numbers and returns the remainder if any. Take 9 % 5. When dividing 9 by 5, 5 goes in once with a remainder of 4 so 9 % 5 = 4. Now our original formula from the top will draw a black box for every ninth number except that the bitwise XOR throws a wrench into that count, varying how often a number divisible by 9 appears and supplying the complexity necessary for these awesome patterns.

What are the most interesting designs can you create in a simple formula?

These Bit Twiddling Tricks Will Make Your Coworkers Hate You

January 16, 2020 by Kerry Scharfglass 32 Comments

In the embedded world, twiddling a few bits is expected behavior. Firmware is far enough down the stack that the author may care about the number of bits and bytes used, or needs to work with registers directly to make the machine dance. Usually these operations are confined to the typical shifting and masking but sometimes a problem calls for more exotic solutions. If you need to descend down these dark depths you invariably come across the classic Bit Twiddling Hacks collected by [Sean Eron Anderson]. Here be dragons.

Discussions of bit math are great opportunities to revisit Wikipedia’s superb illustrations

Bit Twiddling Hacks is exactly as described; a page full of snippets and suggestions for how to perform all manner of bit math in convenient or efficient ways. To our surprise upon reading the disclaimer at the top of the page, [Sean] observes that so many people have used the contents of the page that it’s effectively all been thoroughly tested. Considering how esoteric some of the snippets are we’d love to know how the darkest corners found use.

The page contains a variety of nifty tricks. Interview content like counting set bits makes an early appearance. There’s more esoteric content like this trick for interleaving the bits in two u16’s into a single u32, or rounding up to the next power of two by casting floats. This author has only been forced to turn to Bit Twiddling Hacks on one occasion: to sign extend the output from an unfortunately designed sensor with unusual length registers.

Next time you need to perform an operation with bitmatch, check out Bit Twiddling Hacks. Have you ever needed it in production? How did you use it? We’d love to hear about it in the comments.