Binary Manipulations

Atrevida Game Programming Tutorial #3
Copyright 1997, Kevin Matz, All Rights Reserved.

"Prerequisites:"

Chapter 1: Introduction to Binary and Hexadecimal
Chapter 2: Binary Operations

This chapter will consider in more detail the process of modifying specific bits in a binary number (typically a byte). We will also learn how to extract information from a number. First, however, we will consider bit shifting, which is often helpful in the above tasks.

Bit shifting

Bit shifting lets us move all of the bits in a binary number type (usually a byte or a word) either to the left or to the right a specified number of times.

For example, if we shift the byte "00110111 bin" left once, we get "01101110 bin". If we shift "10110011 bin" right by three places, we get "00010110 bin". Notice in the right-shift example that bits that are shifted out of the byte are lost. This also occurs with left-shifting: if any bits are shifted outside of the "boundaries" of the type in use (eight bits, for a byte), they are lost. Also notice that zeroes, not ones, are always "shifted in" from the other end.

In C and C++, the bitwise shifting operators are << (left shift) and >> (right shift). The expression "a << b" will evaluate to the number a shifted to the left by b places. You can also use <<= and >>= in the same way that you would use operators such as += and -=. Remember that C and C++ do not allow you to directly enter binary numbers, so you must convert any binary numbers to hexadecimal (and prefix them with "0x") or decimal. So, if x is a byte-sized type (char or unsigned char), then "x = 5 << 1" will shift the binary equivalent of 5 dec left by one, and "x >>= 4" will shift x to the right four places (and place the result back into x).

Elsewhere, you will probably see SHL and SHR used in place of C/C++'s << and >> operators. (Also, note that << and >> are not to be confused with C++'s stream operators.)

Notice that these shifting operations may cause problems with binary numbers that you consider signed (two's complement) -- this will be discussed in another chapter.

Let's try shifting some bytes. If we shift "00000001 bin" (1 dec) left, we get "00000010 bin" (2 dec). If we shift that number left, we get "00000100 bin" (4 dec). If we keep shifting these results to the left, we get the pattern 8 dec, 16 dec, 32 dec, etc. We've seen this pattern before: each number is double the previous number. So if we want to multiply a number by two, we can shift it left once. This works for any arbitrary number you might try: "01100101 bin" (101 dec) shifted left is "11001010 bin" (202 dec). However, be aware that if any bits fall outside the range of the type, the resulting byte will no longer be correct.

Conversely, shifting a number to the right once halves the number. But notice that if any bits are shifted outside the range of the type, accuracy is lost. Notice how "00010101 bin" (21 dec), shifted right by one, gives "00001010 bin" (10 dec). The answer should, of course, be 10.5 dec, but we are dealing with whole numbers, so the desired 10.5 dec is truncated to 10 dec.

Why does this work? Well, if we draw our byte diagram, with the values associated with each bit written above...

       7   6   5   4   3   2   1   0
      2   2   2   2   2   2   2   2
    +---+---+---+---+---+---+---+---+
    | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
    +---+---+---+---+---+---+---+---+

...we can see that a 1 in, say, the 2^4 (16 dec) position that gets shifted left becomes worth 2^5 (32 dec) instead of 2^4 (16 dec). Similarly, a bit that is shifted right is worth only half as much.

We can multiply (or divide) numbers by powers of two (2, 4, 8, 16, etc). using bit shifting. Obviously, shifting a number left and then shifting the result left again is equivalent to shifting a number left by two. The two shift lefts result in multiplying the original number by two and then by two again, with a net result of multiplying by four. So, a shift left by 1 is equal to multiplying by 2^1, and a shift left by 2 is equal to multiplying by 2^2, and a shift left by 3 is the same as multiplying by 2^3, and so on. In general, to multiply by a power of two, shift the number left x times, where "multiplier = 2^x". (To divide, shift right by x.)

Briefly, why bother with bit shifting for this purpose when multiplying and dividing already adequately perform the same tasks? It turns out that, on the PC (and very likely, most all other computers), performing a shift is much faster than performing a multiply or divide. (When we deal with optimization in later chapters, we'll investigate this topic further.)

Before we leave this topic, I want to mention the rotate-left and rotate-right operations. These operations take bits that "fall off the edge" of a type and insert them back on the other side of the number, so no bits are lost. (Rotating a number of a certain type left or right by the number of bits in the width of that type gives back the original number.) C and C++ provide no operations for bitwise rotation, which is fine, because they are only rarely used.

Setting fields in larger number types

Often it is necessary to set fields, or ranges of bits, within a number (most often a byte). Sometimes, when accessing a register or memory location (discussed in later chapters), we need to set several bits in a byte. We may be given a diagram that indicates which bits correspond to which functions. In these diagrams, the bits are numbered from 0 to 7 (or 0 to 15 for a word) from the right (least-significant) to the left (most-significant). These "bit numbers" are the same as the exponents that we used previously. The following is an entirely imaginary diagram; the byte which is referred to in this diagram perhaps controls a robot or a toy car connected to the computer:

      7     6     5     4     3     2     1     0
   +-----+-----+-----+-----+-----+-----+-----+-----+
   | XXX | DIRECTION |      SPEED      | LTS | PWR |
   +-----+-----+-----+-----+-----+-----+-----+-----+

   Bit 0:     Power on/off:  1 = ON, 0 = OFF
   Bit 1:     Headlights on/off:  1 = ON, 0 = OFF
   Bits 4..2: Speed (0..7 dec)
   Bits 6..5: Direction: 00 = FORWARD; 01 = TURN RIGHT; 10 = TURN LEFT;
                         11 = REVERSE
   Bit 7:     Unused

If we were to somehow send this control byte to the robot or toy car, we could control its actions. The byte "01110011 bin" would mean "turn the power on, turn the headlights on, set the speed to 4 dec (100 bin), and travel in reverse" (the unused bit, bit 7, could be either 1 or 0; its value has no effect).

Now say that we want to change just one field in this byte. Perhaps we need to change the speed, but we would like to keep everything else as is. A common procedure for this task is to: 1. construct an AND mask, which is designed to zero-out the field in question, 2. AND the original byte with the AND mask, 3. construct an OR mask (perhaps by using bit shifting) which is designed to set the desired bits, and 4. OR the the result from the second step with the OR mask.

Let's work through an example, using C/C++. Let's say we have a variable speed, which is some number between 0 and 7 dec (let's say it is 3 dec (that's 00000011 bin)). Let's also say that we have read the current control byte from our device and it is stored in a variable called control_byte. To change the speed in the control byte to the speed specified in speed, we can do this:

1. Construct an AND mask: "11100011 bin" will leave all the fields except for the SPEED field alone. Store the mask in and_mask.
2. Evaluate "control_byte AND and_mask". Store the result back in control_byte.
3. Construct an OR mask. speed contains "00000011 bin". To move the three least-significant bits into position, we can shift speed left by two. We can store the result of this left-shift in or_mask.
4. Evaluate "control_byte OR or_mask". Store the result back in control_byte.

Now, we could send control_byte out to our device, and it would change its speed. In C/C++, the above steps could be written as follows (I've taken out the unnecessary references to the variables and_mask and or_mask):

speed = 3;

/* (read control_byte from the device here) */
control_byte &= 0xE3;
control_byte |= (speed << 2);
/* (write control_byte back to the device here) */

Testing bits or extracting fields from larger number types

It is common to read in a byte from a device and extract information from it. We can simply apply an AND mask that has ones where the information is to be saved, and zeroes everywhere else.

Let's take our robot/toy car example again. Say that we have read in control_byte from this device, and we wish to determine what the device's current direction is. Our AND mask would be "01100000 bin". Then we would like to shift the result to the right by five. In C/C++:

/* (read control_byte from the device here) */
direction_code = (control_byte & 0x60) >> 2;

Sometimes we want to see if a single bit is set or cleared. This is easy to do: set up an AND mask with a one corresponding to the bit you wish to test. AND the original number with the AND mask. Then, if the result equals zero, the bit must be zero; if the result is non-zero, the bit must be one. In the following code fragment, we will display a message regarding the status of the headlights on our device (yes, you could rewrite it to remove the "== 0"):

/* (read control_byte from the device here) */
if (direction_code & 0x02 == 0)
        printf ("The headlights are off.\n");
else
        printf ("The headlights are on.\n");

Summary

In this chapter, we have learned about bit shifting, and methods for setting and retrieving fields in bytes or words. We have also seen how we can easily test single bits.

This chapter concludes all of the details regarding the manipulation of binary and hexadecimal numbers!

A project