Exercise 2-9 (Fast bitcount)

Chapter_2     Exercise_2-8     bitcount

items     Exercise_2-10

---

---

Exercise 2-9     K&R, p. 51

Exercise 2-9. In a two's complement number system, x &= (x-1) deletes the rightmost bit in x. Explain why, Use this observation to write a faster version of bitcount().

fastbitcount.c         download

#include <stdio.h> // for printf(), scanf()

#define LENGTH 100 // bits

int fastbitcount(unsigned x); // count 1 bits in x
// reverse s[], knowing its length:
void reverse(char s[], int len);
// get the bits of x into bits[], return length of bits[] (no of bits):
int bitstring (char bits[], unsigned x);

int main()
{
char bits[LENGTH];
unsigned x;

printf("Give a positive integer: ");
scanf("%u", &x);

bitstring(bits,x);

printf("fastbitcount(%s): %d\n", bits, fastbitcount(x));

return 0;
}

int fastbitcount(unsigned x) // count set (to 1) bits in x
{
int b;

for (b = 0; x != 0; x &= (x-1))
{ // x != 0 means x has at least one bit of 1 (or else x == 0)
// if x is odd, the last bit of x is 1, so x-1 is x with last bit 0,
// then x = x & (x-1) is x with the last 1 bit removed (set to 0)
// if x is even, last bit of x is 0, but x != 0 means x has at least one bit of 1,
// then x-1 sets the last 1 bit of x to 0, while setting the last 0 bits of x to 1:
// 2 == 10, 2-1 == 1 == 01; 4 == 100, 4-1 == 3 == 011;
// 6 == 110, 6-1 == 5 == 101; 12 == 1100, 12-1 == 11 == 1011;
// in all these cases, x & (x-1) is x with the last 1 bit removed (set to 0)
b++; // at each iteration we remove exactly one bit of 1 from x
}

return b;
}
// reverse s[], knowing its length:
void reverse(char s[], int len)
{
int i = 0, j = len-1;
char temp;

while (i < j)
{
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
// get the bits of x into bits[], return length of bits[] (no of bits):
int bitstring (char bits[], unsigned x)
{
int i = 0;

if (x == 0)
{
bits[i++] = '0';
bits[i] = '\0';

return i;
}

while (x > 0)
{ // last bit gives the parity:
bits[i++] = '0' + x % 2; // 0 for even, 1 for odd
x /= 2; // x = x / 2; // lose last bit
}
bits[i] = '\0'; // end the string

reverse(bits, i);

return i;
}
/*
gcc fastbitcount.c -o fastbitcount
./fastbitcount
Give a positive integer: 74
fastbitcount(1001010): 3

./fastbitcount
Give a positive integer: -1
fastbitcount(11111111111111111111111111111111): 32

./fastbitcount
Give a positive integer: 4294967295 // UINT_MAX
fastbitcount(11111111111111111111111111111111): 32

./fastbitcount
Give a positive integer: -2
fastbitcount(11111111111111111111111111111110): 31

./fastbitcount
Give a positive integer: 4294967294
fastbitcount(11111111111111111111111111111110): 31

./fastbitcount
Give a positive integer: 0
fastbitcount(0): 0

./fastbitcount
Give a positive integer: 32767
fastbitcount(111111111111111): 15

./fastbitcount
Give a positive integer: 123
fastbitcount(1111011): 6
*/

Note:  fastbitcount() is faster than bitcount() because it has fewer iterations (see bitcount).
No. of iterations of bitcount(x): no of bits of x, including inner 0 bits, which is returned by bitstring(bits,x).
No. of iterations of fastbitcount(): no of 1 (set) bits of x.

---

---

Chapter_2     Exercise_2-8     bitcount

BACK_TO_TOP

items     Exercise_2-10