ch2-bitcount (Count set bits in an integer)

Chapter_2     Exercise_2-8

Exercise_2-9

---

---

bitcount.c     K&R, p. 50         download

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

#define LENGTH 100 // bits

int bitcount(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("bitcount(%s): %d\n", bits, bitcount(x));

return 0;
}

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

for (b = 0; x != 0; x /= 2)
{ // x >>= 1 and x /= 2 are equivalent, but x /= 2 is safer
if (x & 01) // 01 is octal 1 (first bits are 0)
{b++;}
}

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 bitcount.c -o bitcount
./bitcount
Give a positive integer: 74
bitcount(1001010): 3

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

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

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

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

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

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

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

---

---

Chapter_2     Exercise_2-8

BACK_TO_TOP

Exercise_2-9