Computer Science › Section C · Data manipulation › Topic C.6

Programming data manipulation

Everything Sparrow does with masks, shifts and jumps, Python can do in a line or two. Seeing the two side by side shows what a high-level language hides from you, and where the hidden details still leak through.

What Python hides

A Python statement such as total = price - discount must still become machine instructions: loads, a subtraction and a store, much like the Sparrow programs of this section. One statement may become one machine instruction or hundreds, and the Python interpreter handles that on whatever processor you have, RISC or CISC. You never see registers or addresses, yet statements still run one after another, just as instructions do. The examples here use Python 3 and build on "Data and programming", which showed that 0b11111111, 0xFF and 255 are three ways of writing the same int.

Bitwise operators

Python has an operator for each instruction in "Arithmetic, logic, shift, and rotate instructions": & for AND, | for OR, ^ for XOR, ~ for NOT, and << and >> for shifts, with the number of places on the right. So 0b1100 & 0b1010 is 8, 0b1100 | 0b1010 is 14 and 0b1100 ^ 0b1010 is 6, while 0b00111100 >> 2 is 15. Python prints results in decimal unless asked otherwise. bin(8) gives '0b1000', dropping leading zeros, while format(8, '08b') gives '00001000', padded to the eight digits you would see in a register. There is no rotate operator; a rotation must be built from two shifts and an OR.

Integers with no fixed width

A Sparrow register has exactly 8 bits, but a Python int grows as needed. So with x = 0b10110100, which is 180, x << 1 gives 360, not the 104 an 8-bit register would keep. To imitate a register, mask the result: (x << 1) & 0xFF gives 104. NOT behaves oddly for the same reason. Python treats an int as if it had endlessly many sign bits in two's complement, so ~5 is −6, not 250. Masking fixes that too: ~0b00001111 & 0xFF is 240, which is 0b11110000. Right shifts of negative numbers are arithmetic, so −76 >> 2 is −19, matching the arithmetic shift from the previous topic.

Worked example: packing a colour

Colours are often stored as three bytes, red, green and blue, in one 24-bit number. 1. Pack them: with red, green, blue = 255, 128, 0, the expression (red << 16) | (green << 8) | blue moves red into the top byte and green into the middle one, giving 0xFF8000, which is 16744448. 2. Unpack a colour c = 0x3366CC: c >> 16 gives the red byte, 51. 3. (c >> 8) & 0xFF gives green, 102: the shift brings the middle byte to the bottom and the mask removes red. 4. c & 0xFF gives blue, 204. Check: 0x33 = 51, 0x66 = 102 and 0xCC = 204, so each byte came back unchanged.

Worked example: a bit-testing function

Write a function that reports whether one bit of a value is 1. def bit_is_set(value, position): followed by the indented line return ((value >> position) & 1) == 1. 1. The shift moves the chosen bit into position 0. 2. The mask & 1 clears every other bit, leaving 0 or 1. 3. The comparison turns that into False or True. Check with the light bit map from the previous topic, 0x96 = 10010110: bit_is_set(0x96, 3) returns False and bit_is_set(0x96, 4) returns True, matching the bits read from the right. On Sparrow the same job took a SET for the mask, an AND and a conditional jump.

Control structures become jumps

Python's if and while are built from the conditional and unconditional jumps of "Program execution and the machine cycle". An if statement is carried out as a test and a conditional jump over its indented body when the condition is false. A while loop tests at the top, jumps past the loop when the test fails, and ends its body with a jump back to the test. Take count = 5, total = 0, then while count > 0: with the body total = total + count and count = count - 1. It gives 15, like the Sparrow loop, whose conditional jump, ADD, SUB and unconditional jump did the same four jobs.

Functions are jumps that come back

print(), bin() and max() are functions: named groups of instructions, run by writing the name and arguments in parentheses. A call jumps to the function's code, runs it with the arguments plugged into its parameters, and then returns to the point just after the call. Some functions hand back a value, so max(4, 9, 2) can sit inside an expression and gives 9. Others, such as print(), are used for their effect and return the special value None, so r = print('hi') leaves r holding None. You can define your own with def, as the bit-testing example did; "Procedural units: functions and parameters" covers this fully.

Library modules

Beyond its few dozen built-in functions, Python comes with a standard library of modules, collections of ready-made functions. An import statement makes one available, and you call its functions with the module name, a full stop and the function name. After import math, math.sqrt(2) gives about 1.414, math.floor(7.8) gives 7 and math.gcd(12, 18) gives 6. The module also holds constants such as math.pi. A library function is usually safer than your own version, because many people have already tested it.

Input and output

Programs reach the keyboard and screen through functions, not hardware. print() sends text out; input() shows an optional prompt, waits for the user to press Enter, and returns what was typed. Behind the scenes they ask the operating system to talk to device controllers, as in "Communicating with other devices". One rule causes endless bugs: input() always returns a string. If the user types 12 into n = input('How many? '), then n * 2 is '1212', because * repeats a string. Convert first with int() or float(), as "Data and programming" showed: int(input('How many? ')) * 2 gives 24.

Worked example: a reading-time script

Estimate how long a text takes to read. Line 1: def reading_seconds(words, wpm): with the indented body return words * 60 // wpm. Line 2: words = int(input('Number of words? ')). Line 3: wpm = int(input('Words per minute? ')). Line 4: total = reading_seconds(words, wpm). Line 5: print('Reading time:', total // 60, 'min', total % 60, 's'). Run it with 2600 words at 240 words per minute: 1. The function computes 2600 × 60 = 156,000, then 156,000 // 240 = 650 seconds. 2. 650 // 60 = 10 minutes and 650 % 60 = 50 seconds. 3. The output is Reading time: 10 min 50 s. Check: 10 × 60 + 50 = 650.

Common mistakes to avoid

First, writing ^ for a power; in Python it is XOR, and powers use **. Second, forgetting that Python ints have no fixed width, so a left shift never overflows; mask with & 0xFF to get an 8-bit result. Third, expecting bin() to show leading zeros; use format(value, '08b'). Fourth, forgetting that + is done before <<, so 1 << 2 + 1 is 8; use parentheses. Fifth, doing arithmetic on the string returned by input() without converting it.

Key takeaways

Python statements become machine instructions, but the interpreter hides registers, addresses and the processor type. The operators &, |, ^, ~, << and >> perform the ALU's logic and shift operations. Python ints have no fixed width, so mask with & 0xFF to imitate an 8-bit register. Shifts and masks pack and unpack fields, such as the bytes of a colour. if and while are built from conditional and unconditional jumps, and a function call jumps away and returns. Library modules add tested functions. input() always returns a string.

Flashcards

Flashcard

&

Python bitwise AND

0b1100 & 0b1010 is 8.

Test your understanding

Question 1 of 5

What does print(0b1101 ^ 0b0110) display in Python 3?

Question 2 of 5

With x = 0b11110000, what does print((x << 2) & 0xFF) display?

Question 3 of 5

Why does print(~15) display −16 rather than 240?

Question 4 of 5

A colour is stored as c = 0x40A0E0, with red in the top byte, then green, then blue. What does (c >> 8) & 0xFF give?

Question 5 of 5

A script runs n = input('How many? ') and the user types 12. What is n * 2?

← Previous topicNext topic →