/*
 * PrecomputedBitCount.cpp
 * 
 * This code implements a precomputed bit counting algorithm. The algorithm uses 16-bit numbers,
 * and for a 32-bit integer, it adds the count of set bits in the first 16 bits with 
 * that of the second 16 bits. My testing (2007) of this indicates that this is the fastest
 * bit counting algorithm on my PC, which was built in 2006-2007.
 * 
 * Original code by Samuel Allen. Copyright 2008.
 * Dot Net Perls, http://dotnetperls.com/
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 * 
 * */

#include <stdio.h>

// Bit max is (0x1u << 16) which is 65536.
#define BIT_MAX 65536

// The bit counts of the first 65536 integers.
// I have found the unsigned char data type to be most efficient.
static unsigned char BITS_16[BIT_MAX]; 

static unsigned int get_bitcount(int n) {
  // Return the bit count of the first half of the parameter n,
  // added to the bit count of the second half.
  return BITS_16[n & 0xffffu] + BITS_16[(n >> 16) & 0xffffu];
}

int main() {
  // Calculate all the bit counts between 0 and 65535. 
  // Store all those values in the BITS_16 array.
  int i;
  for (i = 0; i < BIT_MAX; i++) {
    // Here we just use a simple algorithm that counts set bits.
    // This is slower, but yields the same results as the precomputed
    // algorithm. These numbers could be stored in memory rather than
    // precomputed on each execution.
    unsigned char count = 0;
    int n = i;
    while (n) {
      count++;
      n &= (n - 1);
    }
    BITS_16[i] = count;
  }
  
  // Some debugging/test code.
  printf("Bitcount of %d: %d\n", 3, get_bitcount(3));
  printf("Bitcount of %d: %d\n", 99999, get_bitcount(99999));
  printf("Bitcount of %d: %d\n", 1, get_bitcount(1));
  printf("Bitcount of %d: %d\n", 8, get_bitcount(8));
  printf("Bitcount of %d: %d\n", 30000, get_bitcount(30000));
  // Pause for input before returning.
  getchar();
  
  return 0;
}