Chapter 3: Binary Arithmetic and Bit Operations

Understanding how computers represent data in binary is a prerequisite to writing software that works well on those computers. Of equal importance, of course, is understanding how computers operate on binary data. Exploring arithmetic, logical, and bit operations on binary data is the purpose of this chapter.

3.1 Arithmetic Operations on Binary and Hexadecimal Numbers

Because computers use binary representation, programmers who write great code often have to work with binary (and hexadecimal) values. Often, when writing code, you may need to manually operate on two binary values in order to use the result in your source code. Although calculators are available to compute such results, you should be able to perform simple arithmetic operations on binary operands by hand.

Hexadecimal arithmetic is sufficiently painful that a hexadecimal calculator belongs on every programmer's desk (or, at the very least, use a software-based calculator that supports hexadecimal operations, such as the Windows calculator). Arithmetic operations on binary values, however, are actually easier than decimal arithmetic. Knowing how to manually compute binary arithmetic results is essential because several important algorithms use these operations (or variants of them). Therefore, the next several subsections describe how to manually add, subtract, multiply, and divide binary values, and how to perform various logical operations on them.

3.1.1 Adding Binary Values

Adding two binary values is easy; there are only eight rules to learn. (If this sounds like a lot, just realize that you had to memorize approximately 200 rules for decimal addition!) Here are the rules for binary addition:

• 0 + 0 = 0

• 0 + 1 = 1

• 1 + 0 = 1

• 1 + 1 = 0 with carry

• Carry + 0 + 0 = 1

• Carry + 0 + 1 = 0 with carry

• Carry + 1 + 0 = 0 with carry

• Carry + 1 + 1 = 1 with carry

Once you know these eight rules you can add any two binary values together. Here are some complete examples of binary addition:

 0101          + 0011          ------ Step 1: Add the LO bits (1 + 1 = 0 + carry).              c            0101          + 0011          ------              0  Step 2: Add the carry plus the bits in bit position one (carry + 0 + 1 = 0 +  carry).             c            0101          + 0011         -------             00  Step 3: Add the carry plus the bits in bit position two (carry + 1 + 0 = 0 +  carry).            c            0101          + 0011          ------            000  Step 4: Add the carry plus the bits in bit position three (carry + 0 + 0 = 1).            0101          + 0011          ------           1000 

Here are some more examples:

 1100_1101           1001_1111          0111_0111  + 0011_1011         + 0001_0001        + 0000_1001  -----------         -----------        ------------ 1_0000_1000           1011_0000          1000_0000 

3.1.2 Subtracting Binary Values

Binary subtraction is also easy; like addition, binary subtraction has eight rules:

• ˆ’ 0 = 0

• ˆ’ 1 = 1 with a borrow

• 1 ˆ’ 0 = 1

• 1 ˆ’ 1 = 0

• ˆ’ ˆ’ borrow = 1 with a borrow

• ˆ’ 1 ˆ’ borrow = 0 with a borrow

• 1 ˆ’ ˆ’ borrow = 0

• 1 ˆ’ 1 ˆ’ borrow = 1 with a borrow

Here are some complete examples of binary subtraction:

 0101   0011          ------ Step 1: Subtract the LO bits (1   1 = 0).            0101   0011          ------              0  Step 2: Subtract the bits in bit position one (0   1 = 1 + borrow).            0101   0011             b          ------             10  Step 3: Subtract the borrow and the bits in bit position two (1     b = 0).            0101   0011          ------            010  Step 4: Subtract the bits in bit position three (0   0 = 0).            0101   0011          ------           0010 

Here are some more examples:

 1100_1101           1001_1111          0111_0111   0011_1011   0001_0001   0000_1001  -----------         -----------        -----------   1001_0010           1000_1110          0110_1110 

3.1.3 Multiplying Binary Values

Multiplication of binary numbers is also very easy. It's just like decimal multiplication involving only zeros and ones (which is trivial). Here are the rules you need to know for binary multiplication:

• 0 — 0 = 0

• 0 — 1 = 0

• 1 — 0 = 0

• 1 — 1 = 1

Using these four rules, multiplication is done the same way you'd do decimal multiplication (in fact, if you just follow the rules for decimal multiplication on your binary values you'll actually get the correct results, because the rules for decimal multiplication involving the zero and one digits are identical). Here are some examples of binary multiplication:

 1010       0101      ------- Step 1: Multiply the LO bit of the multiplier times the multiplicand.        1010       0101      -------       1010    (1  1010)  Step 2: Multiply bit one of the multiplier times the multiplicand.        1010       0101      -------       1010    (1  1010)       0000     (0  1010)      -------      01010    (partial sum)  Step 3: Multiply bit two of the multiplier times the multiplicand.        1010       0101      -------     001010    (previous partial sum)      1010      (1  1010)      -------     110010    (partial sum)  Step 4: Multiply bit three of the multiplier times the multiplicand.        1010       0101     --------     110010    (previous partial sum)     0000       (0  1010)     --------    0110010    (product) 

3.1.4 Dividing Binary Values

Like multiplication of binary numbers, binary division is actually easier than decimal division. You use the same (longhand) division algorithm, but binary division is easier because you can trivially determine whether the divisor goes into the dividend during each step of the longhand division algorithm. Figure 3-1 on the next page shows the steps in a decimal division problem.

	(1) 12 goes into 34 two times.		(2) Subtract 24 from 34 and drop down the 105.
	(3) 12 goes into 105 eight times.		(4) Subtract 96 from 105 and drop down the 96.
	(5) 12 goes into 96 exactly eight times.		(6) Therefore, 12 goes into 3456 exactly 288 times.

Figure 3-1: Decimal division (3456/12)

This algorithm is actually easier in binary because at each step you do not have to guess how many times 12 goes into the remainder nor do you have to multiply 12 by your guess to obtain the amount to subtract. At each step in the binary algorithm, the divisor goes into the remainder exactly zero or one times. As an example, consider the division of 27 (11011) by three (11) as shown in Figure 3-2.

	11 goes into 11 one time.
	Subtract out the 11 and bring down the zero.
	11 goes into 00 zero times.
	Subtract out the zero and bring down the one.
	11 goes into 01 zero times.
	Subtract out the zero and bring down the one.
	11 goes into 11 one time.
	This produces the final result of 1001.

Figure 3-2: Longhand division in binary