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