number of 1's in an integer

[junky_fellow]

Can anybody suggest me an efficient way of counting
no. of 1's in an integer (assume size of int=4)?
Note: no looping is allowed.

i agree this is a homework question. i tried a lot
but couldn't find any solution.
Any hints will be highly appreciated.

thanx a ton...

 

[Grumble]

Can anybody suggest me an efficient way of [...]

What is your definition of efficient?

Small execution time? Small code size? Small data size? Easy to read?

BTW, there is no need to assume how many bits there are in an int, you
can use sizeof(unsigned int) * CHAR_BIT

 

[Sean Kenwrick]

Can anybody suggest me an efficient way of counting
no. of 1's in an integer (assume size of int=4)?
Note: no looping is allowed.

i agree this is a homework question. i tried a lot
but couldn't find any solution.
Any hints will be highly appreciated.

thanx a ton...

Create a lookup table with 256 entries where each entry holds the number of
bits for each byte value (from 0 - 255):

/* Notice the recursive series pattern... */
/* Check out the first four entries, then every other entry, then every
fourth entry (see the pattern.?.) */
/* Another solution could make use of this pattern....!!! */
int bits_in_a_byte[256]={0,1,1,2, 1,2,2,3, 1,2,2,3, 2,3,3,4, 1,2,2,3 ,
2,3,3,4, 2,3,3,4, 3,4,4,5.etc..};

The for each byte in you 4 byte int you can do a lookup on this table and
add all the results together.

You can use casting of pointers to get each byte of the int as follows:

long value;
char byte1, byte2, byte3, byte4;
char *p;

p=(char *) &value;
byte1= p[0];
byte2=p[1];
byte3=p[2];
byte4=p[3];

This makes some assumptions about the sizeof long etc but I hope you get the
general gist...

Sean

 

[Arjan Kenter]

Can anybody suggest me an efficient way of counting
no. of 1's in an integer (assume size of int=4)?
Note: no looping is allowed.

i agree this is a homework question. i tried a lot
but couldn't find any solution.
Any hints will be highly appreciated.

thanx a ton...

Since you say it's a homework question I won't give you the code
but suggest you use recursion to work around the looping bit. And
take care when you are going to shift your integer number: shifting
right signed ints is implementation defined. But if you get it right,
you don't even need to know (not to mention assume) the size of
your ints.

--
ir. H.J.H.N. Kenter ^^
Electronic Design & Tools oo ) Philips Research Labs
Building WAY 3.23 =x= \ (e-mail address removed)
Prof. Holstlaan 4 (WAY31) | \ tel. +31 40 27 45334
5656 AA Eindhoven /|__ \ tfx. +31 40 27 44626
The Netherlands (____)_/ http://www.kenter.demon.nl/

Famous last words: Segmentation Fault (core dumped)

 

[Grumble]

Create a lookup table with 256 entries where each entry holds
the number of bits for each byte value (from 0 - 255):

What if CHAR_BIT > 8 ?

<g>

 

[Francois Grieu]

Can anybody suggest me an efficient way of counting
no. of 1's in an integer (assume size of int=4)?

Two favorites:

int bitcount1 (unsigned long x)
{
int n = 0;
if (x) do ++n; while (x &= x-1);
return n;
}

/* assume unsigned long is 32 bits */
int bitcount2 (unsigned long x)
{
x -= ((x>>1)&013333333333)+((x>>2)&01111111111);
x = ((x>>3)+x)&030707070707;
x += x>>18;
return ((x>>12)+(x>>6)+x)&63;
}


François Grieu

 

[Sean Kenwrick]

What if CHAR_BIT > 8 ?

<g>

I did state in my original post that I made some assumptions and that this
was really just a concept for which the OP to build upon....

Sean

 

[CBFalconer]

Can anybody suggest me an efficient way of counting
no. of 1's in an integer (assume size of int=4)?
Note: no looping is allowed.

i agree this is a homework question. i tried a lot
but couldn't find any solution.

The integer N contains (1 + 1 + 1 + .... 1) == N ones. If this is
not what you want the problem is poorly stated, and you might with
to look at M Grieus posting.

Even if the actual meaning is "1 bits", the problem without
looping is foolish. Any solution requires further system
knowledge, such as CHAR_BIT. Also there is no need to assume
sizeof(int) == 4.

 

[Peter Nilsson]

Can anybody suggest me an efficient way of [...]

What is your definition of efficient?

Small execution time? Small code size? Small data size? Easy to read?

BTW, there is no need to assume how many bits there are in an int, you
can use sizeof(unsigned int) * CHAR_BIT

This is useful as an upper bound only. It is not guaranteed to be number of
sign and value bits in an int.

 

[junky_fellow]

Two favorites:

int bitcount1 (unsigned long x)
{
int n = 0;
if (x) do ++n; while (x &= x-1);
return n;
}

/* assume unsigned long is 32 bits */
int bitcount2 (unsigned long x)
{
x -= ((x>>1)&013333333333)+((x>>2)&01111111111);
x = ((x>>3)+x)&030707070707;
x += x>>18;
return ((x>>12)+(x>>6)+x)&63;
}


François Grieu

thanx a lot. The first one is really appreciable. However,the
logic of second one is still not clear.

 

[Mark McIntyre]

thanx a lot. The first one is really appreciable. However,the
logic of second one is still not clear.

rewrite the magic numbers in binary form, work through it for a couple of
numbers (also in binary form), and it will become clear.