Bit manipulation

In high-level programming languages, programmers rarely work directly with binary strings. Bit manipulation lets a programmer work with sets of bits using logical bitwise operations. These operations are directly supported by the processor, which makes them fast and very efficient.

The logical bitwise operators AND, OR, XOR and NOT can be used with a mask to pick out or change specific bits. Binary shifts (logical, arithmetic and cyclic) can be used to move the bits, for example within a register.

A logical bitwise operator works on a single bit (or a set of bits) within a binary string. Bitwise operations are often used in low-level programs to change the contents of registers or memory locations.

For example, in a monitoring and control system, a single 8-bit register or memory location could hold the inputs from eight sensors, or control eight actuators. Logical bitwise operators can be used with a mask to check, set, clear or toggle (flip) each bit, or set of bits, in the string.

A mask is a binary string that is used with a logical bitwise operator to pick out or change a single bit (or set of bits) in another binary string.

For example, each bit in a processor’s status register has its own meaning. Suppose the first bit shows whether the result of an arithmetic operation was zero; this is called the zero flag. That bit can be examined, set or reset using a mask of the same length with a 1 in the position of the zero flag and 0 everywhere else. Here the mask would be 10000000, because the zero flag is in the first position.

The logical bitwise AND operation takes two binary strings of the same length and ANDs each pair of matching bits. The result in each position is 1 if both bits are 1; otherwise it is 0.

AND can be used to find out whether a particular bit (or group of bits) is set (1) or clear (0). It can also be used to clear selected bits, that is, to set them to 0.

Consider a control system that uses an 8-bit register to control eight lights. If the bit for a light is 1, the light is on; if it is 0, the light is off. This register shows that lights 1, 4, 5 and 8 are on and lights 2, 3, 6 and 7 are off:

Lights 3 and 4 are security lights outside the building. To pick out the bits that control these two outside lights, the mask 00110000 is used:

Checking selected bits. To check whether either of the outside lights is on, AND the register with the mask. If the result is not zero (00000000), at least one of those lights is on.

The result is not zero, so at least one outside light is on (light 4).

Clearing selected bits. To turn the outside lights off, AND is used again, but now the mask must have 0 in the positions to clear and 1 everywhere else. So first apply a bitwise NOT to the mask to flip its bits:

Then AND the register with the inverted mask:

Only the bit in position 4 (light 4) has changed. Light 3 was already off, so bit 3 did not need to change. All the other bits keep their original values.

The logical bitwise OR operation takes two binary strings of the same length and ORs each pair of matching bits. The result in each position is 1 if either or both bits are 1; if both bits are 0, the result is 0.

AND with a mask is used to check or clear bits. OR with a mask is used to set one or more bits to 1.

To set (turn on) the outside lights, use the same register, the same mask (00110000) and OR:

The bit in position 3 (light 3) has been set to 1; it was 0. All the other bits are unchanged. Light 4 was already on, so bit 4 did not need to change.

The logical bitwise XOR operation takes two binary strings of the same length and XORs each pair of matching bits. The result in each position is 1 if exactly one of the two bits is 1; if both bits are 0, or both are 1, the result is 0.

XOR with a mask is used to toggle bits: a bit that is 1 becomes 0, and a bit that is 0 becomes 1.

To toggle the outside lights, use the same register, the same mask and XOR:

The bits in positions 3 and 4 have been toggled (flipped). All the other bits are unchanged.

Clearing all the bits. XOR is also an efficient way to set a register to zero. XOR of two bits that are the same gives 0, so XOR the register with a copy of itself:

This usually needs fewer clock cycles and less memory than loading the value zero and saving it to the register.

The logical bitwise NOT operation flips every bit in a binary string: bits that are 0 become 1, and bits that are 1 become 0. For example:

Note There is no NOT instruction in the Cambridge instruction set. To flip every bit of the ACC, use XOR B11111111 (XOR with all 1s). To flip only some bits, XOR with a mask that has 1s in those positions.

A logical left shift moves all the bits in a binary string a given number of places to the left. A left shift by one place means:

• moving all the bits one place to the left
• discarding the most significant (leftmost) bit
• putting a 0 into the empty place on the right

If the string represents a number, each shift one place left multiplies the number by 2. So shifting three places left multiplies the number by 2³ = 8. For example, to multiply 14 by 8, shift its binary value left three times to get 112:

In general, shifting a binary number left by n places multiplies it by 2ⁿ.

A logical right shift moves all the bits a given number of places to the right. A right shift by one place means:

• moving all the bits one place to the right
• discarding the least significant (rightmost) bit
• putting a 0 into the empty place on the left

If the string represents a number, each shift one place right divides the number by 2. In general, shifting a binary number right by n places divides it by 2ⁿ. For example, shifting 01110000 (112) right three places gives 00001110 (14), and 112 ÷ 8 = 14.

Note Bits shifted out at the end are lost. If a 1 is shifted out, the answer is no longer exact: a left shift has overflowed, or a right shift has lost the remainder (for example 7 shifted right one place gives 3).

In the Cambridge instruction set, LSL #n shifts the bits in the ACC n places to the left and LSR #n shifts them n places to the right; zeros are introduced at the other end.

Logical shifts cannot be used to multiply or divide signed numbers, because the sign bit must not simply be shifted like the other bits. If a number is signed, an arithmetic shift must be used.

An arithmetic shift is used when the binary string represents a signed number, stored with the sign as the most significant bit (for example, in two’s complement). It makes sure that shifting does not change the sign by accident: the sign of the number is preserved.

• In an arithmetic right shift, the bits move right and the sign bit is copied into the empty place on the left, so a negative number stays negative. Each place divides the number by 2.
• In an arithmetic left shift, the bits move left and 0s are put in on the right, just as in a logical left shift. Each place multiplies the number by 2, as long as the sign bit does not change. If it would change, the result is too large to store: overflow.

In a cyclic shift, no bits are lost: the bits that are shifted out at one end are moved into the other end of the register.

The syllabus adds these instructions to the instruction set in 4.2. Each row gives the opcode, the operand and what the instruction does:

The same rules apply as in 4.2: only one general purpose register (ACC), IX is the Index Register, <address> can be absolute or symbolic, and #123 is denary, B01001010 is binary and &4A is hexadecimal. Watch the difference: AND #15 uses the number 15, but AND 15 uses the contents of address 15.

Exam questions usually number the bits of a byte from 7 (the most significant bit, on the left, worth 128) down to 0 (the least significant bit, on the right, worth 1). Bit n is worth 2ⁿ, so a mask for bit 2 is 00000100, which is #4.

In a monitoring or control system, each bit of a memory location or register stands for one device: a sensor that is reporting (1 = triggered, 0 = not), or an actuator such as a light, motor or valve that is switched on (1) or off (0). One byte can hold the state of eight devices.

• Monitoring: the program repeatedly reads the byte into the ACC and uses AND with a mask to test the bit for one sensor. A CMP and a conditional jump then decide what to do.
• Control: the program sets a bit with OR and a mask to switch a device on, clears it with AND and an inverted mask to switch it off, or toggles it with XOR. It then stores the byte back so that the device changes.

Using the lights register from earlier, where lights 3 and 4 (mask 00110000) are the outside lights:

// are both outside lights off?
LDD  Lights
AND  B00110000
CMP  #0
JPE  BothOff

// switch both outside lights on
LDD  Lights
OR   B00110000
STO  Lights

// switch both outside lights off
LDD  Lights
AND  B11001111
STO  Lights