AP Computer Science Principles · Unit 2 lecture · Part 2 of 11 · 9 min

2.1 Binary numbers: convertingCounting in base 2

Mr. Thompkins
You already know a number system with place values: the one you've used since kindergarten. Binary uses the exact same idea with only two digits. Once you see that, converting is just adding.

Our everyday numbers are base 10, also called decimal. There are ten digits, 0 to 9, and each place is worth ten times the place to its right: ones, tens, hundreds, thousands. The number 4,072 means 4 thousands, 0 hundreds, 7 tens and 2 ones.

Place (base 10)ThousandsHundredsTensOnes
Digit in 4,0724072
Worth4 × 1,0000 × 1007 × 102 × 1
Base 10: each place is worth 10 times the one to its right.
?Wait, what's an exponent again?
An exponent tells you how many times to multiply a number by itself. 2³ means 2 × 2 × 2 = 8. And any number to the power 0 is 1, so 2⁰ = 1. The places in binary are 2⁰, 2¹, 2², 2³: that is, 1, 2, 4, 8.

Binary is base 2. There are only two digits, 0 and 1, and each place is worth twice the place to its right: 1, 2, 4, 8, 16, 32, 64, 128, and so on. The rightmost bit is the ones place. To read a binary number, write the place values over the bits and add up the places that hold a 1.

place value168421
bit10110
adds160420
Binary 10110: 1s in the 16, 4 and 2 places, so 16 + 4 + 2 = 22.

Going the other way, from decimal to binary, use the "biggest power that fits" method. List the powers of 2 up to your number. Starting from the biggest, ask: does it fit in what's left? If yes, write a 1 and subtract it. If no, write a 0. Keep going down to the ones place.

powerfits in what is left?bitleft over
6464 ≤ 77: yes113
3232 ≤ 13: no013
1616 ≤ 13: no013
88 ≤ 13: yes15
44 ≤ 5: yes11
22 ≤ 1: no01
11 ≤ 1: yes10
Converting 77: take out 64, then 8, then 4, then 1. Reading the bit column top to bottom gives 1001101.
?Wait, what does MOD do?
a MOD b gives the remainder when a is divided by b. 22 MOD 2 is 0, because 22 divides evenly by 2. 11 MOD 2 is 1. Any number MOD 2 tells you whether it's even (0) or odd (1), and that's exactly the last bit of its binary form.

A computer would use a different method, and it's worth seeing because it's a tiny algorithm you can trace. Divide by 2 again and again. Each remainder is the next bit, working from the right. Here it is in the exam's pseudocode. INSERT(bits, 1, x) puts x at the front of the list, so the bits come out in the right order.

1n ← 222bits ← []3REPEAT UNTIL (n = 0)4{5  INSERT(bits, 1, n MOD 2)16  n ← (n - n MOD 2) / 227}8DISPLAY(bits)
  1. line 5 The remainder is the next bit, added at the front
  2. line 6 Drop that bit and halve: 22 becomes 11
output › [1, 0, 1, 1, 0]
Decimal to binary by repeated halving.
nn MOD 2bits after INSERTnew n
220[0]11
111[1, 0]5
51[1, 1, 0]2
20[0, 1, 1, 0]1
11[1, 0, 1, 1, 0]0
The trace for n = 22. The remainders, read from the last row up, are 10110.
Pause and think
Without converting all of it, is binary 1011011 even or odd?
I thought about it. Show me
Odd. The rightmost bit is the ones place, and it's 1. Every other place is a multiple of 2, so a binary number is odd exactly when its last bit is 1.
Convert, then compare
Put these three values in order from smallest to largest: binary 110010, decimal 49, binary 101111.
  1. Convert 110010. Places from the left: 32, 16, 8, 4, 2, 1. The 1s are in 32, 16 and 2: 32 + 16 + 2 = 50.
    Why?
    A six-bit number has places up to 32. Always label the places before adding.
  2. Convert 101111. The 1s are in 32, 8, 4, 2 and 1: 32 + 8 + 4 + 2 + 1 = 47.
  3. Now all three are in base 10: 50, 49 and 47. In order: 47, 49, 50.
    Why?
    You can't compare numbers written in different bases by looking at them. Convert to one base first.

Answer: Binary 101111 (47), then decimal 49, then binary 110010 (50).

Stuck? Get a hint
  1. Write 32, 16, 8, 4, 2, 1 over each six-bit number.
  2. Add only the places under a 1.
  3. Once all three are decimal, ordering is easy.
Decimal to binary
Convert 200 to an 8-bit binary number, then check your answer by converting back.
  1. Powers of 2 up to 200: 128, 64, 32, 16, 8, 4, 2, 1. (256 is too big.)
  2. 128 fits: bit 1, 72 left. 64 fits in 72: bit 1, 8 left. 32 and 16 don't fit in 8: bits 0, 0.
    Why?
    At each place ask: is this power at most what is left?
  3. 8 fits exactly: bit 1, 0 left. 4, 2 and 1: bits 0, 0, 0.
  4. Read the bits in order: 11001000. Check: 128 + 64 + 8 = 200.
    Why?
    Converting back is a quick way to catch a slip.

Answer: 200 = 11001000.

Stuck? Get a hint
  1. Start with the biggest power of 2 that is at most 200.
  2. 200 - 128 = 72, and 72 - 64 = 8.
  3. 8 is itself a power of 2.
Check yourself
What is the decimal value of binary 1101101?
  1. A91
  2. B109
  3. C117
  4. D182
Show the answer

B. Places from the left for seven bits: 64, 32, 16, 8, 4, 2, 1. The 1s are in 64, 32, 8, 4 and 1: 64 + 32 + 8 + 4 + 1 = 109. 182 is the trap: it treats the leftmost bit as 128, as if there were eight bits.

Check yourself
Which of these is the binary form of decimal 39?
  1. A100111
  2. B110011
  3. C100101
  4. D101001
Show the answer

A. 39 = 32 + 4 + 2 + 1, so the places 32, 16, 8, 4, 2, 1 get 1, 0, 0, 1, 1, 1. The others are 51, 37 and 41.

Beyond the course, as a bonus: programmers often write long binary patterns in base 16, hexadecimal, where each digit stands for four bits. The AP exam sticks to binary and decimal.

Exam tip from Mr. T

On a "which is largest" question that mixes bases, convert everything to decimal before you compare. A long binary number like 10000 is only 16, and decimal 15 is close behind.

  • Binary is base 2. Places from the right: 1, 2, 4, 8, 16, 32, 64, 128.
  • Binary to decimal: add the place values under each 1.
  • Decimal to binary: take out the biggest power of 2 that fits, and repeat.
  • A binary number is odd exactly when its rightmost bit is 1. Compare across bases only after converting.