How to design the new bitcount function?

J

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.
 
N

Nick Keighley

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?
 
J

jacklisp

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...
 
P

Phil Carmody

Eric Sosman said:
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
 
U

user923005

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.com/Population+Count
 
N

Nate Eldredge

user923005 said:

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
 
H

Hallvard B Furuseth

Eric said:
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]; }

:)
 
N

Nate Eldredge

Hallvard B Furuseth said:
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]; }

:)
 
F

Flash Gordon

Hallvard B Furuseth wrote, On 08/11/08 21:54:
Eric said:
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...
 
N

Nate Eldredge

[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.
 
F

Flash Gordon

Nate Eldredge wrote, On 08/11/08 23:15:
[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 :)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top