count number of ones in a given integer using only << >> + | & ^ ~ ! =

Question

How to write a C program using only << >> + | & ^ ~ ! =
That counts the number of ones in a given integer?

Answer 1

Have a look at the Bit Twiddling hacks from Stanford. Here are some choices for your problem:

The naïve Approach

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

for (c = 0; v; v >>= 1)
{
  c += v & 1;
}

With a Lookup Table

static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// Option 1:
c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] + 
    BitsSetTable256[p[3]];


// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

Brian W. Kernighan's Approach

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

There are some more algorithms, read the linked page for details.

Answer 2

It is impossible to do this using only << >> + | & ^ ~ ! =. You need some other punctuation such as {, }, (, ) and ;, and you need some letters too.

Here is a solution without digits:

int bc(unsigned int n){int c=!&n;while(n){c++;n&=n+~!&n;}return c;}

It uses only the operators mentioned, but only works on 2's complement architectures.

If you cannot use if, for nor while statements, the parallel sum works this way:

int bitcount32(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);
    return (x >> 16) + (x & 0x0000ffff);
}

This function works for 32 bit ints, but can be modified to handle 16 or 64 bit ints. There are more compact solutions and possibly more efficient ones depending on your actual CPU performance here: How to count the number of set bits in a 32-bit integer?