Binary Arithmetic and Shifts
Adding binary numbers with carries, recognising overflow, and binary shifts, including exactly what happens to the bits that fall off the end.
Binary addition
There are only four rules, and every binary addition uses them.
0 + 0 = 0
1 + 0 = 1
1 + 1 = 0 carry 1
1 + 1 + 1 = 1 carry 1Work from the right hand column, exactly as in denary, carrying into the next column to the left.
carry 1 1 1 1 1
0 1 1 0 1 1 0 1 = 109
+ 0 0 1 1 0 1 1 0 = 54
-------------------
1 0 1 0 0 0 1 1 = 163AQA requires you to be able to add up to three binary numbers. The method is unchanged, but three ones in a column give 1 carry 1, and three ones plus a carry give 0 carry 2, which means writing a 1 into each of the next two columns. Doing the addition in two stages, adding the first two numbers and then adding the third to that result, is usually safer and is fully acceptable.
It is the difference between a method mark and nothing. Examiners can see where a correct method went wrong only if the working is on the page.
Overflow
Overflow happens when the result of a calculation needs more bits than are available.
1 1 0 0 0 0 0 0 = 192
+ 1 0 0 0 0 0 0 0 = 128
-------------------
1 0 1 0 0 0 0 0 0 = 320, which needs nine bitsWith only eight bits available, the carry out of the leftmost column has nowhere to go. It is lost, and the value actually stored is 01000000, which is 64. The program has not crashed and nothing has been reported: it simply now holds a wrong answer.
Overflow occurs when the result of an addition is too large to be stored in the number of bits available, so a carry is produced out of the most significant bit and the stored result is incorrect.
That last clause matters. Plenty of answers say the number is too big. Fewer say that the consequence is a wrong value being stored and used, which is what makes overflow dangerous rather than merely inconvenient.
- Adding 1111 1111 and 0000 0001 produces a ninth bit. The register only keeps eight, so the answer shown is 0000 0000.
- An odometer is the same: 999 plus 1 gives 000 because the 1000 does not fit in three wheels.
- The answer is wrong, the carry flag is set to record it, and it is avoided with more bits or a check.
Binary shifts
A binary shift moves every bit a given number of places left or right.
Left shift
A left shift multiplies by 2 for each place shifted. Zeros come in on the right, and bits shifted off the left hand end are lost.
00001011 = 11
shift left 1
00010110 = 22
shift left 2 more
01011000 = 88Eleven times two is 22, and 22 times four is 88. The pattern holds until a 1 falls off the left hand end, at which point the value is wrong, and that is overflow again.
Right shift
A right shift divides by 2 for each place shifted. Zeros come in on the left, and bits shifted off the right hand end are lost.
00011001 = 25
shift right 1
00001100 = 12Twenty five divided by two is 12.5, but there is nowhere to store the half. The 1 that fell off the right hand end is gone, so the result is 12. The division is integer division, and the lost bit is the remainder.
A full mark answer states that bits shifted out of the register are discarded and zeros are introduced at the other end, and that a right shift therefore loses precision. Saying only "it divides by two" is a partial answer.
Why shifts are used
Shifting is far cheaper for a processor than a general multiply or divide, because it is a single hardware operation rather than a repeated one. Compilers replace multiplication by a power of two with a shift for exactly that reason.
- A left shift moves every bit one column to the left, which doubles it. A 0 fills the gap on the right.
- A right shift moves bits to the right, which halves them each place. Shifting by 2 divides by 4.
- In a fixed number of bits a 1 can be pushed off the end and lost, which makes the answer wrong.
Key terms you must be able to define
- Binary addition
- Adding binary numbers column by column from the right, carrying into the next column.
- Carry
- A 1 passed into the next column to the left when a column total is too large for one bit.
- Overflow
- A result too large to be stored in the number of bits available, so the stored value is wrong.
- Most significant bit
- The leftmost bit, which has the largest place value.
- Least significant bit
- The rightmost bit, which has a place value of 1.
- Binary shift
- Moving every bit in a value a number of places left or right.
- Left shift
- A shift towards the most significant bit, multiplying by two for each place.
- Right shift
- A shift towards the least significant bit, dividing by two for each place.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
Three habits separate full marks from most of a mark here.
Write the carry row. Every time, without exception. It is the method mark.
Name the consequence of overflow, not just the cause. The cause is that the result needs more bits. The consequence is that the carry is lost and an incorrect value is stored and then used, with no error reported.
Describe a shift in three parts. What direction the bits move, what fills the vacated positions, and what happens to the bits that leave. An answer with all three cannot be marked down.
Mistakes that cost marks here
- Adding from left to right. Binary addition works from the least significant bit, exactly like denary.
- Writing 1 + 1 = 2 in a column. There is no digit 2 in binary: it is 0 carry 1.
- Saying overflow means the program crashes. It usually does not, which is what makes it dangerous.
- Forgetting that bits shifted off the end are discarded rather than wrapping round.
- Claiming a right shift always divides exactly by two. It performs integer division, and an odd number loses its remainder.
A binary left shift multiplies by two because every place value is twice the one to its right, which is the same reason adding a zero to the end of a denary number multiplies it by ten.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LShows column addition with the carries
- LGives the answer 10000011
Working from the right: 0 plus 1 is 1, 1 plus 0 is 1, 1 plus 1 is 0 carry 1, 0 plus 1 plus the carry is 0 carry 1, 1 plus 0 plus the carry is 0 carry 1, 1 plus 0 plus the carry is 0 carry 1, 0 plus 1 plus the carry is 0 carry 1, and 0 plus 0 plus the carry is 1. The answer is 10000011, which is 131, and 54 plus 77 does equal 131.
- LThe result of the calculation needs more bits than are available
- LA carry is produced out of the most significant bit and is lost
- LThe value stored is therefore incorrect, and usually no error is reported
Overflow occurs when the result of a calculation is too large to be represented in the number of bits allocated to it. A carry is produced out of the most significant bit, and because there is no further bit to hold it the carry is simply discarded. The value that ends up stored is therefore wrong. What makes this a serious problem rather than a minor one is that the program normally carries on running with no error reported at all, so the incorrect value is used in later calculations and the fault can go unnoticed for a long time.
- LGives the result 10110000
- LStates that a left shift of two multiplies by four
- LRelates it to the denary values, 44 becomes 176
Shifting every bit two places to the left and filling the two vacated positions on the right with zeros gives 10110000. Each place a value is shifted left doubles it, because every column is worth twice the one to its right, so a shift of two places multiplies by four. In denary the original value is 44, and 44 times four is 176, which is what 10110000 represents.
- LBits shifted off the right hand end are discarded
- LFor an odd number the least significant bit is a 1, which represents the remainder
- LSo the result is the integer part of the division and precision is lost
A right shift moves every bit one place towards the least significant end, and the bit that moves out of the rightmost position is discarded rather than stored anywhere. For an even number that bit is a 0 and nothing is lost, so the division by two is exact. For an odd number the least significant bit is a 1, and that 1 represents the remainder of the division. Discarding it means the result is the whole number part of the division only, so 25 shifted right by one gives 12 rather than 12.5 and precision has been lost.