My favourite bit of bit twiddling doesn't seem to appear here - how to enumerate all the subsets of bits set. Like so many bit-twiddling hacks, I first saw this in chess engines:<p><a href="https://www.chessprogramming.org/Traversing_Subsets_of_a_Set" rel="nofollow">https://www.chessprogramming.org/Traversing_Subsets_of_a_Set</a>
I love these kinds of things and use them in GPU programming, among other things. Things have changed in a variety of ways: population count and count-trailing-zeros are generally available as fast instructions now. Multiply is also now just as fast as other operations, so is not to be avoided.<p>A couple examples. [1] computes the sum of the number of bytes used of four consecutive segments of a bezier path - each segment can be lineto, quadto, or curveto, can be the end of a path or not, and be i16 or f32. 4 tag bytes are packed into a 32 bit word, it computes all these, then sums them together.<p>[2] linearizes a recursive subdivision into an iterative loop. The stack depth is represented as the number of zeros in a word, so pushing the stack is a left shift, and popping is a right shift. It turns out you want to pop multiple levels at once, and the number of levels is computed by countTrailingZeros. ([2] is experimental Rust code, but I will adapt this into a compute shader)<p>[1]: <a href="https://github.com/linebender/piet-gpu/blob/main/piet-wgsl/shader/shared/pathtag.wgsl#L48" rel="nofollow">https://github.com/linebender/piet-gpu/blob/main/piet-wgsl/s...</a><p>[2]: <a href="https://github.com/linebender/kurbo/blob/euler/src/euler.rs#L630" rel="nofollow">https://github.com/linebender/kurbo/blob/euler/src/euler.rs#...</a>
If you like this, you'll love the book "Hacker's Delight": <a href="https://en.wikipedia.org/wiki/Hacker%27s_Delight" rel="nofollow">https://en.wikipedia.org/wiki/Hacker%27s_Delight</a>
Here are two more(most of these websites link to each other):<p><a href="http://aggregate.org/MAGIC/" rel="nofollow">http://aggregate.org/MAGIC/</a><p><a href="https://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html" rel="nofollow">https://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html</a><p>I think this trend of publishing bit twiddling tricks started when Dr. Dobb's Journal in it's early days published an article about various such tricks. If someone has a link to that article then please could you share it? I think the article's title was "Bit Magic".<p>Edit:<p>There were two DDJ articles:<p>"Binary Magic Numbers - Some Applications and Algorithms" by Edwin E. Freed in Volume 8, Number 4, April, 1983; and<p>"More on Binary Magic Numbers" by Dale Wilson from Volume 9, Number 3, March, 1984.
Great page. A few years ago I saw it posted here on HN and bookmarked it, and would play around with a few of the (simpler) examples every now and then.<p>Last year I was in an interview and something around writing a program to find out if an integer is a power of 2 came up. I remembered the example from the doc above and used that (you basically AND your integer with itself minus one, which makes sense because any power of 2 is going to be 1 followed by some zeroes...see below). I got the job!<p><pre><code> 10000
& 1111
______
1</code></pre>
For all interested in the topic , there's a renowned classic of a cookbook: "Matters Computational" by Jörg Arndt.<p>Available freely: <a href="http://www.jjj.de/fxt/#fxtbook" rel="nofollow">http://www.jjj.de/fxt/#fxtbook</a>
In the game of Connect-4, bit twiddling allows amazing efficiency in board representation, board hashing, and win detection [1].<p>[1] <a href="https://github.com/denkspuren/BitboardC4/blob/master/BitboardDesign.md" rel="nofollow">https://github.com/denkspuren/BitboardC4/blob/master/Bitboar...</a>