Date: Tue, 17 Aug 1999 02:13:49 +0700 From: Batchex X-Mailer: The Bat! (v1.32) S/N E34104EF X-Priority: 3 (Normal) Message-ID: <792.990817@Phreaker.net> To: Davin McCall 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 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Reply-To: djgpp AT delorie DOT com X-Mailing-List: djgpp AT delorie DOT com X-Unsubscribes-To: listserv AT delorie DOT com Precedence: bulk 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