/*
    Name:    ex20-9.c
    Purpose: Counts the number of 1 bits in a given unsigned char.
    Author:  The count_ones() functions were provided by W.W. Norton & Co.;
             the main() function and editorial comments by Bill Slough

    Notes:   count_ones_b() assumes the unsigned char data type is 8 bits long.
             It avoids a loop using a technique modeled on a binary tree.  To
             begin, adjacent pairs of bits are summed.  These four sums are then
             grouped into pairs and summed, leaving just two sums.  As a final
             step, those two are summed, giving the desired result.
 */

#include <stdio.h>
#include <limits.h>

int count_ones_a(unsigned char ch);
int count_ones_b(unsigned char ch);

int main(void) {
    unsigned char x;
    int i;

    /* exhaustively exercise the two bit count functions;
       complain if the functions disagree */
    for (i = 0; i <= UCHAR_MAX; i++) {
        x = (unsigned char) i;
        printf("%2.2x %d %d\n", x, count_ones_a(x), count_ones_b(x));
        if (count_ones_a(x) != count_ones_b(x))
            printf("FUNCTIONS DISAGREE!\n");
    }
    return 0;
}

/* Return the bit population of a given quantity */
int count_ones_a(unsigned char ch) {
    int ones = 0;
    while (ch != 0) {
        if (ch & 1)    /* is the least significant bit a one? */
            ones++;    /* yes; count it */
        ch >>= 1;      /* slide all bits one position right */
    }
    return ones;
}

/* Return the bit population of a given quantity; no looping! */
int count_ones_b(unsigned char ch) {
    ch = (ch & 0x55) + ((ch >> 1) & 0x55);   /* add adjacent pairs of bits (4 sums) */
    ch = (ch & 0x33) + ((ch >> 2) & 0x33);   /* then add those sums (2 sums) */
    ch = (ch & 0x0F) + ((ch >> 4) & 0x0F);   /* and finally add these (1 sum) */
    return ch;
}