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.
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.
Pretty cool that they seemed to have come up with the idea on their own, but they're definitely not the first: https://graphics.stanford.edu/~seander/bithacks.html#ZerosOn...
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.
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.
This is a good illustration of what competent SIMD code requires.
Might be useful on a GPU or something I guess?