Comment by NovaX | Hacker News Reader

Comment by NovaX | Hacker News Reader

Parent Full thread

I'm confused because isn't the bitwise version the inverted logic? If the LSB is 1 then it is an odd value, which should be zero, yet that is shifted to become 32. The original modulus is for an even value becoming 32. Shouldn't the original code or compiler invert it first? I'd expect

    let shift = ((~(i >> 5) & 1) << 5);

EDIT: The compiler uses "vpandn" with the conditional version and "vpand" with the bitwise version. The difference is it includes a bitwise logical NOT operation on the first source operand. It looks like the compiler and I are correct, the author's bitwise version is inverted, and the incorrect code was merged in the author's commit. Also, I think this could be reduced to just (~i & 32).

Even more interesting :).

From my days as a junior member of a team developing a compiler and run-time libraries, I really like the approach we took there: if the compiler generated sub-optimal code for a straightforward implementation, we'd aim to fix the compiler instead of tweaking the code. That's more difficult if you're not already maintaining your own compiler, of course. And algorithmic improvements are still valuable.

In this case, the optimiser already generated efficient code. Makes me wonder if any observed speed-up might have been because the incorrect code needed to do less work?

Thanks for pointing out. I have updated the post. I use the opposite shift since I store the binary in u64 with a different endian from the C++ version. Sorry for the confusion, my bad.

Endian indicates the byte order (MSB->LSB, LSB->MSB), but does not change the representation of a bit. The conditional logic says that an even result is 32 and an odd is 0 after a modulus two. In binary that (x & 1) is 0 for even and 1 for odd. When you shift by 5 that is 0 for even and 32 for odd, which is the opposite of the conditional logic. This is why I suggested using a binary NOT to flip the bits so that you get the same result as the original.

Reply on news.ycombinator.com