4 ms·
The compiler could still sub in the equation for unsigned integers, the equation is (mostly) the same. Not discussed (that I can see), the real problem is the
by CJefferson 5y ago
The compiler could still sub in the equation for unsigned integers, the equation is (mostly) the same.
Not discussed (that I can see), the real problem is the loop variable -- because the loop ends with ' <= n', which means if n is the largest unsigned integer, this is an infinite loop. One easy thing UB is useful for is proving these types of loop terminate (as overflowing would be UB).
- tpolzer 5y agoAnd 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]
- deleted 5y ago[deleted]