How to design the new bitcount function?

[jacklisp]

When I do the exercises I met a question:
In a two's complement number system, x &= (x-1) deletes the rightmost
1-bit in x. Explain why. Use this observation to write a faster
version of bitcount.
The old version of bitcount function as follows:
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
I had consider for a long time still fetch the point,
how can I re-write the "new & faster" bitcount function?
Any suggestion?
Thanks.

[Nick Keighley]

On 7 Nov, 14:47, "[e-mail]" <[e-mail]:

When I do the exercises I met a question:
In a two's complement number system, x &= (x-1) deletes the rightmost
1-bit in x. Explain why. Use this observation to write a faster
version of bitcount.
The old version of bitcount function as follows:
/* bitcount: *count 1 bits in x */
* *int bitcount(unsigned x)
* *{
* * * *int b;
* * * *for (b = 0; x != 0; x >>= 1)
* * * * * *if (x & 01)
* * * * * * * *b++;
* * * *return b;
* *}
I had consider for a long time still fetch the point,
how can I re-write the "new & faster" bitcount function?
Any suggestion?

x &= (x-1) deletes a bit. How many times could you apply
it before there were no bits left?

--
Nick Keighley

[Eric Sosman]

ja******@gmail.com wrote:

When I do the exercises I met a question:
In a two's complement number system, x &= (x-1) deletes the rightmost
1-bit in x. Explain why. Use this observation to write a faster
version of bitcount.
The old version of bitcount function as follows:
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
I had consider for a long time still fetch the point,
how can I re-write the "new & faster" bitcount function?
Any suggestion?

If there are ninety-nine bottles of beer on the wall, how
many times can you take one down and pass it around before you
find yourself confronting an empty wall?

--
Er*********@sun.com

[J. Cochran]

In article <74**********************************@o4g2000pra.g ooglegroups.com>,
ja******@gmail.com <ja******@gmail.comwrote:

>When I do the exercises I met a question:
In a two's complement number system, x &= (x-1) deletes the rightmost
1-bit in x. Explain why. Use this observation to write a faster
version of bitcount.
The old version of bitcount function as follows:
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
I had consider for a long time still fetch the point,
how can I re-write the "new & faster" bitcount function?
Any suggestion?
Thanks.

Think about it, you have a function that when presented with a non-zero
value will *always* remove *exactly* 1 bit from a number regardless of
where in the number that bit is.

For the sample function you have above, it will loop 32 times for the
value 0x80000000, where using the "turn off last bit in number" will only
loop once.
--
The Venture Co: Crisell (70 Gnome Warlock), Flolyna (64 Human Warrior),
Alassaria (64 Druid), Being (64 Dwarf Hunter), Lory (64 Human Paladin),
Trinalie (64 Gnome Mage), Kincann (65 Dwarf Rogue),
Mysa (66 Draenei Priest), Kathelone (64 Shaman)

[jacklisp]

On Nov 7, 11:28 pm, Eric Sosman <[e-mail]:

[e-mail] wrote:

When I do the exercises I met a question:
In a two's complement number system, x &= (x-1) deletes the rightmost
1-bit in x. Explain why. Use this observation to write a faster
version of bitcount.
The old version of bitcount function as follows:
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
I had consider for a long time still fetch the point,
how can I re-write the "new & faster" bitcount function?
Any suggestion?

If there are ninety-nine bottles of beer on the wall, how
many times can you take one down and pass it around before you
find yourself confronting an empty wall?

--
[e-mail]

int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x &= (x-1))
b++;
return b;
}
Thanks, I got understand...

[Eric Sosman]

ja******@gmail.com wrote:

On Nov 7, 11:28 pm, Eric Sosman <[e-mail]:

>[e-mail] wrote:

>>When I do the exercises I met a question:
In a two's complement number system, x &= (x-1) deletes the rightmost
1-bit in x. Explain why. Use this observation to write a faster
version of bitcount.
The old version of bitcount function as follows:
/* bitcount: count 1 bits in x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
I had consider for a long time still fetch the point,
how can I re-write the "new & faster" bitcount function?
Any suggestion?

If there are ninety-nine bottles of beer on the wall, how
many times can you take one down and pass it around before you
find yourself confronting an empty wall?

int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x &= (x-1))
b++;
return b;
}
Thanks, I got understand...

Bit-counting is one of those problems that offers many dissimilar
solutions. Here's another whose study you might find educational; it
assumes a 32-bit `unsigned int' but could be adapted for other sizes:

int bitcount(unsigned int x) {
x = ((x >1) & 0x55555555) + (x & 0x55555555);
x = ((x >2) & 0x33333333) + (x & 0x33333333);
x = ((x >4) & 0x0F0F0F0F) + (x & 0x0F0F0F0F);
x = ((x >8) & 0x00FF00FF) + (x & 0x00FF00FF);
x = (x >16) + (x & 0x0000FFFF);
return x;
}

This one looks utterly baffling at first, but is really quite simple
once you understand it. Perhaps the best path to understanding is
to work through a few values with pencil and paper, writing down each
intermediate result as it's developed. Write them in hexadecimal;
it'll be clearer and easier.

Considering the many ways to count bits, it's too bad there's
not more demand for bit counts!

--
Er*********@sun.com

[Phil Carmody]

Eric Sosman <Er*********@sun.comwrites:

Bit-counting is one of those problems that offers many dissimilar
solutions. Here's another whose study you might find educational; it
assumes a 32-bit `unsigned int' but could be adapted for other sizes:

int bitcount(unsigned int x) {
x = ((x >1) & 0x55555555) + (x & 0x55555555);
x = ((x >2) & 0x33333333) + (x & 0x33333333);
x = ((x >4) & 0x0F0F0F0F) + (x & 0x0F0F0F0F);
x = ((x >8) & 0x00FF00FF) + (x & 0x00FF00FF);
x = (x >16) + (x & 0x0000FFFF);
return x;
}

This one looks utterly baffling at first,

Absolutely. Far to many '&'s.

Phil
--
We must respect the other fellow's religion, but only in the sense and to the
extent that we respect his theory that his wife is beautiful and his children
smart. -- Henry Louis Mencken (1880-1956), American editor and critic

[user923005]

On Nov 7, 6:47*am, "[e-mail]" <[e-mail]:

When I do the exercises I met a question:
In a two's complement number system, x &= (x-1) deletes the rightmost
1-bit in x. Explain why. Use this observation to write a faster
version of bitcount.
The old version of bitcount function as follows:
/* bitcount: *count 1 bits in x */
* *int bitcount(unsigned x)
* *{
* * * *int b;
* * * *for (b = 0; x != 0; x >>= 1)
* * * * * *if (x & 01)
* * * * * * * *b++;
* * * *return b;
* *}
I had consider for a long time still fetch the point,
how can I re-write the "new & faster" bitcount function?

https://chessprogramming.wikispaces....pulation+Count

[Nate Eldredge]

user923005 <dc*****@connx.comwrites:

On Nov 7, 6:47*am, "[e-mail]" <[e-mail]:

>When I do the exercises I met a question:
In a two's complement number system, x &= (x-1) deletes the rightmost
1-bit in x. Explain why. Use this observation to write a faster
version of bitcount.
The old version of bitcount function as follows:
/* bitcount: *count 1 bits in x */
* *int bitcount(unsigned x)
* *{
* * * *int b;
* * * *for (b = 0; x != 0; x >>= 1)
* * * * * *if (x & 01)
* * * * * * * *b++;
* * * *return b;
* *}
I had consider for a long time still fetch the point,
how can I re-write the "new & faster" bitcount function?

https://chessprogramming.wikispaces....pulation+Count

Not really addressing the question, but for people who actually need to
use a popcount function, I'll mention that GCC provides a function

int __builtin_popcount(unsigned);

which ought to compile into some optimized assembly. There are also

int __builtin_popcountl(unsigned long);
int __builtin_popcountll(unsigned long long);

So you might do

#ifdef __GCC__
#define popcount __builtin_popcount
#else
int popcount(unsigned) { ... }
#endif

[Hallvard B Furuseth]

Eric Sosman writes:

Considering the many ways to count bits, it's too bad there's
not more demand for bit counts!

Yeah, half of the fun little C hacks are nearly useless. We oughta
complain to Kernighan & Ritchie.

Since you gave a 32-bit variant, here is another one. I wonder how
many compilers handle a megabyte-sized preprocessor expansion?

static const unsigned char bits[] = {
#define B3(n) n,n+1,n+1,n+2, n+1,n+2,n+2,n+3
#define B5(n) B3(n), B3(n+1), B3(n+1), B3(n+2)
#define B7(n) B5(n), B5(n+1), B5(n+1), B5(n+2)
#define B9(n) B7(n), B7(n+1), B7(n+1), B7(n+2)
#define B11(n) B9(n), B9(n+1), B9(n+1), B9(n+2)
#define B13(n) B11(n),B11(n+1),B11(n+1),B11(n+2)
B13(0),B13(1),B13(1),B13(2), B13(1),B13(2),B13(2),B13(3)
};
int bitcount(unsigned x) { return bits[x & 0xFFFFu] + bits[x >16]; }

:-)

--
Hallvard

[Nate Eldredge]

Hallvard B Furuseth <h.**********@usit.uio.nowrites:

Eric Sosman writes:

> Considering the many ways to count bits, it's too bad there's
not more demand for bit counts!

Yeah, half of the fun little C hacks are nearly useless. We oughta
complain to Kernighan & Ritchie.

Since you gave a 32-bit variant, here is another one. I wonder how
many compilers handle a megabyte-sized preprocessor expansion?

All the ones I tried did just fine, and compiled this in a few seconds.
Not much of a challenge, compared to, say,
http://www0.us.ioccc.org/1995/vanschnitz.c .

Very cute, though.

static const unsigned char bits[] = {
#define B3(n) n,n+1,n+1,n+2, n+1,n+2,n+2,n+3
#define B5(n) B3(n), B3(n+1), B3(n+1), B3(n+2)
#define B7(n) B5(n), B5(n+1), B5(n+1), B5(n+2)
#define B9(n) B7(n), B7(n+1), B7(n+1), B7(n+2)
#define B11(n) B9(n), B9(n+1), B9(n+1), B9(n+2)
#define B13(n) B11(n),B11(n+1),B11(n+1),B11(n+2)
B13(0),B13(1),B13(1),B13(2), B13(1),B13(2),B13(2),B13(3)
};
int bitcount(unsigned x) { return bits[x & 0xFFFFu] + bits[x >16]; }

:-)

--
Hallvard

[Flash Gordon]

Hallvard B Furuseth wrote, On 08/11/08 21:54:

Eric Sosman writes:

> Considering the many ways to count bits, it's too bad there's
not more demand for bit counts!

Yeah, half of the fun little C hacks are nearly useless. We oughta
complain to Kernighan & Ritchie.

Since you gave a 32-bit variant, here is another one. I wonder how
many compilers handle a megabyte-sized preprocessor expansion?

static const unsigned char bits[] = {
#define B3(n) n,n+1,n+1,n+2, n+1,n+2,n+2,n+3

Surely the pattern would be better if you started

#define B1(n) n, n+1
#define B3(n) B1(n), B1(n+1), B1(n+1), B1(n+2)

#define B5(n) B3(n), B3(n+1), B3(n+1), B3(n+2)
#define B7(n) B5(n), B5(n+1), B5(n+1), B5(n+2)
#define B9(n) B7(n), B7(n+1), B7(n+1), B7(n+2)
#define B11(n) B9(n), B9(n+1), B9(n+1), B9(n+2)
#define B13(n) B11(n),B11(n+1),B11(n+1),B11(n+2)

Then ended
#define B15(n) B13(n),B13(n+1),B13(n+1),B13(n+2)
B15(0),B15(1)

B13(0),B13(1),B13(1),B13(2), B13(1),B13(2),B13(2),B13(3)
};
int bitcount(unsigned x) { return bits[x & 0xFFFFu] + bits[x >16]; }

:-)

Mind you, for more flexibility use this program to generate your
bit-count macros. Something like this...

#include <stdio.h>
#include <stdlib.h>

int main(int argc,char *argv[])
{
if (argc != 2) {
fputs("Please supply exactly one argument"
" which is the number of bits\n",stderr);
return EXIT_FAILURE;
}
else {
int bits = strtod(argv[1],NULL);
if (bits < 1) {
fputs("Oi, that argument is meant"
" to be a number of bits!\n",stderr);
return EXIT_FAILURE;
}
else if (bits==1)
puts("const unsigned char bitcount[] = { 0, 1 };");
else {
int i;
printf("#define B1(n) n,n+1\n");
for (i=1; i<bits-1; i++)
printf("#define B%0d(n) B%0d(n), B%0d(n+1)\n",i+1,i,i);
printf("const unsigned char bitcount[] ="
" { B%0d(0), B%0d(1) };\n",i,i);
}
return EXIT_SUCCESS;
}
}

Capture the output from a valid number to a file and compile it :-)

I might let you know if gcc manages it for 32 bits...
--
Flash Gordon
If spamming me sent it to sm**@spam.causeway.com
If emailing me use my reply-to address
See the comp.lang.c Wiki hosted by me at http://clc-wiki.net/

[Nate Eldredge]

Flash Gordon <sm**@spam.causeway.comwrites:

[clever macros that generate an array of bitcounts]

Capture the output from a valid number to a file and compile it :-)

I might let you know if gcc manages it for 32 bits...

Good luck! Doing some extrapolations on my machine, you'll need about
1.2 TB of memory.

[Flash Gordon]

Nate Eldredge wrote, On 08/11/08 23:15:

Flash Gordon <sm**@spam.causeway.comwrites:

[clever macros that generate an array of bitcounts]

>Capture the output from a valid number to a file and compile it :-)

I might let you know if gcc manages it for 32 bits...

Good luck! Doing some extrapolations on my machine, you'll need about
1.2 TB of memory.

It took a while, bit it did eventually fail with an error complaining it
could not allocate any more virtual memory :-)
--
Flash Gordon
If spamming me sent it to sm**@spam.causeway.com
If emailing me use my reply-to address
See the comp.lang.c Wiki hosted by me at http://clc-wiki.net/