Author: Dieter Buerssner
Date: 09:20:05 05/28/04
Go up one level in this thread
An example of 8 bits. Say all are set
eoeoeoeo
11111111
We see this bit pattern as 8 individual counters. We look at odd and even
counters individually by shifiting and masking:
11111111 & 01010101 = 01010101
(11111111 >> 1) & 01010101 = 01010101
---------
Add those together 10101010
This was the "0x55 stage"
Now we look at the result as 4 individual counters of width 2 bits, and again
look at odd and even 2-bit counters seperately:
10101010 & 00110011 = 00100010
(10101010 >> 2) & 00110011 = 00100010
---------
Add those together 01000100
This was the "0x33 stage" The result we see as a pair of 4-bit counters. Maximum
is 0100 here, and we can add 2 together, without overflowing our 4 bit counters.
For example an 8-bit popcount could here just return (x&0xf)+x>>4, which would
yield 8 in the above example, just as expected. If we would have done 2 8-bit
pobcounts in parallel, we could add the 2 bytes consisting of the 4-bit counters
now without risk of overflow. And of course similar, when we started with 2
32-bits words.
Cheers,
Dieter
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.