CODEWITHSUNDEEP
algorithm
askovpen
askovpen

Reputation: 2494

easy algorithm for using flags

Exists flags defs:

flag1=1
flag2=2
flag3=4
flag4=8
...
flagN=2^(N-1)

flag=flag1+flag2+...+flagN

if flagI not set, it eq 0

i have flag. which method can easily check, is for example flag2 defined?

Upvotes: 1

Views: 326

Answers (4)

abcdabcd987
abcdabcd987

Reputation: 2053

Answer to your question

What's the range of flag? If it's under 2^64-1, almost every method is okay.

As @taskinoor posted, you should notice that:

flag1 = 000 ... ... 0001 

flag2 = 000 ... ... 0010 

flag3 = 000 ... ... 0100

In other words, 

flag[n] = 1 << (n-1)

So, if you want to check all bits, a for loop and bitwise operation are fast enough to solve you problem. Like This (suppose you could understand C/C++ and flag is less than 2^32, which could be hold by an unsigned int in C/C++):

void check(unsigned int flag)
{
  for (int i = 0; i < 32; ++i)
    if ((flag & (1 << i)) != 0)
      printf("flag%d defined!\n", i+1);
}

It's O(k), which k is the length of the type of flag in binary. For unsigned int, it's O(32) = O(1), almost in constant time.

If you just want to count how many flags defined:

I don't know what's your purpose. If you just want to count how many flags defined and flag is less than 2^64, the following method is awesome(suppose unsigned int as well):

unsigned int count_bit(unsigned int x)
{
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
  return x;
}

If you call count_bit(1234567890), it'll return 12.

Let me explain this algorithm.

This algorithm is based on Divide and Conquer Algorithm. Suppose there is a 8bit integer 213(11010101 in binary), the algorithm works like this(each time merge two neighbor blocks):

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+

Upvotes: 4

Arvind
Arvind

Reputation: 478

It is worth grokking the concept of bitmasks and flags more deeply. You can then use your imagination to represent state efficiently . (Just an example explained below)

 First -Define the bitmask :          0x0000001c

What are the binary strings for which when you do an 'and' operation on the mask, you get a non-zero value?

Those are your valid flag values.

Valid flag values for this bitmask: 0x0000001c,0x00000014,0x00000018,0x00000004,0x00000008,etc ..

So, in your application if you can do the following:

flagvariable |= flagvalue1  ->Enable a particular flag.  
if( flagvariable & maskvalue)   :Check if a mask is enabled  :

Then the different cases you would need to check : 

if(flagvariable &maskvalue ==flagvalue1)    { do something}
else  
if(flagvariable &maskvalue ==flagvalue2) {do something else}    

flagvariable &= `flagvalue1  : Clear the flag

To be more clear about flags and bitmasks, just step into gdb and do p /t and evaluate the the operations described above.

Upvotes: 0

taskinoor
taskinoor

Reputation: 46027

Note that in each flag only one bit is set to 1, others are 0.

flag1 = 000 ... ... 0001
flag2 = 000 ... ... 0010
flag3 = 000 ... ... 0100
// and like this

So if you do bitwise AND flag & flag2 then the result will be non-zero only if flag2 is defined.

r = flag & flag2;
if r != 0 then flag2 is defined

You can do this with all flags.

Upvotes: 4

molyss
molyss

Reputation: 256

Boolean isSet (flags, flagN){
   Return (flags & flagN) != 0;
}

Flags being the flag vector, flagN the flag you want to check

Upvotes: 0

Related Questions