I did something quite useless.
The value is repeatedly bitshifted, losing one digit and lowering the value of all the remaining digits
The lowest bit is used one time as 1 (total 1)
The second is used twice, as 2 and 1 (total 3)
The third is used three times, as 4 2 1 (total 7)
The fourth is used four times, as 8 4 2 1 (total 15)
… and so on
that sum (1 3 7 15 31 …) is a power of 2 minus 1
bitvalue n = 2 ^ (n + 1) - 1
where n=0 is the first bit
…except, may as well do it with bit shifting
bitvalue n = 2 `shiftL` n - 1
I can then create a list for how much each bit is worth
bitvalues = map bitvalue [0 ..]
which gets me this:
> take 15 bitvalues
[1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767]
If i then have the bits of some number
bits n = fromEnum <$> unfoldr next n
where next x = if x == 0 then Nothing else Just (testBit x 0, shiftR x 1)
> bits 4
[0,0,1]
> bits 1234897
[1,0,0,0,1,0,1,1,1,1,1,0,1,0,1,1,0,1,0,0,1]
I can zip that with how much they’re worth
> zip (bits 1234897) bitvalues
[(1,1),(0,3),(0,7),(0,15),(1,31),(0,63),(1,127),(1,255),(1,511),(1,1023),(1,2047),(0,4095),(1,8191),(0,16383),(1,32767),(1,65535),(0,131071),(1,262143),(0,524287),(0,1048575),(1,2097151)]
multiply each pair (1 -> keep, 0 -> drop)
> zipWith (*) (bits 1234897) bitvalues
[1,0,0,0,31,0,127,255,511,1023,2047,0,8191,0,32767,65535,0,262143,0,0,2097151]
and sum them
halvingSum n = sum $ zipWith (*) (bits n) bitvalues
…refactor a bit
halvingSum = sum . zipWith (*) bitvalues . bits
And all that is useless because it’s one iteration per bit which is the same number of iterations as one would get by repeatedly halving the value.
For manual computation I imagine this would be faster, but computers happen to be good at summing and halving large numbers and rather bad at looking at individual bits.
https://repl.it/repls/CylindricalUtilizedBlocks