Get a Speed Boost from the Bitwise Operator

By Dave Stewart

Be it ActionScript or PHP, we all find ourselves re-using code snippets we learned (or “borrowed”) at some point during the development of an application. Why re-invent the wheel, right?

Whenever I have a little down time, though, I experiment with new things (as I am sure we all do) or go back and study code that I know works to optimize/improve upon it. Sometimes while researching something, I get off on a tangent and eventually end up unearthing a bit of programming which is very helpful, but often overlooked.

This happened recently when I was building a Flash game and wrote some code to alternate through squares in a grid system. It seemed rather slow, so I started searching for a better solution. I blew the dust off the Bitwise operator (&) and researched what it actually does. I think the reason it was dusty was because of descriptions like this one (from the Flash 8 docs):

expression1 & expression2

Converts expression1 and expression2 to 32-bit unsigned integers, and performs a Boolean AND operation on each bit of the integer parameters. Floating-point numbers are converted to integers by discarding any digits after the decimal point. The result is a new 32-bit integer.

How could that be useful?

Let’s translate this jibberish into something that can save our overworked CPUs some cycles. As you’ll soon see, the bitwise operator can be used in many programming languages.

Below are two examples. The first is one I have written (and re-written) dozens of times in PHP – it alternates between colors on (X)HTML table rows from a MySQL query. The second is the ActionScript required to make a chessboard. These examples are very specific, but this technique can be adapted to any situation in which you want to cycle through for or while loops to find odd or even numbers or trigger on/off switches.

Exhibit A: Stripey tables in PHP

<table>
  <thead>
    <tr>
      <th>Event Date</th>
      <th>Event Title</>
    </tr>
  </thead>
  <tbody>
<?php
  // Define colors for the alternating rows
  $color1 = "#CCCCCC";
  $color2 = "#FFFFFF";
  $row_count = 0;
  // SQL query.
  $sql = mysql_query( "SELECT * FROM events" ) or die( mysql_error() );
  while( $row = mysql_fetch_array( $sql ) ){
    $id = $row["id"];
    $date = $row["date"];
    $title = $row["title"];
    // Alternate the colors between the two colors we defined above.
    $row_color = ( $row_count % 2 ) ? $color1 : $color2;
    // Echo your table row ?>
    <tr>
      <td bgcolor="<?= $row_color ?>"><?= $date ?></td>
      <td bgcolor="<?= $row_color ?>"><a href="articles.php?article_id=<?= $id ?>"><?= $title ?></a></td>
    </tr>
<?php
    // Add 1 to the row count
    $row_count++;
  } ?>
  <tbody>
</table>

Pretty standard stuff right? Now take a look at this line:

    …
    $row_color = ($row_count % 2) ? $color1 : $color2;
    …

A lot of people use this method (which also makes use of the ternery operator) for deciding which color to make a table row. It works great. No big deal for a hundred rows or so, but when we get into thousands of rows, this method can use more system resources than it really needs. To find out why, let’s look at what the % (modulo) operator does.

In computing, given two integers, a and n, a modulo n is the remainder after numerical division of a by n.

The calculation looks something like this:

For example, let’s say $row_count starts at 1024 and performs this operation with n being 2. If the result is 0 (making the statement true) the ? (ternery) operator sets the value of $row_color to $color1; when the statement is false (because the result is 1) it sets $row_color to $color2. Great, no big deal for a computer you say.

Just remember that this statement is likely to be one of dozens or even hundreds of computations your program has to do before returning the results to a user. That’s a lot of unnecessary math (and a real cycle-sucker).

We can optimize this code by using the bitwise operator (&). First, a little definition:

[B]itwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. On many computers, bitwise operations are slightly faster than addition and subtraction operations and significantly faster than multiplication and division operations.

Do you remember how binary works? Here’s a refresher:

001 → 1
010 → 2
011 → 3
100 → 4
101 → 5
and so on…

Each odd number has a binary equivalent with a 1 in the last column, and even numbers have binary equivalents with 0 there. So let’s look for that pattern instead, doing simple comparisons instead of calculations for each iteration.

To do this, we just modify the statement to look like this:

    …
    $row_color = ( ( $row_count & 1 ) == 0 ) ? $color1 : $color2;
    …

What this does is mask $row_count with a 1 and you can see if it is even.

1024 → 10000000000
1023 → 1111111111

All we are doing is checking for a 0 in the last column and that’s a much quicker way of figuring out if the row is even or odd.

But you can do many more things with this too. For example, if you need a simple switch (on/off), consider this instead of doing conditional statements:

$mySwitch = ($counter & 1);
$counter++;

Exhibit B: Chessboard in ActionScript

Here is a 100% ActionScript Chessboard. It could be modified to PHP/(X)HTML to make a checkered table, but that might look a little crazy.

Note: We’re using AS best practices here, keeping our code as portable as possible by using objects.

Copy this to the first frame of a new Flash file

// For a chessboard you want your stage to be equal width and height.
import chessboard;
var w:Number = Stage.width;
var h:Number = Stage.height;
// 8 is the number of squares in a chessboard row.
var chessBoard = new chessboard( w, h, 8 );

Copy this to a file called chessboard.as and save in same directory as the above Flash file:

class chessboard {
  // Private vars
  private var __w:Number;
  private var __h:Number;
  private var __divider:Number;
  private var cols:Number;
  private var rows:Number;
  private var counter:Number;
  private var depth:Number;
  private var i:Number;
  private var j:Number;
  
  // Constructor
  public function chessboard( w:Number, h:Number, divider:Number ){
    this.__w = w;
    this.__h = h;
    this.__divider = w / divider;
    this.cols = w / divider;
    this.rows = h / divider;
    this.counter = 0;

    _root.createEmptyMovieClip( "chessboard_mc", 0 );
    for( i = 0; i < rows; i++ ){
      for( j = 0; j < cols; j++ ){
        depth = _root.chessboard_mc.getNextHighestDepth();
        var square = _root.chessboard_mc.createEmptyMovieClip( "square" + depth + "_mc", depth );
        // Our Bitwise & to make Black or White squares
        var addSquare:Boolean = ( (counter & 1) == 0 ) ? fill( square, 0xFFFFFF ) 
                                                       : fill( square, 0x000000 );
        square._x = j * __divider;
        square._y = i * __divider;
        counter++;
      }
      // We don�t want stripes, we want checkers,
      // so we need to offset the counter on each row.
      counter += 1;
    }
  }
  // Draw and Fill the squares with colors
  function fill( square:MovieClip, color:Number ){
    square.beginFill( color, 100 );
    square.lineStyle( 0, color, 100 );
    square.moveTo( 0, 0 );
    square.lineTo( __divider, 0 );
    square.lineTo( __divider, __divider );
    square.lineTo( 0, __divider );
    square.lineTo(0, 0);
    square.endFill();
  }
}

And that’s all there is to it. It’s amazing how something as simple as an & can be so incredibly useful.

Get the Source

You can download the files that go with this article in a single compressed archive: theBitwiseOperator_files.zip