##
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