c - count number of ones in a given integer using only << >> + | & ^ ~ ! = -
this question has answer here:
how write c program using << >> + | & ^ ~ ! =
counts number of ones in given integer?
have @ bit twiddling hacks stanford. here choices problem:
the naïve approach
unsigned int v; // count number of bits set in v unsigned int c; // c accumulates total bits set in v (c = 0; v; v >>= 1) { c += v & 1; } with lookup table
static const unsigned char bitssettable256[256] = { # define b2(n) n, n+1, n+1, n+2 # define b4(n) b2(n), b2(n+1), b2(n+1), b2(n+2) # define b6(n) b4(n), b4(n+1), b4(n+1), b4(n+2) b6(0), b6(1), b6(1), b6(2) }; unsigned int v; // count number of bits set in 32-bit value v unsigned int c; // c total bits set in v // option 1: c = bitssettable256[v & 0xff] + bitssettable256[(v >> 8) & 0xff] + bitssettable256[(v >> 16) & 0xff] + bitssettable256[v >> 24]; // option 2: unsigned char * p = (unsigned char *) &v; c = bitssettable256[p[0]] + bitssettable256[p[1]] + bitssettable256[p[2]] + bitssettable256[p[3]]; // generate table algorithmically: bitssettable256[0] = 0; (int = 0; < 256; i++) { bitssettable256[i] = (i & 1) + bitssettable256[i / 2]; } brian w. kernighan's approach
unsigned int v; // count number of bits set in v unsigned int c; // c accumulates total bits set in v (c = 0; v; c++) { v &= v - 1; // clear least significant bit set } there more algorithms, read linked page details.
Comments
Post a Comment