Hacker News Reader

Comment by bsmith0 | Hacker News Reader

Yep my bad! I think flipping the order should work still though.

The two links in the article:

https://lemire.me/blog/2016/05/23/the-surprising-cleverness-...

And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine.

View on HN

Flipping the order works, except if the LSB on x is set.

https://godbolt.org/z/qdWhxMPsf

Note the run output under clang.

edit:

> And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine.

Thanks for teaching me something this morning. That's annoying.

I think the portable solution is std::popcount in C++ (or equivalent in Rust).

> or equivalent in Rust

https://doc.rust-lang.org/std/?search=count_ones

Internally Rust actually just staples LLVM's implementation into your code, via an intrinsic - but if that were ever to change the standard library count_ones() methods will do whatever happens instead so you should use that.

While it seems to be true gcc and clang don't recognize this pattern even when implemented correctly, your program becomes an infinite loop if the highest bit is set (negative), because 'i' will never become 0.

Example with int8_t:

  int8_t i = -127; // 0b10000001
  i >>= 1; // 0b11000000
  i >>= 1; // 0b11100000
  i >>= 1; // 0b11110000
  i >>= 1; // 0b11111000
  i >>= 1; // 0b11111100
  i >>= 1; // 0b11111110
  i >>= 1; // 0b11111111
  i >>= 1; // 0b11111111 ad infinitum

One needs to be careful when using >> (shift right) with signed integers.

So your program is not equivalent to popcount.

Reply on news.ycombinator.com