Mail Archives: djgpp/1999/08/16/22:02:48
Hi,
Saturday, August 14, 1999, 10:28:51 AM, you wrote:
DM> I don't think modulo is *that* slow, especially on newer processors.
DM> An alternative way to do it is (this is quite complicated)
DM> Mask of every 2nd bit and store the result (say in "masked1")
DM> Mask of every *other* bit and store the result (masked2)
DM> eg: (written in "not-exactly-C"):
DM> mask1 = value & 01010101010101b;
DM> mask2 = value & 10101010101010b;
DM> Then shift mask2 right one:
DM> mask2 >>= 1;
DM> Now, The total number of bits in mask1 and mask2 is equal to the total
DM> number of bits in value. More importantly, mask1 and mask2 can each be
DM> seen as a sequence of two bit numbers (MSB 0) whose total is the
DM> number of set bits. Now if we do:
DM> tempvalue = mask1 + mask2;
DM> We get tempvalue, a single variable containing a sequence of two bit
DM> numbers, the total of which is the total number of bits in value. On
DM> this value we use the same method with a slightly different mask:
DM> mask1 = tempvalue & 0011001100110011b;
DM> mask2 = (tempvalue & 1100110011001100b) >> 2;
DM> Now mask1 and mask2 each contain a sequence of four bit numbers (two
DM> MSBs 0) whose total value is the number of bits set in value. In the
DM> same manner as before:
DM> tempvalue = mask1 + mask2;
DM> Now, tempvalue contains a sequence of four bit numbers whose total
DM> value is the number of bits set in value.
DM> The process can be repeated to get a sequence of 8 bit values, and
DM> continued until tempvalue contains a sequence of N-bit values where N
DM> is the number of bits in value. In this case, tempvalue contains only
DM> one number: the total number of bits in value.
DM> Davin.
I'm curious about this approach. I've tested this approach
(theoretically) with some values.
2 bit sequemce:
value = 7
mask1 = 0000000000000111 & 0101010101010101 = 5
mask2 = 0000000000000111 & 1010101010101010 = 2
mask2 >>=1 = 1
tempvalue = mask1 + mask2 = 5 + 1 = 6
4 bit sequence:
value = 7
mask1 = 0000000000000111 & 0011001100110011 = 3
mask2 = 0000000000000111 & 1100110011001100 = 4
mask2 >>= 2 = 1
tempvalue = mask1 + mask2 = 3 + 1 = 4
value = 192
mask1 = 0000000011000000 & 0011001100110011 = 0
mask2 = 0000000011000000 & 1100110011001100 = 192
mask2 >>= 2 = 48
tempvalue = mask1 + mask2 = 0 + 48 = 48
8 bit sequence:
value = 192
mask1 = 0000000011000000 & 0000111100001111 = 0
mask2 = 0000000011000000 & 1111000011110000 = 192
mask2 >>= 3 = 24
tempvalue = mask1 + mask2 = 0 + 24 = 24
I understand that the initial question is how to count how many bits
in a data value that is set (1). From the above tests, none that
reflect this. Am I missing something here?
Batchex
mailto:thedark1 AT Phreaker DOT net
- Raw text -