#include <inttypes.h>

/* Cribbed from http://wiki.cs.pdx.edu/forge/popcount.html */
static char popcount_table_8[256] = {
  /*0*/ 0,
  /*1*/ 1,
  /*2*/ 1,
  /*3*/ 2,
  /*4*/ 1,
  /*5*/ 2,
  /*6*/ 2,
  /*7*/ 3,
  /*8*/ 1,
  /*9*/ 2,
  /*10*/ 2,
  /*11*/ 3,
  /*12*/ 2,
  /*13*/ 3,
  /*14*/ 3,
  /*15*/ 4,
  /*16*/ 1,
  /*17*/ 2,
  /*18*/ 2,
  /*19*/ 3,
  /*20*/ 2,
  /*21*/ 3,
  /*22*/ 3,
  /*23*/ 4,
  /*24*/ 2,
  /*25*/ 3,
  /*26*/ 3,
  /*27*/ 4,
  /*28*/ 3,
  /*29*/ 4,
  /*30*/ 4,
  /*31*/ 5,
  /*32*/ 1,
  /*33*/ 2,
  /*34*/ 2,
  /*35*/ 3,
  /*36*/ 2,
  /*37*/ 3,
  /*38*/ 3,
  /*39*/ 4,
  /*40*/ 2,
  /*41*/ 3,
  /*42*/ 3,
  /*43*/ 4,
  /*44*/ 3,
  /*45*/ 4,
  /*46*/ 4,
  /*47*/ 5,
  /*48*/ 2,
  /*49*/ 3,
  /*50*/ 3,
  /*51*/ 4,
  /*52*/ 3,
  /*53*/ 4,
  /*54*/ 4,
  /*55*/ 5,
  /*56*/ 3,
  /*57*/ 4,
  /*58*/ 4,
  /*59*/ 5,
  /*60*/ 4,
  /*61*/ 5,
  /*62*/ 5,
  /*63*/ 6,
  /*64*/ 1,
  /*65*/ 2,
  /*66*/ 2,
  /*67*/ 3,
  /*68*/ 2,
  /*69*/ 3,
  /*70*/ 3,
  /*71*/ 4,
  /*72*/ 2,
  /*73*/ 3,
  /*74*/ 3,
  /*75*/ 4,
  /*76*/ 3,
  /*77*/ 4,
  /*78*/ 4,
  /*79*/ 5,
  /*80*/ 2,
  /*81*/ 3,
  /*82*/ 3,
  /*83*/ 4,
  /*84*/ 3,
  /*85*/ 4,
  /*86*/ 4,
  /*87*/ 5,
  /*88*/ 3,
  /*89*/ 4,
  /*90*/ 4,
  /*91*/ 5,
  /*92*/ 4,
  /*93*/ 5,
  /*94*/ 5,
  /*95*/ 6,
  /*96*/ 2,
  /*97*/ 3,
  /*98*/ 3,
  /*99*/ 4,
  /*100*/ 3,
  /*101*/ 4,
  /*102*/ 4,
  /*103*/ 5,
  /*104*/ 3,
  /*105*/ 4,
  /*106*/ 4,
  /*107*/ 5,
  /*108*/ 4,
  /*109*/ 5,
  /*110*/ 5,
  /*111*/ 6,
  /*112*/ 3,
  /*113*/ 4,
  /*114*/ 4,
  /*115*/ 5,
  /*116*/ 4,
  /*117*/ 5,
  /*118*/ 5,
  /*119*/ 6,
  /*120*/ 4,
  /*121*/ 5,
  /*122*/ 5,
  /*123*/ 6,
  /*124*/ 5,
  /*125*/ 6,
  /*126*/ 6,
  /*127*/ 7,
  /*128*/ 1,
  /*129*/ 2,
  /*130*/ 2,
  /*131*/ 3,
  /*132*/ 2,
  /*133*/ 3,
  /*134*/ 3,
  /*135*/ 4,
  /*136*/ 2,
  /*137*/ 3,
  /*138*/ 3,
  /*139*/ 4,
  /*140*/ 3,
  /*141*/ 4,
  /*142*/ 4,
  /*143*/ 5,
  /*144*/ 2,
  /*145*/ 3,
  /*146*/ 3,
  /*147*/ 4,
  /*148*/ 3,
  /*149*/ 4,
  /*150*/ 4,
  /*151*/ 5,
  /*152*/ 3,
  /*153*/ 4,
  /*154*/ 4,
  /*155*/ 5,
  /*156*/ 4,
  /*157*/ 5,
  /*158*/ 5,
  /*159*/ 6,
  /*160*/ 2,
  /*161*/ 3,
  /*162*/ 3,
  /*163*/ 4,
  /*164*/ 3,
  /*165*/ 4,
  /*166*/ 4,
  /*167*/ 5,
  /*168*/ 3,
  /*169*/ 4,
  /*170*/ 4,
  /*171*/ 5,
  /*172*/ 4,
  /*173*/ 5,
  /*174*/ 5,
  /*175*/ 6,
  /*176*/ 3,
  /*177*/ 4,
  /*178*/ 4,
  /*179*/ 5,
  /*180*/ 4,
  /*181*/ 5,
  /*182*/ 5,
  /*183*/ 6,
  /*184*/ 4,
  /*185*/ 5,
  /*186*/ 5,
  /*187*/ 6,
  /*188*/ 5,
  /*189*/ 6,
  /*190*/ 6,
  /*191*/ 7,
  /*192*/ 2,
  /*193*/ 3,
  /*194*/ 3,
  /*195*/ 4,
  /*196*/ 3,
  /*197*/ 4,
  /*198*/ 4,
  /*199*/ 5,
  /*200*/ 3,
  /*201*/ 4,
  /*202*/ 4,
  /*203*/ 5,
  /*204*/ 4,
  /*205*/ 5,
  /*206*/ 5,
  /*207*/ 6,
  /*208*/ 3,
  /*209*/ 4,
  /*210*/ 4,
  /*211*/ 5,
  /*212*/ 4,
  /*213*/ 5,
  /*214*/ 5,
  /*215*/ 6,
  /*216*/ 4,
  /*217*/ 5,
  /*218*/ 5,
  /*219*/ 6,
  /*220*/ 5,
  /*221*/ 6,
  /*222*/ 6,
  /*223*/ 7,
  /*224*/ 3,
  /*225*/ 4,
  /*226*/ 4,
  /*227*/ 5,
  /*228*/ 4,
  /*229*/ 5,
  /*230*/ 5,
  /*231*/ 6,
  /*232*/ 4,
  /*233*/ 5,
  /*234*/ 5,
  /*235*/ 6,
  /*236*/ 5,
  /*237*/ 6,
  /*238*/ 6,
  /*239*/ 7,
  /*240*/ 4,
  /*241*/ 5,
  /*242*/ 5,
  /*243*/ 6,
  /*244*/ 5,
  /*245*/ 6,
  /*246*/ 6,
  /*247*/ 7,
  /*248*/ 5,
  /*249*/ 6,
  /*250*/ 6,
  /*251*/ 7,
  /*252*/ 6,
  /*253*/ 7,
  /*254*/ 7,
  /*255*/ 8,
};
/* Table-driven popcount, with 8-bit tables */
/* 6 ops plus 4 casts and 4 lookups, 0 long immediates, 4 stages */
inline uint32_t
popcount(uint32_t x)
{
    return popcount_table_8[(uint8_t)x] +
       popcount_table_8[(uint8_t)(x >> 8)] +
       popcount_table_8[(uint8_t)(x >> 16)] +
       popcount_table_8[(uint8_t)(x >> 24)];
}

/* TODO: Add a 16-bit variant */