Select Page

So, you have heard the term binary before, but really, what does it mean? How is it useful? And when should it be used in code? These questions are all answered in this article that revolves around the intricacies of binary math.

#### What Does It Mean?

Binary is just one of a number of systems used to describe integers. There are several popular systems, but for this article, we will contain our discussion to “decimal” and “binary”.

As you may know, the prefix of decimal, “deca”, means “ten”. The decimal system is base-10. What this means is that there are ten unique symbols that can represent any particular digit in a decimal system number. These “symbols” are the integers 0 through 9. Let’s take a unique look at a traditional decimal number and see exactly how it can be manipulated:

```27
:: break down what each digit technically means ::
( 2 x 10^1 ) + ( 7 x 10^0 )
( 2 x 10 ) + ( 7 x 1 )
( 20 ) + ( 7 )
27
:: check successful ::```

So where did this come from? Well, the best way to understand this is to understand the formula applied here. In all number systems, the formula is similar. But first, let’s get some terminology down:

Index
Starting with the rightmost digit, assign an integer starting with 0 and increment until you reach the leftmost digit.

Base
This number is based upon which number system you are currently using. For “decimal”, you would use 10, for “binary”, you would use 2.

So getting back to the point — you want to start your conversion at the rightmost digit. Take the base of the number system and raise it to this digit’s index. Then take this result and multiply it by the digit, itself. This product should then be stored off to the side, so to speak. Perform the same logic on each and every digit, then sum all of the products resulting from the previous computations. This shall give you a number with which you would be more familiar.

For you math geniuses out there, the formula is something like: Σ( digit * base^index )

Pretty easy, huh?

Let’s try to convert a binary number now:

```11011
:: break down what each digit technically means ::
( 1 x 2^4 ) + ( 1 x 2^3 ) + ( 0 x 2^2 ) + ( 1 x 2^1 ) + ( 1 x 2^0 )
( 1 x 16 ) + ( 1 x 8 ) + ( 0 x 4 ) + ( 1 x 2 ) + ( 1 x 1 )
( 16 ) + ( 8 ) + ( 0 ) + ( 2 ) + ( 1 )
27
:: check successful ::```

Binary means that we are using base-2. This means that there are only two different symbols available in this number system — 0 and 1. So we found out that 27 in decimal is the same as 11011 in binary form! If you were to test this in a scientific calculator (or the Windows Calculator), you would find the same result.

#### How Is It Useful?

To a computer, binary numbers are everything. For instance, a computer is made up of bits. These bits are either a 0 or a 1, usually meaning off or on, respectively. These bits make up the blueprints of programs that run on your computer. In this respect, the numbers are pretty meaningless to humans because there are so many of them — but without them, the different parts of a computer would have problems communicating with one another through the various electrical devices that each employs.

To humans, we can perform what is known as bitwise operations to binary numbers. This simply refers to the act of operating upon each bit in a binary number in some sort of way. The various ways we can operate upon binary numbers are:

 AND & 1 0 1 1 0 0 0 0
 OR | 1 0 1 1 1 0 1 0
 XOR ^ 1 0 1 0 1 0 1 0

Generally think of a 0 as false and a 1 (or any non-zero) as true. If you are familiar with Discrete Mathematics logic tables, you should have noticed some familiarities. So how does this work exactly? Let’s work out an example:

```5 & 3
:: convert each number to binary and apply the logic tables
to each column ::
5 = 101
3 = 011 &
---
001 = 1```

So, 5 & 3 = 1 (read “five and three equals one”). We perform the same sort of thing when ORing or XORing, as well. We’ve already covered three special bitwise operators; however, there are a few more worth noting right now:

Not (~)
Changes all 0 bits to 1 and vice-versa. Also referred to as the complement.

Left Shift (<<)
Moves all bits one position to the left. 0 is tacked on to the right side of the binary number. This effectively multiplies the number in question by 2^X, where X is the number of positions that are being shifted.

Right Shift (>>)
Moves all bits one position to the right. Whatever the bit was on the rightmost end of the binary number before the shift is truncated after the shift. This effectively divides the number in question by 2^X, where X is the number of positions that are being shifted.

#### When Should It Be Used In Code?

There are several applications of bitwise operations in code. The examples that I discuss here mostly touch on game programming, but can easily relate to other Computer Science fields.

1. Faster Division/Multiplication

There are often times you will have a need to double an integer or divide it in half. To do this, you would normally do something like this:

[sourcecode language=”cpp”]
{
int x = 4;

// double the value…
x = x * 2;
}
[/sourcecode]

Although this works, on some compilers, there is a faster way of doing this:

[sourcecode language=”cpp”]
{
int x = 4;

// double the value…
x = x << 1;
}
[/sourcecode]

2. Giving Attributes

Let’s say that you have a structure of a knight that looks something like this:

[sourcecode language=”cpp”]
struct tKnight
{
int fLife;
int fHasShield;
int fHasHelmet;
int fHasArmor;
};
[/sourcecode]

Then in the implementation, we do something like this:

[sourcecode language=”cpp”]
void TestPlayerEquipment( struct tKnight* object )
{
if ( object->fHasShield == 1 )
{
printf( “This player has a shield equipped.n” );
}
if ( object->fHasHelmet == 1 )
{
printf( “This player has a helmet equipped.n” );
}
if ( object->fHasArmor == 1 )
{
printf( “This player has armor equipped.n” );
}
}

void main( void )
{
// create the player
struct tKnight gPlayer;

// assign attributes to the player
gPlayer.fLife = 100;
gPlayer.fHasShield = 1;
gPlayer.fHasHelmet = 0;
gPlayer.fHasArmor = 1;

// test to see what the player has equipped
TestPlayerEquipment( gPlayer );
}
[/sourcecode]

Note that we have three different variables holding whether or not a knight has three distinct pieces of equipment – shield, helmet, and armor. Although this is clear, it can be made more efficient and kept just as clear through the use of bitwise operations. Let’s rewrite the structure:

[sourcecode language=”cpp”]
enum eEquipment
{
kShield = 1, // binary = 0001
kHelmet = 2, // binary = 0010
kArmor = 4 // binary = 0100
};

struct tKnight
{
int fLife;
int fEquipment;
};
[/sourcecode]

Notice that we have condensed the size of the structure by quite a bit. But we have also added an enumeration and have assigned each a value that is a power of 2. You will understand why in a moment.

Next, let’s rewrite the implementation:

[sourcecode language=”cpp”]
void TestPlayerEquipment( int stuff )
{
if ( stuff & kShield )
{
printf( “This player has a shield equipped.n” );
}
if ( stuff & kHelmet )
{
printf( “This player has a helmet equipped.n” );
}
if ( stuff & kArmor )
{
printf( “This player has armor equipped.n” );
}
}

void main( void )
{
// create the player
struct tKnight gPlayer;

// assign attributes to the player
gPlayer.fLife = 100;
gPlayer.fEquipment = kShield | kArmor;

// test to see what the player has equipped
TestPlayerEquipment( gPlayer.fEquipment );
}
[/sourcecode]

First, in the main function, notice how we use the bitwise OR (|) operator to assign gPlayer.fEquipment. Let’s look at the underlying binary:

```:: write out the binary forms of each piece of equipment that we assign
one under the other ::
0001
0100 |
----
0101 :: = gPlayer.fEquipment ::```

As you might be able to tell, as long as we use powers of 2 for the equipment in the enumeration, we will never have a problem using the bitwise OR operator in this respect. What we have effectively done is to condense two pieces of information, which previously resided in two separate integer variables, into one integer variable.

Now let’s take a look at the TestPlayerEquipment function. Instead of using the equality operator (==) on each piece of equipment, we can use the bitwise AND (&) operator on a single integer variable — in this case, stuff. Let’s see how this works:

```:: test "stuff" for presence of shield ::
0101
0001 &
----
0001 :: true ::

:: test "stuff" for presence of helmet ::
0101
0010 &
----
0000 :: false ::```

The process that we have gone through here is commonly referred to as bitmasking. It is used fairly often in the game industry, but is also used in general applications. Often times, it’s implementation may be a bit transparent as in the case of the BitBlt function from the Windows API.

3. Fixed Point

On certain consoles (and very old computers), the hardware does not contain a chip that goes by the name of floating-point unit or more commonly known as FPU. If the hardware with which you work does not have an FPU, then you will not be able to work with values like 5.7, 3.542, etc. In other words, fractional parts are out of the question.
To remedy this, a method has been drawn up that mimics the fractional part of a floating- point number. This method involves quite a bit of binary math and some of its more common implementation is listed below:

[sourcecode language=”cpp”]
typedef tInt32 tFix; // “tInt32” is just a 32-bit integer
#define kFix_Bits 16

#define FIX_TO_INT( fix ) ( ( fix ) >> kFix_Bits )
#define FIX_TO_INT_TRUNC( fix ) ( ( fix ) >> kFix_Bits )
#define INT_TO_FIX( i ) ( ( i ) << kFix_Bits ) #define HALVE_FIX( fix ) ( ( fix ) >> 1 )
#define MUL_SMALL_FIX( fixA, fixB ) ( ( ( fixA ) * ( fixB ) ) >> kFix_Bits )
[/sourcecode]

Note that kFix_Bits is set to 16. What we are saying is that out of the 32 bits that make up an integer, the rightmost 16 bits are set aside for the fractional part.

There are other macros that are often used with fixed-point math, but the implementation of those functions is usually highly dependent on the hardware with which one is working.

I hope you are not afraid of binary math. Hopefully, this article opened your eyes to a concept that is usually passed over in most programming courses, but offers reasonable applications in real code.