News for hackers. Stuff that matters.

A comment on Counting set bits in an interesting way.

Re:Counting set bits in an interesting way by tromp on Saturday April 30, 2022 @08:13AM (#31215440)
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.

[ Parent | on HN ]
Re:Counting set bits in an interesting way by goldenkey on Saturday April 30, 2022 @08:22AM (#31215489)
Nice analysis, it's basically just an alternating series that uses the inclusion exclusion principle.

https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_pr...

[ Parent | on HN ]