Counting bits
Ajay Pal Singh
I need to count number of 1 and 0 bits in a 64, 32 and 8 bit words.
How can I do that?? Ideas would be appreciated.
Sean Walberg
while (mymask) {
if (mybyte & mymask) ones++ else zeroes++;
mymask = mymask << 1;
}
probably a quicker way than that though. (I'm assuming that mymask and
mybyte are the same type here)
Sean
Alexander Viro
Ajay Pal Singh <asi...@sybase.com> wrote:
>Folks,
>
>I need to count number of 1 and 0 bits in a 64, 32 and 8 bit words.
>How can I do that?? Ideas would be appreciated.
int count;
for(count=0;x;count++,x&=x-1)
;
That will count 1's. Works for positive numbers on any binary architecture
and for all numbers on 2-complement one (absolute majority now). On
1-complement it will give you interesting results for negative numbers, but
unless you are playing with UNIVAC it shouldn't be a problem. And UNIVAC
is 36-bit, so considering the sizes you are interested in...
--
"You're one of those condescending Unix computer users!"
"Here's a nickel, kid. Get yourself a better computer" - Dilbert.
Eric Levenez
> mymask=1;
> while (mymask) {
> if (mybyte & mymask) ones++ else zeroes++;
> mymask = mymask << 1;
> }
>
> probably a quicker way than that though. (I'm assuming that mymask and
> mybyte are the same type here)
>
> Sean
>
> <asi...@sybase.com> wrote:
>
> >Folks,
> >
> >I need to count number of 1 and 0 bits in a 64, 32 and 8 bit words.
> >How can I do that?? Ideas would be appreciated.
The fastest way is to have a precalculated array of 256 values for
all 8 bits words. Then you just use the 8 bits word as an index,
and sum all words.
--
--------------------------------------------------------------------
Éric Lévénez "Felix qui potuit rerum cognoscere causas"
mailto:lev...@club-internet.fr Publius Vergilius Maro,
http://perso.club-internet.fr/levenez Georgica, II-489
--------------------------------------------------------------------
"We are Microsoft. You will be assimilated. Resistance is futile."
Ken Pizzini
>I need to count number of 1 and 0 bits in a 64, 32 and 8 bit words.
>How can I do that?? Ideas would be appreciated.
There are several different ways, each with a corresponding
domain in which they are good, and a domain in which they
are not so good.
Here is a mildly obscure one, whose run time is determined by the number
of bits actually set in the input word (only works on 2's-complement
machines, but that is a fairly safe assumption these days):
int count_bits(u_int64_t word) {
int count=0;
/* note that on 2's-complement machines "w & (w-1)" is
* the same as "w" with the low-order bit cleared */
for (; word; word &= word-1)
++count;
return count;
}
And here is one whose run time is up to (bits_per_word/8) loop iterations:
int count_bits(u_int64_t word) {
static int bits_in_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,
1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5, 2,3,3,4, 3,4,4,5, 3,4,4,5, 4,5,5,6,
1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5, 2,3,3,4, 3,4,4,5, 3,4,4,5, 4,5,5,6,
2,3,3,4, 3,4,4,5, 3,4,4,5, 4,5,5,6, 3,4,4,5, 4,5,5,6, 4,5,5,6, 5,6,6,7,
1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5, 2,3,3,4, 3,4,4,5, 3,4,4,5, 4,5,5,6,
2,3,3,4, 3,4,4,5, 3,4,4,5, 4,5,5,6, 3,4,4,5, 4,5,5,6, 4,5,5,6, 5,6,6,7,
2,3,3,4, 3,4,4,5, 3,4,4,5, 4,5,5,6, 3,4,4,5, 4,5,5,6, 4,5,5,6, 5,6,6,7,
3,4,4,5, 4,5,5,6, 4,5,5,6, 5,6,6,7, 4,5,5,6, 5,6,6,7, 5,6,6,7, 6,7,7,8
};
int count=0;
for (; word; word>>=8)
count += bits_in_byte[word&0xff];
return count;
}
Note that you can pass an integer of any width (up to 64 bits)
to these functions; the compiler will automatically promote
the value to u_int64_t (assuming a prototype in scope), and
the functions won't waste time trying to count the high-order
zero bits.
--Ken Pizzini
Eric Levenez
>
> I need to count number of 1 and 0 bits in a 64, 32 and 8 bit words.
> How can I do that?? Ideas would be appreciated.
The fastest way to compute the number of 0 or 1 in
some bytes is to use a pre-compute array and you just
use each byte value as an offset in it
For example :
int compute_nb0(unsigned char *p, int n)
{
static const unsigned char table[] = {
8, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0,
};
int l = 0;
while (n--)
l += table[*p++];
return l;