[A+DS]

### Bits

Problem: Count the number of bits set to `1' in a word of length `w' bits, as quickly as possible. This can be done with loops, e.g. from 0 to w-1, in O(w)-time, but it can be done in O(log(w))-time which is much faster, e.g.

```        76543210 - columns
--------
input: `01101101' has 5 bits set to `1';  w=8.

stage1:

01101101  >> 1  = 00110110
& 01010101        & 01010101
--------          --------
= 01000101          00010100
|
|
01000101             |   NB. adding two one-bit #s gives one
+ 00010100  <-----------       two-bit #, (1+0),(0+1),(1+1),(1+0)
--==--==
= 01011001                   = 1,1,2,1 base4!
--==--==

stage2:

01011001  >> 2  = 00010110
& 00110011        & 00110011
--------          --------
00010001          00010010
|
|
00010001             |
+ 00010010 <------------
----====
00100011  NB. 2 (0010) bits set in cols 7-4, 3 (0011) in 3-0
----====  2,3 base16

stage 3 (i.e. stage log2(w)):

00100011  >> 4  = 00000010
& 00001111        & 00001111
--------          --------
00000011          00000010
|
|
00000011             |
+ 00000010 <------------
--------
00000101 = 5256 = 510, i.e. 5 bits were `1'
--------
```

So, w=8 --> 3 stages, w=16 --> 4 stages, w=32 --> 5 stages, etc.. Each stage involves a right-shift `>', two bit-wise ands `&', and an addition.

This is not `core' material for CSE2304; it just shows that apparently simple problems can have amazing solutions. I'm not sure where it comes from originally, it might be one of Bentley's books?
- L.A. 5/3/1999