Computer Science › Section C · Data manipulation › Topic C.4
Arithmetic, logic, shift, and rotate instructions
The ALU does more than add. With a handful of logic, shift and rotate operations a program can test a single bit, switch it on or off, multiply by powers of two, and pack several small values into one byte.
Three families of ALU instructions
The arithmetic/logic group of instructions, introduced in "Machine language", splits into three families. Logic operations combine bit patterns with AND, OR and XOR. Shift and rotate operations slide the bits of a register left or right. Arithmetic operations add, subtract and, on many machines, multiply and divide. Sparrow's table gives 0x7RST AND, 0x8RST OR and 0x9RST XOR (register R gets S combined with T), 0xAR0N to rotate R right N places, and 0xBR0N and 0xCR0N to shift R left or right N places, filling with 0s. Bits are numbered from 0 at the right-hand end of a byte to 7 at the left.
Logic operations work column by column
AND, OR and XOR were defined for single bits in "Bits, gates, and flip-flops": AND gives 1 only when both inputs are 1, OR gives 1 when at least one is, and XOR gives 1 when exactly one is. A logic instruction applies the rule to each column of two bytes separately, which is why these are called bitwise operations. Take 10110110 and 01101100. AND gives 00100100, OR gives 11111110 and XOR gives 11011010. No column affects any other, so there is no carrying as there is in addition.
Masks: clearing, setting and flipping bits
To change some bits of a byte and leave the rest alone, use a second operand, called a mask, that chooses which bits are affected. AND with a mask clears bits: where the mask has 0 the result is 0, and where it has 1 the original bit is copied, so AND with 11110000 keeps the left half and clears the right. OR sets bits: where the mask has 1 the result is 1, and elsewhere the original is copied. XOR flips bits: where the mask has 1 each bit is inverted, so XOR with 11111111 complements the whole byte. To test one bit, AND with a mask holding a single 1; the result is zero exactly when that bit was 0, and a conditional jump can then act on it.
Bit maps and letter case
Masks are most useful with a bit map, a pattern in which each bit records whether something is present or switched on. Eight bits can record which of eight seats are booked. Masks also explain a neat feature of ASCII, from "Representing text, images, and sound as bits". Each capital letter's code differs from its lower-case partner only in bit 5, worth 0x20: "A" is 0x41 and "a" is 0x61. So, for a letter, AND with 0xDF (11011111) forces upper case, OR with 0x20 forces lower case, and XOR with 0x20 swaps the case.
Worked example: a bit map of lights
A byte records eight lights, bit 0 to bit 7, and currently holds 10010110, or 0x96. 1. Is light 3 on? AND with 00001000 gives 00000000, so light 3 is off. 2. Switch light 0 on: OR with 00000001 gives 10010111, or 0x97. 3. Switch light 7 off: AND with 01111111 gives 00010111, or 0x17. 4. Reverse every light: XOR with 11111111 gives 11101000, or 0xE8. Check: in each step only the bits under a 1 in an OR or XOR mask, or under a 0 in an AND mask, changed. On Sparrow, with the byte in R1 and the mask in R2, step 2 is the single instruction 0x8112.
Rotating and shifting
Shift a byte one place right and the rightmost bit falls off while a gap opens on the left. A rotation, or circular shift, puts the fallen bit into the gap, so no bit is ever lost: rotating a byte right eight times restores it, and on 8 bits a right rotation of 3 equals a left rotation of 5. A logical shift discards the fallen bit and fills the gap with 0. An arithmetic right shift fills the gap with a copy of the leftmost bit, the sign bit in two's complement, so negative numbers stay negative. Just as moving decimal digits left multiplies by ten, a binary left shift of N places multiplies by \(2^N\), provided no 1 bits fall off, and a logical right shift divides an unsigned number by \(2^N\), dropping the remainder.
Worked example: one byte, three operations
Register R4 holds 10110100, or 0xB4. As an unsigned number that is 180; in two's complement it is −76. 1. Rotate right 3 (0xA403): the three right-hand bits, 100, wrap round to the left, giving 10010110, or 0x96. 2. Starting again from 0xB4, logical shift left 1 (0xB401): every bit moves left and a 0 enters at the right, giving 01101000, or 0x68. The leftmost 1 fell off, so 180 × 2 = 360 did not fit, and 360 − 256 = 104 = 0x68 was left. 3. Logical shift right 2 (0xC402) gives 00101101, or 0x2D, which is 45 = 180 ÷ 4. Check: an arithmetic right shift of 2 would give 11101101, which is −19 = −76 ÷ 4.
Arithmetic: one name, several operations
Small processors can manage with few arithmetic instructions. Subtraction can be done by negating in two's complement and adding; multiplication is repeated addition, or adding shifted copies; division is repeated subtraction. One name can hide very different work. Adding two's complement integers is plain column addition with carries. Adding floating-point values, from "Storing fractions: floating-point notation", means separating each mantissa and exponent, shifting one mantissa until the exponents match, adding, and then normalising the result, which is why machines provide separate integer and floating-point add instructions. And 8-bit integer addition can overflow: 0x64 + 0x50 is 100 + 80, but the result 0xB4 reads as −76, because 180 does not fit.
Worked example: multiplying by ten
Sparrow has no multiply instruction. Write a program that multiplies the unsigned value in cell 0xA0 by 10 and stores the result in 0xA1. The idea: \(10x = 8x + 2x\). 1. 0x11A0 loads the value into R1. 2. 0x4021 copies R1 into R2. 3. 0xB103 shifts R1 left 3 places, making 8x. 4. 0xB201 shifts R2 left 1 place, making 2x. 5. 0x5312 adds them into R3. 6. 0x33A1 stores R3 in cell 0xA1. 7. 0x0000 halts. Check with 0x0D, which is 13: 8 × 13 = 104 and 2 × 13 = 26, and 104 + 26 = 130 = 0x82. A simulated run leaves 0x82 in cell 0xA1. Any value above 25 would overflow, since 260 needs 9 bits.
Common mistakes to avoid
First, carrying between columns in AND, OR or XOR; logic operations treat each column separately. Second, using the wrong kind of mask: AND clears where the mask has 0s, while OR sets and XOR flips where the mask has 1s. Third, confusing rotation, which loses no bits, with a logical shift, which discards them. Fourth, using a logical right shift on a negative two's complement number, which turns it into a positive one. Fifth, forgetting that a left shift overflows once a 1 falls off the end.
Key takeaways
Logic instructions apply AND, OR or XOR to each bit position separately. A mask picks the bits to change: AND clears, OR sets and XOR flips, and AND with a single 1 tests one bit. Bit maps store many yes-or-no facts in one byte. Rotation wraps bits round; a logical shift fills with 0s; an arithmetic right shift copies the sign bit. A left shift of N places multiplies by 2ᴺ and a right shift divides, if nothing overflows. Integer and floating-point addition need different circuits, and fixed-size addition can overflow.
Flashcards
Flashcard
Applies a logic operation to each bit position separately
Test your understanding
Question 1 of 5
What is 11001010 XOR 10011100?
Question 2 of 5
A byte is a bit map. Which operation switches bit 4 off while leaving every other bit unchanged?
Question 3 of 5
Register R6 holds 01101001. What does it hold after the Sparrow instruction 0xA602, a right rotation of 2?
Question 4 of 5
An 8-bit register holds 00011011, which is 27. What does a logical left shift of 2 places give?
Question 5 of 5
Sparrow adds 0x70 and 0x30 as 8-bit two's complement numbers. What happens?
