Bitwise operations and characters

Masks with AND, OR and XOR, logical, arithmetic and circular shifts, and characters as codes in ASCII and Unicode.

A7.5Data representationA level30 min

A byte is often not one number but several small fields packed together: a status byte with a flag per bit, a colour with red, green and blue squeezed into 16 bits, a character code whose bits mean something. Bitwise operations work on those bits directly. This lesson uses them to pick bytes apart, then looks at characters, where the same tricks turn a digit character into its value.

AND, OR and XOR on whole bytes

At GCSE you met AND, OR and XOR as gates on single bits. A bitwise operation applies the gate to each pair of bits in the same position. The second operand is called a mask: it chooses which bits are affected.

• AND (& in Python): a 1 in the mask keeps a bit and a 0 clears it, so AND is for testing or clearing bits. 10110010 AND 00000010 gives 00000010, so bit 1 is set.
• OR (the vertical bar in Python): a 1 in the mask sets a bit and a 0 leaves it alone, so OR is for setting bits. 10110010 OR 00000001 gives 10110011.
• XOR (^ in Python): a 1 in the mask flips a bit and a 0 leaves it alone, so XOR is for toggling bits. 10110010 XOR 11110000 gives 01000010.

NOT (~ in Python) flips every bit. In Python ~ works on its unlimited-width integers, so mask the result back to 8 bits: ~x & 0xFF.

status = 0b10110010
BUMPED = 1 << 1           # a mask with only bit 1 set: 00000010
LOW_BATTERY = 1 << 0      # 00000001

print(format(status & BUMPED, "08b"), "bumped" if status & BUMPED else "clear")
status = status | LOW_BATTERY        # set bit 0
status = status & ~BUMPED & 0xFF     # clear bit 1
status = status ^ 0b11110000         # flip the top four bits
print(format(status, "08b"))

Run this in the simulator

Shifts

A shift moves every bit left or right.

• Logical shift left by n: bits move left, 0s come in on the right, and bits pushed off the left are lost. For unsigned values it multiplies by 2ⁿ, if nothing is lost.
• Logical shift right by n: bits move right, 0s come in on the left. For unsigned values it divides by 2ⁿ, throwing away the remainder.
• Arithmetic shift right: the sign bit is copied in on the left instead of a 0, so a two's complement number keeps its sign. 11110100 (-12) shifted right once is 11111010 (-6).
• Circular shift (rotate): the bits pushed off one end come back in at the other. 10110010 rotated left once is 01100101.

In Python << and >> shift; >> on a negative integer is arithmetic. Python integers have no fixed width, so mask with & 0xFF to keep a result to 8 bits.

Shifts and masks together extract a field: shift right until the field is at the bottom, then AND with a mask as wide as the field. The robot's LED takes 8 bits per colour, but small displays often store a colour as RGB565: 5 bits red, 6 bits green, 5 bits blue in one 16-bit value.

bit  15 14 13 12 11 | 10  9  8  7  6  5 |  4  3  2  1  0
     r  r  r  r  r  |  g  g  g  g  g  g |  b  b  b  b  b

Red is (colour >> 11) & 0b11111. To widen a 5-bit field to 8 bits, shift it left 3 and fill the three new low bits with its own top three bits, so full brightness 11111 becomes 11111111 rather than 11111000.

Characters

A character is stored as a number, its character code, and a character set is the agreed table of codes.

ASCII uses 7 bits: 128 codes, enough for English letters, digits, punctuation and control codes such as newline. Extended 8-bit versions add another 128 characters, but different countries filled those differently, so text moved between systems came out garbled.

Unicode gives every character in every writing system its own code point, more than a million possible. Its first 128 code points are the same as ASCII, so ASCII text is valid Unicode. Code points are stored with an encoding: UTF-8 uses 1 to 4 bytes per character (1 byte for ASCII), UTF-16 uses 2 or 4, and UTF-32 always uses 4.

for ch in ["A", "é", "€", "🤖"]:
    print(ch, ord(ch), len(ch.encode("utf-8")), "bytes in UTF-8")

Run this in the simulator

ASCII was arranged so that bit patterns help. Capital A is 65 (1000001) and small a is 97 (1100001): they differ only in the bit worth 32, so XOR with 32 swaps the case of a letter.

A digit as a character and as a number

The character 7 and the number 7 are different bit patterns:

The digit characters 0 to 9 are codes 48 to 57, so the character's low four bits are the digit's value. Masking with 00001111 (or subtracting 48) turns the character into the number. That is exactly what int("7") does for you, and why "7" + "1" is "71", not 8: the program is joining codes, not adding values.

reading = "0451"                   # a distance arriving as text from a serial port
value = 0
for ch in reading:
    value = value * 10 + (ord(ch) & 0x0F)    # the character code's low nibble is the digit
print(value + 1)
print(chr(ord("b") ^ 32))           # swap case with the bit worth 32

Run this in the simulator

Task: unpack a colour

colour holds 0xFD20, a 16-bit RGB565 colour: bits 15 to 11 are red, bits 10 to 5 green, bits 4 to 0 blue. Using only shifts (>>, <<) and masks (&, |):

1. Extract the fields into r5 (0 to 31), g6 (0 to 63) and b5 (0 to 31) and print r5=<r5> g6=<g6> b5=<b5>.
2. Widen each to 8 bits (0 to 255): r8 is r5 shifted left 3, ORed with r5 shifted right 2; g8 is g6 shifted left 2, ORed with g6 shifted right 4; b8 is made like r8. Print rgb=<r8>,<g8>,<b8> with no spaces.
3. Light the LED with led(r8, g8, b8).

Do not use //, %, bin or format, and do not type the answers.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

colour = 0xFD20

r5 = 0
g6 = 0
b5 = 0
print("r5=" + str(r5), "g6=" + str(g6), "b5=" + str(b5))

Challenges

1. Go the other way: pack (255, 128, 64) into RGB565 and print it in hex.
2. Write rotate_left(byte, n) for an 8-bit circular shift.
3. Why does masking with 00001111 not work for turning the character A into a number?