Date:	Tue, 17 Aug 1999 02:13:49 +0700
From:	Batchex <thedark1 AT Phreaker DOT net>
X-Mailer:	The Bat! (v1.32) S/N E34104EF
X-Priority:	3 (Normal)
Message-ID:	<792.990817@Phreaker.net>
To:	Davin McCall <djgpp AT delorie DOT com>
Subject:	Re[2]: Bit counting?
In-reply-To:	<37b4e020.2582291@newsserver.cc.monash.edu.au>
References:	<37b4e020 DOT 2582291 AT newsserver DOT cc DOT monash DOT edu DOT au>
Mime-Version:	1.0
Reply-To:	djgpp AT delorie DOT com
X-Mailing-List:	djgpp AT delorie DOT com
X-Unsubscribes-To:	listserv AT delorie DOT com

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 -