Bitwise Operators used for Flagging Items

Update: Thanks to Jesper Noehr of BitBucket fame for pointing out gaping flaws in my post below (see his comment). I strongly advise you disregard all I have said below, because it will get you into a mess, in much the same way it has me. I’m going to sit down when I have a spare 1/2 hour and try to work out exactly what is going on! Many thanks and big kudos to Jesper, I really appreciate the time you took to correct me.


I have always wondered what the point of Bitwise Operators were,to me they seem to belong to a distant past. However, after reading a couple of great blog posts I have at last an understanding of how they can be put to use, and have started playing around with them a bit (ba dum!).

Jesper Noehr has written about using bitwise operators for a flexible permissions scheme within Python  and Jonathan Snook has taken the bitwise concept further creating a great calendar app in Javascript. After reading these I thought I better dive in, and an opportunity came along yesterday when I had to code a flagging system within PHP.

For the benefit of this post I have greatly simplified the problem but hopefully it should be enough to get an understanding and allow you to get started with playing around with bits.

The problem is as follows. I have a number of items and each item has 3 different flags associated with it. We’ll call these flags F1, F2 and F3. A single item can have none, some or all flags set, and needs to have the ability to turn each flag on or off independently. The “base” state for each item is that no flags are set.

Each flag is a boolean, on or off, or to put it another way, 1 or 0. This translates perfectly into binary numerals. If we visualise this with a number of examples:

No flags switched on

F1 F2 F3 Binary Number
0 0 0 0

Just F1 switched on

F1 F2 F3 Binary Number
1 0 0 001 or 1

Just F2 switched on

F1 F2 F3 Binary Number
0 1 0 010 or 10

Just F3 switched on

F1 F2 F3 Binary Number
0 0 1 100

F1 and F3 switched on

F1 F2 F3 Binary Number
1 0 1 101

The reason we have translated the binary number for just F1 switched on to 001 and not 100 is because from a text point of view, we read F1, F2 then F3 from left to right, but from a numeric point of view we read numbers right to left, i.e. 1s then 10s then 100s then 1000s etc.

From the above examples, we can see that if F1 is already switched on, we can easily switch on F3 as well by simply turning on the F3 bit. We accomplish this by simply adding the F3 bit:
Base + F1 + F3 = 0 + 1 + 100 = 000 + 001 + 100  = 101

We can also remove flags, for example if we have F3 and F1 set, but then remove F1 we have:
101 – 001 = 101 – 1 = 100
But even though these are all ones and noughts we can translate these into decimal. PHP has a handy little utility function for this: decbin() [http://php.net/manual/en/function.decbin.php]

State Binary Decimal
All off 0 0
F1 on 1 1
F2 on 10 2
F3 on 100 4
F1 and F3 on 101 5 (1 + 4)
All on 111 7 (1 + 2 + 4)

So now this makes it really easy to turn flags on an off.
In PHP it would be as follows:

define('BASE', 0);
define('F1', 1);
define('F2', 2);
define('F3', 4);
 
echo "No flags = ".BASE.":".decbin(BASE)."n";
 
// switching flags on
$f1_on = BASE+F1;
echo "Turn on F1 = $f1_on:".decbin($f1_on)."n";
 
$f2_on = $f1_on+F2;
echo "Turn on F2 = $f2_on:".decbin($f2_on)."n";
 
$f3_on = $f2_on+F3;
echo "Turn on F3 = $f3_on:".decbin($f3_on)."n";
 
// switching flags off
$f2_off = $f3_on-F2;
echo "Turn off F2 = $f2_off:".decbin($f2_off)."n";
 
$f1_off = $f2_off-F1;
echo "Turn off F1 = $f1_off:".decbin($f1_off)."n";

Save this as bits.php and then run it from the command line with:

$ php ./bits.php
No flags = 0:0
Turn on F1 = 1:1
Turn on F2 = 3:11
Turn on F3 = 7:111
Turn off F2 = 5:101
Turn off F1 = 4:100

All good so far, but now we need to see if a particular flag is switched on or off. I’ll publish that in my next blog post. So stay tuned.

  • jespern

    Hi Rob,

    Thanks for the mention. Unfortunately, there’s something fundamentally wrong with your article, and possibly with your understanding of how this works.

    As I mention in my article, it’s easy to get tricked into thinking binary OR (|) is equal to numerical addition (+), alas, it is not. The same goes for numerical subtraction (-), which is, well, &~ in bitwise operators, and a bit more advanced than simply doing OR and AND’s.

    Consider this:

    F1 = 1<<1
    F2 = 1<<2

    mask = F1 # set the F1 flag

    print mask + F1 # you get 4, which is, incorrect, F1 is already set.
    print mask | F1 # you get 2, which is correct, F1 is already set.

    You get the same results with subtraction:

    mask = F1 | F2 # set both
    print mask &~ F1 # 4, which is F2, correct.
    print mask – F1 # 4, also "correct", but,
    print (mask – F1) – F1 # 2, oops.
    print (mask &~ F1) &~ F1 # 4, correct, bit is already unset, second time has no effect.

    You should revise your findings, as not understanding these things properly will cause significant flaws.

    Hope this helps,

    • http://www.robsearles.com Rob Searles

      Wow! Thanks.

      Clearly this bitwise stuff is harder than I originally thought! Good job the interwebs are full of people more brainy than me.

      I’m going to have to sit down and have a long think about this stuff as my brain can’t handle it right now, but I’m always like that first thing in the morning.

      Thanks for your comment, and the time take to respond.

  • jespern

    Hi Rob,

    Thanks for the mention. Unfortunately, there's something fundamentally wrong with your article, and possibly with your understanding of how this works.

    As I mention in my article, it's easy to get tricked into thinking binary OR (|) is equal to numerical addition (+), alas, it is not. The same goes for numerical subtraction (-), which is, well, &~ in bitwise operators, and a bit more advanced than simply doing OR and AND's.

    Consider this:

    F1 = 1<<1
    F2 = 1<<2

    mask = F1 # set the F1 flag

    print mask + F1 # you get 4, which is, incorrect, F1 is already set.
    print mask | F1 # you get 2, which is correct, F1 is already set.

    You get the same results with subtraction:

    mask = F1 | F2 # set both
    print mask &~ F1 # 4, which is F2, correct.
    print mask – F1 # 4, also “correct”, but,
    print (mask – F1) – F1 # 2, oops.
    print (mask &~ F1) &~ F1 # 4, correct, bit is already unset, second time has no effect.

    You should revise your findings, as not understanding these things properly will cause significant flaws.

    Hope this helps,

  • http://www.robsearles.com Rob Searles

    Wow! Thanks.

    Clearly this bitwise stuff is harder than I originally thought! Good job the interwebs are full of people more brainy than me.

    I'm going to have to sit down and have a long think about this stuff as my brain can't handle it right now, but I'm always like that first thing in the morning.

    Thanks for your comment, and the time take to respond.

  • Pingback: Rob Searles » Understanding Bitwise Operators (hopefully)