On Sat, 2007-10-27 at 15:27 +0200, Christian "Eddie" Dost wrote: > The sparc64 popc works in O(lg(n))
No, it has a fix cost, whatever the operand is. It has another advantage: it does not need any intermediate variable, which is great when running on CISC host in the Qemu execution environmnent. > , the "optimized" code below work in > O(n). Yes. But it's false.... It shoudl be val &= val - 1 instead of val ^= val - 1... [...] I did tests on my PC, which will imho close the debate: the Sparc implementation is at least 50 % faster. I did generate 2 ^ 29 random numbers to achieve this test (and checked that the repartition was OK). -- J. Mayer <[EMAIL PROTECTED]> Never organized
