Using de Bruijn sequences for this purpose is very well known, I'm not claiming to have invented it, it'd be strange if I did, especially when the Wikipedia page directly references this bit trick.
But if you look closer, my algorithm is actually not de Bruijn. First, using de Bruijn with a 32-bit input requires a 32-element table, or even a 33-element one depending on the circumstances, while I make do with 16 elements (repeated twice because that's how AVX works). Second, the de Bruijn snippet multiplies the constant by `x & -x`, a number that has exactly one bit set, i.e. looks like `2^k`, so the multiplication is effectively a shift by `k`. But in my code, I have to use `~x & (x-1)` to reuse a calculation, which produces values of form `2^k - 1`, for which de Bruijn fails spectacularly: `c * (2^k - 1) = c * 2^k - c`, but this subtraction introduces carries, which affects the top 4 bits unpredictably. The magic number I found kinda sorta looks like de Bruijn, but truth be told I found it by brute-force. If anyone knows how to generate such numbers algorithmically, I'm all ears.
teo_zero 9 hours ago [-]
To be fair, the article contains 3 methods. The first one is original, the second one is the same algorithm you linked, and the third one is an evolution of it.
jandrewrogers 13 hours ago [-]
This is a good illustration of what competent SIMD code requires.
But if you look closer, my algorithm is actually not de Bruijn. First, using de Bruijn with a 32-bit input requires a 32-element table, or even a 33-element one depending on the circumstances, while I make do with 16 elements (repeated twice because that's how AVX works). Second, the de Bruijn snippet multiplies the constant by `x & -x`, a number that has exactly one bit set, i.e. looks like `2^k`, so the multiplication is effectively a shift by `k`. But in my code, I have to use `~x & (x-1)` to reuse a calculation, which produces values of form `2^k - 1`, for which de Bruijn fails spectacularly: `c * (2^k - 1) = c * 2^k - c`, but this subtraction introduces carries, which affects the top 4 bits unpredictably. The magic number I found kinda sorta looks like de Bruijn, but truth be told I found it by brute-force. If anyone knows how to generate such numbers algorithmically, I'm all ears.