Bitwise Programming (ActionScript: The Definitive Guide)

15.2.1. Bitwise AND

The bitwise AND operator (&) combines the bits of two numbers by performing a logical AND operation on each bit of the numbers. The operation returns the result of the combination as a number.

A bitwise AND expression takes the form:

operand1 & operand2

The operands of bitwise AND can be any numbers, but they are converted to 32-bit binary integers before the operation occurs. If an operand has a fractional value such as 2.5, the fraction is discarded.

Note that the bitwise AND uses the single-character operator, &, and operates on the individual bits within its operands, whereas the logical AND operator discussed in Chapter 5, "Operators" uses the two-character operator, &&, and treats each operand as a whole.

Bitwise AND returns a number whose value is determined by comparing the individual bits in the numeric operands, operand1 and operand2, one at a time. If a bit contains a 1 in both operands, the corresponding bit will also be set to 1 in the result; otherwise, the bit will be a in the result.

Bitwise AND operations are most easily pictured by arranging the binary equivalents of the decimal operands vertically and lining up their bit columns. In this format, it is easy to tell which bits of the operands both contain 1s.

In this example, bit 2 (the third bit from the right) is 1 in both operands and is therefore set to 1 in the result. Other bits are set to in the result:

1111
& 0100
------
  0100

In this example, bits and 3 are 1 in both operands and are therefore set to 1 in the result. Bits 1 and 2 are set to in the result:

1101
& 1011
------
  1001

ActionScript uses decimal (base-10) numbers instead of binary numbers, which makes it harder to visualize bitwise operations. Here is what the previous operations look like in real code:

15 & 4   // Result is 4
13 & 11  // Result is 9

In practice, the bitwise AND operator is used to check whether a particular flag or set of flags (i.e., bits) is true or false.

The following example checks whether bit 2 (which has the value 4) is set to true:

if (x & 4) { 
  // Do something
}

Or, we can check whether either bit 2 or bit 3 (which has the value 8) is set to true:

if (x & (4|8)) {
  // Do something
}

Note that the preceding example checks whether bit 2 or bit 3 is set using the | operator discussed next. To check whether both bits 2 and 3 are set, we can use:

if (x & (4|8) == (4|8)) { 
  // Do something
}

The bitwise AND operator is also used to set individual bits in a number to false; see Section 15.2.4, "Bitwise NOT" later in this chapter.

15.2.2. Bitwise OR

The Bitwise OR operator (|) combines the bits of two numbers by performing a logical OR operation on each bit of the numbers. Like bitwise AND, bitwise OR returns the result of the combination as a number. A bitwise OR expression takes the form:

operand1 | operand2

The operands can be any numbers, but they are converted to 32-bit binary integers before the operation occurs. The fractional portion of an operand, if any, is discarded.

Note that the bitwise OR uses the single-character operator, |, and operates on individual bits within a number, whereas the logical OR operator discussed in Chapter 5, "Operators" uses the two-character operator, ||, and treats each operand as a whole.

Each bit in the result is determined by taking the logical OR of the bits of the two operands. Therefore, if a bit is set to 1 in either (or both) operand1 or operand2, that bit will be set to 1 in the result. Compare the following pseudoexamples to those shown earlier for the bitwise AND operator.

In this example, only bit 1 is set to in the result because bit 1 is in both operands. The other bits are set to 1:

1101
| 0100
------
  1101

In this example, all bits are set to 1 in the result because each bit contains a 1 in at least one of the two operands:

1101
| 1011
------
  1111

In real code, this reads:

13 | 4    // Result is 13
13 | 11   // Result is 15

In practice, we often use bitwise OR to combine multiple numbers that represent individual options into a single numeric value that represents all the options of a system. For example, the following code combines bit 2 (value 4) and bit 3 (value 8):

options = 4 | 8;

The bitwise OR operator is also used to set an option to true in an existing value. The following example sets the option represented by bit 3 (value 8) to true. If the value in bit 3 is already true, it is untouched:

options = options | 8;

Multiple bits can also be set at once:

options = options | 4 | 8;

15.2.3. Bitwise XOR

We're officially getting into weird punctuation symbols for our operators. The bitwise XOR (eXclusive OR) operator is the caret symbol, ^ (created using Shift-6 on most keyboards). A bitwise XOR expression takes the form:

operand1 ^ operand2

The operands can be any numbers, but they are converted to 32-bit binary integers before the operation occurs. The fractional portion of an operand, if any, is discarded.

The bitwise XOR operator differs from the bitwise OR operator in that the result contains a 0, not a 1, for any bit containing a 1 in both its operands. In other words, the XOR result contains a for any bits that are the same in both operands and contains a 1 for any bits that differ between the two operands.

In this example, bits and 3 match in both operands, so those bits are set to in the result. Bits 1 and 2 differ in the two operands, so they are set to 1 in the result:

1011
^ 1101 
------
  0110

In this example, all the bits match in both operands, so the result is all zeros:

0010
^ 0010
------
  0000

In this example, bits 0, 2, and 3 differ in the two operands, so those bits are set to 1 in the result. Bit 1 is the same in both operands, so it is set to in the result:

0110
^ 1011
------
  1101

Translated to decimal numbers, the preceding examples become:

11 ^ 13    // Result is 6
2 ^ 2      // Result is 0
6 ^ 11     // Result is 13

The bitwise XOR operator is typically used to toggle options between 1 and (true and false). To toggle the option indicated by bit 2 (whose value is 4), we could use:

options = options ^ 4;

15.2.4. Bitwise NOT

Unlike bitwise AND, OR, and XOR, which all produce a number resulting from two other numbers, bitwise NOT changes the bits of a single number. It uses the tilde symbol (~) found in the upper left of most keyboards and takes the form:

~operand

The operand can be any number, but it is converted to a 32-bit binary integer before the operation occurs. Any fractional portion of the operand is discarded.

Bitwise NOT simply inverts the bits in its operand. For example:

~00000000000000000000000000000010  
  // Result is 11111111111111111111111111111101

~11111111111111111111111111111010
  // Result is 00000000000000000000000000000101

which, in decimal, read:

~2    // Result is -3. See the following explanation.
~-6   // Result is 5. See the following explanation.

It's impractical to go into a lesson on negative binary-number representation systems here, but advanced programmers should note that bitwise operations represent negative binary integers using the twos-complement system. To those unfamiliar with this notation, simply remember that the return value of a bitwise NOT operation is one less than the value obtained by taking the negative of the original operand. For example:

~-10  // Change the sign of -10 to 10, then subtract 1. Result is 9.

The bitwise NOT operator is typically used with the bitwise AND operator to clear specific bits (i.e., set them to 0). For example, to clear bit 2, we could use:

options = options & ~4;

The expression ~4 returns a 32-bit integer containing all 1s, except for a in bit 2. By bitwise ANDing that number with the options variable, options' bit 2 is cleared and other bits are left unchanged. The preceding can be written more succinctly as:

options &= ~4;

The same technique can be used to clear multiple bits at once; the following example clears bits 2 and 3:

options &= ~(4 | 8);

15.2.5. The Bitwise Shift Operators

As we've seen, bitwise programming treats binary numbers as a series of switches. It's frequently useful to move those switches around. For example, if we have bit on and we decide we want to turn it off and turn bit 2 on, we could simply move bit left two places. Or if we want to know whether or not the bit 5 of a number is on, we could move that bit right five places and then check bit 0's value. The bitwise shift operators let us perform such movements.

Bitwise shift operators also allow us to rapidly multiply and divide by multiples of 2. If you wanted to divide a decimal (base-10) number by 10, you could simply shift the decimal point one position to the left. Likewise, to multiply by 10, you simply shift the decimal place one position to the right, and to multiply by 10³ (i.e., 1000) you would shift the decimal place three positions to the right. The bitwise shift operators let us perform an analogous operation with binary numbers. Shifting bits to the right divides a number by 2 for each position shifted. Shifting bits to the left multiplies a number by 2 for each position shifted.

15.2.5.1. Signed right shift

The signed right shift operator can be used to divide a number by some power of 2. It uses the >> symbol (created using two successive greater-than signs) and takes the general form:

operand >> n

where n specifies how many places to the right to shift operand 's bits. The result is equivalent to dividing operand by 2ⁿ. The remainder, if any, is discarded. Here's how it works:

All bits are shifted right by the number of positions specified by n. Any bits shifted off the righthand side of the number are discarded. New bits are added on the left side to fill the void created by the shift operation. If operand is positive, the newly added bits are 0s. If operand is negative, the newly added bits are 1s (because negative numbers are represented in twos-complement). Here's an example in pseudocode:

// The right-most bit (0) is lost and 0s fill in on the left
// The result is 00000000000000000000000000000100
00000000000000000000000000001000 >> 1

Shifting a number right one bit is like dividing it by 2¹ (i.e., 2). In decimal this reads:

8 >> 1  // The result is 4

Note that any remainder is discarded:

9 >> 1 // The result is still 4

For negative numbers, >> still divides by 2 for each bit position shifted:

-16 >> 2  // The result is -4 (-16 divided by 2 squared)

15.2.5.2. Unsigned right shift

The unsigned right shift operator, created using three successive greater-than signs (>>>), takes the form:

operand >>> n

It works like the signed right shift operator except that bits vacated by the shift are always filled with 0s (regardless of whether operand is positive or negative). For positive numbers, it is no different than the signed right shift operator.

15.2.5.3. Left shift

The left shift operator can be used to multiply a number by some power of 2. It uses the << symbol (created using two successive less-than signs) and takes the general form:

operand1 << n

where n specifies how many places to the left to shift operand 's bits. The result is equivalent to multiplying operand by 2ⁿ. Here's how it works:

All bits are shifted left by the number of positions specified by n. Any bits shifted off the lefthand side of the number are discarded. The empty bits created by the shift on the right are filled in with 0s. For example:

01000000000000000000000000001001 << 4
  // Result is 00000000000000000000000010010000

Shifting a number left by 4 bits is equivalent to multiplying it by 2⁴ (i.e., 16). In decimal, this reads:

9 << 4  // Result is 9 * 16, i.e., 144

Notice that in prior examples, we "manually" specified the value associated with a particular bit: 1 for bit 0, 2 for bit 1, 4 for bit 2, 8 for bit 3, and so on. The left shift operator is very handy for calculating a bit position's equivalent value:

(1 << 0)    // Bit 0 equals 1
(1 << 1)    // Bit 1 equals 2
(1 << 2)    // Bit 2 equals 4
(1 << 3)    // Bit 3 equals 8
(1 << 15)   // Much easier than remembering bit 15 equates to 32768!

The left shift operator is also handy for dynamically selecting bits by numeric index rather than bit value. Example 15-1 counts up all the 1s in a number.

Example 15-1. Using Left Shift to Count Bits That Are Set

myNumber = 27583;  // The number whose 1s we'll count
count = 0;
for (var i=0; i < 32; i++) {
  if (myNumber & (1 << i)) {
    count++;
  }
}

Example 15-2 is a variation on Example 15-1 using the right shift operator. We can repeatedly right-shift the value and check its rightmost bit (bit 0), instead of using the left shift operator to calculate the bit value associated with each bit.

Example 15-2. Counting Bits Using Right Shift

myNumber = 27583;
count = 0;
temp = myNumber;    // Make a copy for temporary use
for (var i = 0; i < 32; i++) {
  if (temp & 1) {
    count++;
  }
  temp = temp >> 1;
}

The variable myNumber is copied into the temporary variable temp because the right shift is destructive; the variable temp ends up with a final value of 0.

15.2.6. Bitwise Operations Applied

We began our look at bitwise operators using the example of a Flash site that sells cars. Now that we've seen how bitwise operators work, let's use them to determine the cost of a car, as shown in Example 15-3. You can download the .fla file for this example from the online Code Depot.

Example 15-3. Real-Life Bitwise Operations

// First, set the options (usually by adding and subtracting numbers
// based on the selections of a fill-in form, but we hardcode them here)
var hasAirCon   = (1<<0)    // Bit 0: 0 means no, 1 means yes
var hasCDplayer = (0<<1)    // Bit 1: 0 means no, 2 means yes
var hasSunRoof  = (1<<2)    // Bit 2: 0 means no, 4 means yes
var hasLeather  = (1<<3)    // Bit 3: 0 means no, 8 means yes

// Now combine the options into a single number using bitwise OR
var carOptions = hasAirCon | hasCDplayer | hasSunRoof | hasLeather;

// Here's a function that calculates the price
function totalPrice(carOptions) {
  var price = 0;
  if (carOptions & 1) {  // If the first bit is set
    price += 1000;       // add $1000
  }
  if (carOptions & 2) {  // If the second bit is set
    price += 500;        // add $500
  }
  if (carOptions & 4) {  // If the third bit is set
    price += 1200;       // add $1200
  }
  if (carOptions & 8) {  // If the fourth bit is set
    price += 800;        // add $800
  }

  return price;
}

// Everything's set to go: let's call the function and see if it works!
trace(totalPrice(carOptions));  // Returns 3000. Cool...

To avoid hardcoded bit values throughout your code, it's good practice to store the bit values corresponding to specific options in variables, such as:

var airConFLAG   = 1 << 0;  // Bit 0, whose value is 1
var cdPlayerFLAG = 1 << 1;  // Bit 1, whose value is 2
var sunroofFLAG  = 1 << 2;  // Bit 2, whose value is 4
var leatherFLAG  = 1 << 3;  // Bit 3, whose value is 8

Reader Exercise: Rewrite Example 15-3 using variables and the left shift operator instead of hardcoded bit values to represent the options.

15.2.6.1. Why bitwise?

Although Example 15-3 would be easier to understand as a series of Boolean operations, bitwise operations are extremely fast and compact. Anytime we can speak to a computer in its native binary tongue, we save room and gain speed.

For the sake of comparison, consider a situation in which we're tracking a user's profile, and each user has 32 settings that can be on or off. In a normal database, we'd need 32 fields for each user. If we have a million users, that's a million copies of 32 fields. But when we use bitwise programming we can store the 32 settings in a single number, requiring only one field in the database for each user! Not only does this save disk space, but every time we access a user's profile, we need transfer only a single integer, not 32 Boolean values. If we are processing millions of transactions, saving a few milliseconds per transaction can measurably improve system performance.

For further study, see Gene Myers' excellent article for C programmers, Becoming Bit Wise, posted at http://www.cscene.org /CS9/CS9-02.html.


15. Advanced Topics		15.3. Advanced Function Scope Issues

15.2. Bitwise Programming