3 ms·
The way I see it as working, is that the i'th bit in x is initially added to the i'th bit in diff, and subsequently subtracted from the (i-1)th, the (i-2)th, ..
by tromp 5y ago
The way I see it as working, is that the i'th bit in x is initially added to the i'th bit in diff, and subsequently subtracted from the (i-1)th, the (i-2)th, ... the 0th bit of diff.
So this bit of x, if set, contributes (1<<i) - (1<<(i-1) + 1<<(i-2) + ... + 1<<0) = 1 to diff altogether.
- goldenkey 5y agoNice analysis, it's basically just an alternating series that uses the inclusion exclusion principle. https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_pr...