Counting bits

"Timothy L. Nali" <tn0s+@andrew.cmu.edu>:
> > Eli Brandt@jarthur.cs.hm 
> > int byte_ones(int a)
> > // hope this is correct...
> > {
> >         a = (a & 0x55) + (a & 0xAA)/2;          // 0x55 == 01010101b
> [...]
> Note that some compilers might not be smart enough to use logical shift
> ops and instead use expensive division ops.  Just to be safe...
> 
> int byte_ones(int a)
>          a = (a & 0x55) + ((a & 0xAA) << 1);          // 0x55 == 01010101b
                                    ^^^^^^^^^
Let me guess: you're one of the lucky users of the RBO (Reverse Bit Order)
SuperDecryptor from the NSA, where the LSB is the one at the extreme left?

Or did you mean ((a & 0xAA) >> 1)   ;)

My personal preference for byte operands is unsigned char - this ensures
that right shifts are not sign-extended by the most brain dead compiler, and
might use only one byte for the parameter.

-----------------------------------------------------------------------------
Rishab Aiyer Ghosh             "Clean the air! clean the sky! wash the wind!
rishab@dxm.ernet.in                   take stone from stone and wash them..."
Voice/Fax/Data +91 11 6853410  
Voicemail +91 11 3760335                 H 34C Saket, New Delhi 110017, INDIA

Why bother when you can simply do an eight line function?

int bitcount(char b)
{
register int retval=0;

 if (a & 1) retval++;
 if (a & 2) retval++;
 if (a & 4) retval++;
 if (a & 8) retval++;
 if (a & 16) retval++;
 if (a & 32) retval++;
 if (a & 64) retval++;
 if (a & 128) retval++; 

return retval;
}

This function, (if you have a decent compiler) will be turned into about 32
instructions at most.  IE:
  MOV BL,00
  MOV AL,value_of_a_wherever_that_may_be_in_the_stack
  AND AL,01
  JZ @+2_instructions
  INC BL
  AND AL,02
  JZ @+2_instructions...
  ad compiler nausea.

Simple, no shifting, no adding, no dividing, and best of all, it's straight
forward, and you don't have the possibility of sneaking in bugs.  Whereas
the previous example is a one liner, and may be shorter, it will be far
harder for humans to understand. :-)


Just my two bits. ;^)

> Why bother when you can simply do an eight line function?
[ unrolled loop approach deleted ]

1. Speed.  For bytes it probably doesn't matter much, but it
will if you're operating on full words.

2. Why write straightforward code if you don't have to?  ;-)

   Eli   ebrandt@hmc.edu

-----BEGIN PGP SIGNED MESSAGE-----

In list.cypherpunks, rarachel@prism.poly.edu writes:

> 
> Why bother when you can simply do an eight line function?
> 
> int bitcount(char b)
> {
> register int retval=0;
> 
>  if (a & 1) retval++;
>  if (a & 2) retval++;
>  if (a & 4) retval++;
>  if (a & 8) retval++;
>  if (a & 16) retval++;
>  if (a & 32) retval++;
>  if (a & 64) retval++;
>  if (a & 128) retval++; 
> 
> return retval;
> }
> 
> This function, (if you have a decent compiler) will be turned into about 32
> instructions at most.

Just for entertainment value, I clipped your function and compiled it
with Turbo C++ 1.01 in default (ANSI C) mode.  Here's the .asm code
produced (comments and setup code edited for brevity)

_bitcount	proc	near
	push	bp
	mov	bp,sp
	push	si
	mov	dl,byte ptr [bp+4]
	xor	si,si
	test	dl,1
	je	short @1@74
	inc	si
@1@74:
	test	dl,2
	je	short @1@122
	inc	si
@1@122:
	test	dl,4
	je	short @1@170
	inc	si
@1@170:
	test	dl,8
	je	short @1@218
	inc	si
@1@218:
	test	dl,16
	je	short @1@266
	inc	si
@1@266:
	test	dl,32
	je	short @1@314
	inc	si
@1@314:
	test	dl,64
	je	short @1@362
	inc	si
@1@362:
	test	dl,128
	je	short @1@410
	inc	si
@1@410:
	mov	ax,si
	jmp	short @1@434
@1@434:
	pop	si
	pop	bp
	ret	
_bitcount	endp

Your estimate was a little short.  I count 35 instructions. :-)
- -- 
Roy M. Silvernail --  roy@sendai.cybrspc.mn.org will do just fine, thanks.
          "Does that not fit in with your plans?"
                      -- Mr Wiggen, of Ironside and Malone (Monty Python)
        PGP 2.3a public key available upon request (send yours)

-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQCVAwUBLht6nBvikii9febJAQELawP9GFgXQ8HMKoiIWgRDH6oLYxHfz8XMsKEN
I3BXCpqwe35ADBP6ah8vgEWfifOJMIlduR02u8RV/Zz4ROC0kRBrJPw/Gk7R3gd5
uoUlqUgjZQAmqNcBE84hTHqxnLmSKJJb3nygYVZ8fhA6Fhn0BJ/6hpRuAGazN3B0
SVznWIhxpmQ=
=tPEz
-----END PGP SIGNATURE-----