🔒 Locked

counting bits.

Started by Marty666 Sep 15, 2005 at 4:42 PM 1 reply 800+ views

Original Post

Sep 15, 2005 at 4:42 PM

Hi all, I've got a simple 3d engine with a renderqueue that sorts all the objects that need to be rendered by most expensive renderstate change. Each object has an unsigned int where the bits are the flags for the states. When these flags differ from the flags that are set i have a function that checks which states have to be changed:


if ((oldstates ^ newstates) & somestate) == somestate)
{
    if (newstates & somestate) enable(somestate);
    else disable(somestate);
}

Since there are lots of states to check (about 32) it would be nice to skip the checks above (if ((oldstates ^ newstates) & somestate) == somestate)) if i know all have been done. One way I came up with is: countbits(oldstates ^ newstates) oldstates ^ newstates will be an unsigned int that had a bit set for every state that has to be changed. If there's a fast function to count the bits in this unsigned int I would be able to return from the checking (above) when I've changed the maximum number of changes. my question: Is there a faster way anyone knows of to check which states have to be changed? and : Is there a quick way to count the bits in an int. thanx a lot, Marty

Aprosenf

Sep 15, 2005 at 5:08 PM

The best way to count bits is to use a lookup table. Of course, the table can't practically have 4 billion entries, so you'll have to do a few lookups per int. For example:

const int bitsSetInByte[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};inline int bitsSet(unsigned int value){	return bitsSetInByte[value & 0xFF] +	       bitsSetInByte[(value >> 8) & 0xFF] +	       bitsSetInByte[(value >> 16) & 0xFF] +	       bitsSetInByte[(value >> 24) & 0xFF];}

intransigent-seal

102

intransigent-seal

Sep 15, 2005 at 5:30 PM

A nifty little trick can be seen here.

Quote:
Counting bits set, Brian Kernighan's way
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}

Brian Kernighan's method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.

So, something along these lines perhaps:

typedef unsigned int uint32;uint32 changed_states = newstates ^ oldstates;while (changed_states){    // get the least significant bit    uint32 state = changed_states & ~(changed_states - 1);    if (newstates & state)        enable(state);    else        disable(state);    // clear the least significant bit    changed_states &= (changed_states - 1);}

The only part I'm not certain about is the bit twiddling to get just the least significant bit - you'll have to think hard about that to check whether it will work in all circumstances.

John B

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.