Counting 'on' bits in a byte?

[John]

Trying to return the number of 'on' bits in a byte:
'a' = 01100001 = 3 on bits, etc...

I'm just adding a bit-wise AND ('&' against octal 1) to a counter called
'bits', then shifting my byte 1 bit to the right; do this 8 times.

This works, but I was curious if there's some more effective formula
without looping or recursion? That seems like an awful lot of code, but
I can't think of a better way.


int BitCount(char c)
{
int ctr;
int bits = 0;
for (ctr = 0; ctr < 8; ctr++) {
bits += c & 0001;
c >>= 1;
}
return (bits);
}

 

[Tom St Denis]

int BitCount(char c)
{
int ctr;
int bits = 0;
for (ctr = 0; ctr < 8; ctr++) {
bits += c & 0001;
c >>= 1;
}
return (bits);
}

Two things

1. Right shifting signed types == bad
2. Is this really the bottleneck in your application?

But if you know you're dealing with bytes and have the space just use
an 8x8 lookup table. Failing that here's a hint: BitCount(x&15) +
BitCount(x>>4) == BitCount(x) for 8-bit unsigned "x".

Tom

 

[Morris Dovey]

John (in [email protected]) said:

| Trying to return the number of 'on' bits in a byte:
| 'a' = 01100001 = 3 on bits, etc...
|
| I'm just adding a bit-wise AND ('&' against octal 1) to a counter
| called 'bits', then shifting my byte 1 bit to the right; do this 8
| times.
|
| This works, but I was curious if there's some more effective formula
| without looping or recursion? That seems like an awful lot of
| code, but I can't think of a better way.
|
| int BitCount(char c)
| {
| int ctr;
| int bits = 0;
| for (ctr = 0; ctr < 8; ctr++) {
| bits += c & 0001;
| c >>= 1;
| }
| return (bits);
| }

int BitCount(unsigned char c)
{ int bits = 0;
do bits += c & 1; while (c >>= 1);
return bits;
}

The fast, no-loop method would involve pre-storing counts in a
256-element array so that you could code:

int BitCount(unsigned char c)
{ static unsigned char count[] = { 0,1,1,2,1, /* .. */ ,8 };
return count[(unsigned char)c];
}

 

[Morris Dovey]

Morris Dovey (in [email protected]) said:

....ugly stuff. I meant to lose the cast. The compiler knows how to
handle the subscript.

| int BitCount(unsigned char c)
| { static unsigned char count[] = { 0,1,1,2,1, /* .. */ ,8 };
return count[c];
| }

 

[Tom St Denis]

int BitCount(unsigned char c)
{ int bits = 0;
do bits += c & 1; while (c >>= 1);
return bits;
}

bah

int bitcount(unsigned char c)
{
unsigned char s;
s = (c & 0x11);
s += ((c >> 1) & 0x11);
s += ((c >> 2) & 0x11);
s += ((c >> 3) & 0x11);
return (s&15) + (s>>4);
}

More fun . Can work in even more parallel on bigger words.

int bitcount(unsigned c)
{
unsigned s;
s = (c & 0x1111);
s += ((c >> 1) & 0x1111);
s += ((c >> 2) & 0x1111);
s += ((c >> 3) & 0x1111);
s = (s + (s >> 8)) & 255;
return (s&15) + (s>>4);
}

Compared to the other approach which requires on average 15 ANDs,
shifts, additions and XORs this approach only requires 6 ANDs, 5 shifts
and 5 additions. It's also constant time (in the realtime sense).



Tom

 

[pete]

Trying to return the number of 'on' bits in a byte:

I can't think of a better way.

int BitCount(char c)
{
int ctr;
int bits = 0;
for (ctr = 0; ctr < 8; ctr++) {
bits += c & 0001;
c >>= 1;
}
return (bits);
}

unsigned bit_count(unsigned n)
{
unsigned count;

for (count = 0; n != 0; n &= n - 1) {
++count;
}
return count;
}

 

[Dann Corbit]

unsigned bit_count(unsigned n)
{
unsigned count;

for (count = 0; n != 0; n &= n - 1) {
++count;
}
return count;
}

/* Got tableshiftcast from Chris Torek IIRC. */

static const char nbits[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

int
tC_tableshiftcast (unsigned long n)
{

return nbits[(unsigned char) n] +
nbits[(unsigned char) (n >> 8)] +
nbits[(unsigned char) (n >> 16)] +
nbits[(unsigned char) (n >> 24)];
}

/*
Some hacky things for 64 bit versions:
*/
#include <assert.h>
#include <limits.h>

#if (~(USHRT_MAX+UCHAR_MAX) != ~USHRT_MAX-UCHAR_MAX)
#error(no two's-complement);
#endif

typedef unsigned long long bitboard;

/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Matt Taylor's implementation of the de Bruijn bitscan:

From a post on CCC:
http://chessprogramming.org/cccsearch/ccc.php?art_id=306789

Subject : Re: There is huge potential to improve further
Posted by : Matt Taylor on July 16, 2003 at 22:44:43

Which is indirectly a reference to this work:

"Using de Bruijn Sequences to Index a 1 in a Computer Word"

Charles E.Leiserso
Harald Prokop
Keith H, Randall

MIT Laboratory for Computer Science, Cambridge, MA 02139, USA
July 7, 1998

http://supertech.csail.mit.edu/papers/debruijn.ps

The reset option is an obvious and useful addition implemented
by Gerd Isenberg
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */

const int lsz64_tbl[64] =
{
0, 31, 4, 33, 60, 15, 12, 34,
61, 25, 51, 10, 56, 20, 22, 35,
62, 30, 3, 54, 52, 24, 42, 19,
57, 29, 2, 44, 47, 28, 1, 36,
63, 32, 59, 5, 6, 50, 55, 7,
16, 53, 13, 41, 8, 43, 46, 17,
26, 58, 49, 14, 11, 40, 9, 45,
21, 48, 39, 23, 18, 38, 37, 27,
};

unsigned int bitScanAndReset(bitboard & bb)
{
assert(UINT_MAX >= 0xffffffff);
bitboard b = bb ^ (bb - 1);
bb &= (bb - 1);
unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));
return lsz64_tbl[(fold * 0x78291ACF) >> (32 - 6)];
}
unsigned int bitScan(bitboard & bb)
{
assert(UINT_MAX >= 0xffffffff);
bitboard b = bb ^ (bb - 1);
unsigned int fold = (unsigned) ((b & 0xffffffff) ^ (b >> 32));
return lsz64_tbl[(fold * 0x78291ACF) >> (32 - 6)];
}



// return index 0..63 of MSB
// -1023 if passing zero

unsigned int bitScanReverse(bitboard bb)
{
union {
double d;
struct {
unsigned int mantissal : 32;
unsigned int mantissah : 20;
unsigned int exponent : 11;
unsigned int sign : 1;
};
} ud;
ud.d = (double)(bb & ~(bb >> 32));
return ud.exponent - 1023;
}

/*popCount()
*a noniterative population count of 1 bits in a quadword
*
*@param b - the quadword to be counted
*@returns the number of 1 bits in b
*/
#define m1 0x5555555555555555ULL
#define m2 0x3333333333333333ULL
unsigned popCount(bitboard b)
{
assert(UINT_MAX >= 0xffffffff);
unsigned n;
const bitboard a = b - ((b >> 1) & m1);
const bitboard c = (a & m2) + ((a >> 2) & m2);
n = (unsigned) ((c & 0xffffffff) + (c >> 32));
n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
n = (n & 0xFFFF) + (n >> 16);
n = (n & 0xFF) + (n >> 8);
return n;
}

 

[Joe Wright]

Trying to return the number of 'on' bits in a byte:
'a' = 01100001 = 3 on bits, etc...

I'm just adding a bit-wise AND ('&' against octal 1) to a counter called
'bits', then shifting my byte 1 bit to the right; do this 8 times.

This works, but I was curious if there's some more effective formula
without looping or recursion? That seems like an awful lot of code, but
I can't think of a better way.


int BitCount(char c)
{
int ctr;
int bits = 0;
for (ctr = 0; ctr < 8; ctr++) {
bits += c & 0001;
c >>= 1;
}
return (bits);
}

Don't worry about char, use unsigned int.

#include <stdio.h>
#include <stdlib.h>

int bits(unsigned u) {
int ret = 0;
if (u) ++ret;
while ((u &= u - 1)) ++ret;
return ret;
}

int main(int argc, char *argv[]) {
int ans;
unsigned try = 255;
if (argc > 1) {
try = (unsigned)atoi(argv[1]);
}
ans = bits(try);
printf("%u has %d bit%s\n", try, ans, ans == 1 ? "" : "s");
return 0;
}

Enjoy..

 

[Ian Collins]

Trying to return the number of 'on' bits in a byte:
'a' = 01100001 = 3 on bits, etc...

I'm just adding a bit-wise AND ('&' against octal 1) to a counter called
'bits', then shifting my byte 1 bit to the right; do this 8 times.

This works, but I was curious if there's some more effective formula
without looping or recursion? That seems like an awful lot of code, but
I can't think of a better way.


int BitCount(char c)
{
int ctr;
int bits = 0;
for (ctr = 0; ctr < 8; ctr++) {
bits += c & 0001;
c >>= 1;
}
return (bits);
}

For the perverse:

unsigned bitCount( unsigned char n )
{
unsigned count = 0;

if( n ) {
count = bitCount( n >> 1 );
}
return count+(n&1);
}

 

[Jonathan Lamothe]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

1. Right shifting signed types == bad

Out of curiosity, why specifically do you say that?

Is it just because you don't necessairily know how many bits are in a
given type? (Mind you, with char it's a pretty safe assumption you've
got 8.)

- --
Regards,
Jonathan Lamothe

/*
* Oops. The kernel tried to access some bad page. We'll have to
* terminate things with extreme prejudice.
*/

die_if_kernel("Oops", regs, error_code);
-- From linux/arch/i386/mm/fault.c
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFEvZZ+q9nD47x87JYRAqOUAJwPC2ctBPW2lb47j3dMWr2hKcJlLwCfctEC
e0t8HL6bG5S5c/9quZs6pTw=
=bCmW
-----END PGP SIGNATURE-----

 

[J. J. Farrell]

Out of curiosity, why specifically do you say that?

It's not portable. If the value being shifted is negative, the result
of the shift is implementation defined - it can be different on
different compilers and systems.

(Mind you, with char it's a pretty safe assumption you've got 8.)

That you've got at least 8, certainly.

 

[Morris Dovey]

Tom St Denis (in
(e-mail address removed)) said:

| Morris Dovey wrote:
|| int BitCount(unsigned char c)
|| { int bits = 0;
|| do bits += c & 1; while (c >>= 1);
|| return bits;
|| }
|
| bah
|
| int bitcount(unsigned char c)
| {
| unsigned char s;
| s = (c & 0x11);
| s += ((c >> 1) & 0x11);
| s += ((c >> 2) & 0x11);
| s += ((c >> 3) & 0x11);
| return (s&15) + (s>>4);
| }
|
| Compared to the other approach which requires on average 15 ANDs,
| shifts, additions and XORs this approach only requires 6 ANDs, 5
| shifts and 5 additions. It's also constant time (in the realtime
| sense).
|
|

I'm intrigued by your analysis. How were you able to arrive at these
averages for my (admittedly crude) method of counting 'on' bits in an
unsigned char. I'm especially interested in how you arrived at the XOR
contribution.

If you like that approach, why wouldn't you:

int BitCount(unsigned char c)
{ unsigned char s = c & 0111;
s += (c >> 1) & 0111;
s += (c >> 2) & 011;
return (s&3) + ((s>>3)&3) + (s>>6);
}

5 ANDs, 4 shifts, 4 additions (and, of course, constant time) :-D

 

[manoj1978]

Trying to return the number of 'on' bits in a byte:
'a' = 01100001 = 3 on bits, etc...

I'm just adding a bit-wise AND ('&' against octal 1) to a counter called
'bits', then shifting my byte 1 bit to the right; do this 8 times.

This works, but I was curious if there's some more effective formula
without looping or recursion? That seems like an awful lot of code, but
I can't think of a better way.


int BitCount(char c)
{
int ctr;
int bits = 0;
for (ctr = 0; ctr < 8; ctr++) {
bits += c & 0001;
c >>= 1;
}
return (bits);
}

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

 

[Bill Pursell]

Trying to return the number of 'on' bits in a byte:
'a' = 01100001 = 3 on bits, etc...

<NON_PORTABLE GCC-SPECIFIC CODE>

printf("x has %d bits set\n", __builtin_popcount(x));

<\NON_PORTABLE GCC-SPECIFIC CODE>

Note that whatever architecture you're on may have
an assembly level command for returning the
number of bits set in a register. The lookup table
on 8 bits is, IMO a better solution.