3 ms·
And indeed, clang is able to do it for unsigned, too: https://godbolt.org/z/36r1Maq7b https://godbolt.org/z/36r1Maq7b gcc doesn't seem to implement this optimi
by tpolzer 5y ago
And indeed, clang is able to do it for unsigned, too: https://godbolt.org/z/36r1Maq7b 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).
- CJefferson 5y agoDidn'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'.
- hairtuq 5y agoYou 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.
- CJefferson 5y agoThat'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.
- deleted 5y ago[deleted]