Most efficient way to extract bit flags

Question

I have these possible bit flags.

1, 2, 4, 8, 16, 64, 128, 256, 512, 2048, 4096, 16384, 32768, 65536

So each number is like a true/false statement on the server side. So if the first 3 items, and only the first 3 items are marked "true" on the server side, the web service will return a 7. Or if all 14 items above are true, I would still get a single number back from the web service which is is the sum of all those numbers.

What is the best way to handle the number I get back to find out which items are marked as "true"?

Answer 1

Use a bit masking operator. In the C language:

 X & 8

is true, if the "8"s bit is set.

You can enumerate the bit masks, and count how many are set.

If it really is the case that the entire word contains bits, and you want to simply compute how many bits are set, you want in essence a "population count". The absolute fastest way to get a population count is to execute a native "popcnt" usually available in your machine's instruction set.

If you don't care about space, you can set up a array countedbits[...] indexed by your value with precomputed bit counts. Then a single memory access computes your bit count.

Often used is just plain "bit twiddling code" that computes bit counts:

(Kernigan's method):

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
}

(parallel bit summming, 32 bits)

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

If you haven't seen the bit twiddling hacks before, you're in for a treat.

PHP, being funny, may do funny things with some of this arithmetic.

Answer 2

Thought the question is old might help someone else. I am putting the numbers in binary as its clearer to understand. The code had not been tested but hope the logic is clear. The code is PHP specific.

define('FLAG_A', 0b10000000000000);  
define('FLAG_B', 0b01000000000000);
define('FLAG_C', 0b00100000000000);
define('FLAG_D', 0b00010000000000);
define('FLAG_E', 0b00001000000000);
define('FLAG_F', 0b00000100000000);
define('FLAG_G', 0b00000010000000);
define('FLAG_H', 0b00000001000000);
define('FLAG_I', 0b00000000100000);
define('FLAG_J', 0b00000000010000);
define('FLAG_K', 0b00000000001000);
define('FLAG_L', 0b00000000000100);
define('FLAG_M', 0b00000000000010);
define('FLAG_N', 0b00000000000001);

function isFlagSet($Flag,$Setting,$All=false){
  $setFlags = $Flag & $Setting;
  if($setFlags and !$All) // at least one of the flags passed is set
     return true;
  else if($All and ($setFlags == $Flag)) // to check that all flags are set
     return true;
  else
     return false;
}

Usage:

if(isFlagSet(FLAG_A,someSettingsVariable)) // eg: someSettingsVariable = 0b01100000000010

if(isFlagSet(FLAG_A | FLAG_F | FLAG_L,someSettingsVariable)) // to check if atleast one flag is set

if(isFlagSet(FLAG_A | FLAG_J | FLAG_M | FLAG_D,someSettingsVariable, TRUE)) // to check if all flags are set