Prev: DMA programming
Next: Discussion: What is the best way to count all set bits in a LARGEunsigned char array(no memory limit)?
From: mike-yue on 28 Dec 2007 15:55
For example,

0x03 has 2 bits sets.
0x04 has 1 bits set.
0x07 has 3 bits sets.

Suppose we get a really big array, like

unsigned char ucarray[1024*1024*1024];

then what is the best way to count the number of all set bits(no
memory limit)?


To discuss it here because it was an interview question, and I didn't
find the best way. Only method I got was counting the set bits in one
element, and then jump to next element.

Here is a function to count set bits in one unsigned char:

int bits(unsigned char v) {
return (v==0)?0:bits1((unsigned char)v&(v-1))+1;
}

or:

int bits(unsigned char v) {
int count;
for(count = 0; v != 0; count++, v &= (v-1));
return count;
}

Two other supplementary methods may do helps:
1. using macro to replace the upper functions
2. copy the array content to another same memory size unsigned long
array, and count the set bits based on unsigned long instead of
unsigned char.

All the methods here base on array element, not a WHOLE memory block.
I am wondering if there is a way to operate a whole block of memory,
and count bit sets of the memory block.

Many thanks for your attention, and any opinions would be appreciated.

From: Ivan Novick on 28 Dec 2007 20:27
On Dec 28, 12:55 pm, mike-yue <needpass...(a)gmail.com> wrote:
> For example,
>
> 0x03 has 2 bits sets.
> 0x04 has 1 bits set.
> 0x07 has 3 bits sets.
>
> Suppose we get a really big array, like
>
> unsigned char ucarray[1024*1024*1024];
>
> then what is the best way to count the number of all set bits(no
> memory limit)?
>
If you haven't check this site yet, please do:
http://graphics.stanford.edu/~seander/bithacks.html

AFAIK its the best resource for bit manipulation algorithms (interview
questions) :)

Regards,
Ivan Novick
http://www.0x4849.net
From: Francis Glassborow on 29 Dec 2007 07:38
mike-yue wrote:
> For example,
>
> 0x03 has 2 bits sets.
> 0x04 has 1 bits set.
> 0x07 has 3 bits sets.
>
> Suppose we get a really big array, like
>
> unsigned char ucarray[1024*1024*1024];
>
> then what is the best way to count the number of all set bits(no
> memory limit)?
>
>
> To discuss it here because it was an interview question, and I didn't
> find the best way. Only method I got was counting the set bits in one
> element, and then jump to next element.
>
> Here is a function to count set bits in one unsigned char:
>
> int bits(unsigned char v) {
> return (v==0)?0:bits1((unsigned char)v&(v-1))+1;
> }
>
> or:
>
> int bits(unsigned char v) {
> int count;
> for(count = 0; v != 0; count++, v &= (v-1));
> return count;
> }
>
> Two other supplementary methods may do helps:
> 1. using macro to replace the upper functions
> 2. copy the array content to another same memory size unsigned long
> array, and count the set bits based on unsigned long instead of
> unsigned char.
>
> All the methods here base on array element, not a WHOLE memory block.
> I am wondering if there is a way to operate a whole block of memory,
> and count bit sets of the memory block.
>
> Many thanks for your attention, and any opinions would be appreciated.
>


Well my first thought is to create an array of 256 ints and populate it
with the required values:

int bitcounts[256] = {0, 1, 2, 1, 2, 2, 3 and so on

now I would use that as a lookup table, e.g.

long bitcount(int * source, size_t number){
long result(0);
for(size_t i(0); i != number; ++i) result += bitcounts[source[i]];
return result;
}
From: Richard Heathfield on 29 Dec 2007 07:58
Francis Glassborow said:

<snip>

> Well my first thought is to create an array of 256 ints and populate it
> with the required values:
>
> int bitcounts[256] = {0, 1, 2, 1, 2, 2, 3 and so on

UCHAR_MAX + 1, surely?

(One would of course write a program to generate such a table, rather than
compose it by hand.)

> now I would use that as a lookup table, e.g.
>
> long bitcount(int * source, size_t number){
> long result(0);
> for(size_t i(0); i != number; ++i) result += bitcounts[source[i]];
> return result;
> }

The OP actually said "unsigned char array", so I'm puzzled by int * source.

I'd have done it like this:

unsigned long bitcount(unsigned char *source, size_t number)
{
unsigned long result = 0;
while(number--)
{
result += bitcounts[*source++];
}
return result;
}

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
From: Ivan Novick on 29 Dec 2007 09:44
On Dec 29, 4:38 am, Francis Glassborow
<francis.glassbo...(a)btinternet.com> wrote:
> mike-yue wrote:
> > For example,
>
> > 0x03 has 2 bits sets.
> > 0x04 has 1 bits set.
> > 0x07 has 3 bits sets.
>
> > Suppose we get a really big array, like
>
> > unsigned char ucarray[1024*1024*1024];
>
> > then what is the best way to count the number of all set bits(no
> > memory limit)?
>
> > To discuss it here because it was an interview question, and I didn't
> > find the best way. Only method I got was counting the set bits in one
> > element, and then jump to next element.
>
> > Here is a function to count set bits in one unsigned char:
>
> > int bits(unsigned char v) {
> > return (v==0)?0:bits1((unsigned char)v&(v-1))+1;
> > }
>
> > or:
>
> > int bits(unsigned char v) {
> > int count;
> > for(count = 0; v != 0; count++, v &= (v-1));
> > return count;
> > }
>
> > Two other supplementary methods may do helps:
> > 1. using macro to replace the upper functions
> > 2. copy the array content to another same memory size unsigned long
> > array, and count the set bits based on unsigned long instead of
> > unsigned char.
>
> > All the methods here base on array element, not a WHOLE memory block.
> > I am wondering if there is a way to operate a whole block of memory,
> > and count bit sets of the memory block.
>
> > Many thanks for your attention, and any opinions would be appreciated.
>
> Well my first thought is to create an array of 256 ints and populate it
> with the required values:
>
> int bitcounts[256] = {0, 1, 2, 1, 2, 2, 3 and so on
>
> now I would use that as a lookup table, e.g.
>
> long bitcount(int * source, size_t number){
> long result(0);
> for(size_t i(0); i != number; ++i) result += bitcounts[source[i]];
> return result;
>
> }

Could you do it in half the time if your lookup table consisted of all
the combinations in 16 bits, and then you looped and checked 2 bytes
at a time?

int bitcounts[65536] = { ..... }

Regards,
Ivan Novick
http://www.0x4849.net

 |  Next  |  Last
Pages: 1 2
Prev: DMA programming
Next: Discussion: What is the best way to count all set bits in a LARGEunsigned char array(no memory limit)?