Hacker News Reader

And indeed, clang is able to do it for unsigned, too: https://godbolt.org/z/36r1Maq7b

gcc doesn't seem to implement this optimization at all.

Technically it should be possible for the <=n case, too: An infinite loop is undefined behavior, so the compiler is allowed to assume it doesn't happen. But I guess (for good reasons) compiler writers are reluctant to exploit that too heavily (or it's just about ordering of optimization passes).

View on HN

Didn't know clang can do it for unsigned, so it seems there really isn't anything here you can only do with UB.

EDIT: I had a quick look to see why the obvious equation ( n (n+1))/2 ) didn't just work. The only problem for large n is you need to do the 'n (n+1)' in a bigger type (it doesn't technically matter if the n*(n+1) overflows, you just need a bigger type), so when you divide by 2 you get the right value in the top-most byte of 'unsigned int'.

You don't necessarily need a wider type (which might be slower to work with), you can just calculate (n|1) * ((n+1)/2). Clang does something much more complicated, probably because for it is just a special case of some much more general optimization.

That's a neat trick! -- I was trying to figure out how to handle the fact I didn't know which of n and n+1 was even.

Reply on news.ycombinator.com