Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.4: Binary Representation of Positive Integers

( \newcommand{\kernel}{\mathrm{null}\,}\)

Grouping by Twos

Recall that the set of positive integers, P, is {1,2,3,...}. Positive integers are naturally used to count things. There are many ways to count and many ways to record, or represent, the results of counting. For example, if we wanted to count five hundred twenty-three apples, we might group the apples by tens. There would be fifty-two groups of ten with three single apples left over. The fifty-two groups of ten could be put into five groups of ten tens (hundreds), with two tens left over. The five hundreds, two tens, and three units is recorded as 523. This system of counting is called the base ten positional system, or decimal system. It is quite natural for us to do grouping by tens, hundreds, thousands, since it is the method that all of us use in everyday life.

The term positional refers to the fact that each digit in the decimal representation of a number has a significance based on its position. Of course this means that rearranging digits will change the number being described. You may have learned of numeration systems in which the position of symbols does not have any significance (e.g., the ancient Egyptian system). Most of these systems are merely curiosities to us now.

The binary number system differs from the decimal number system in that units are grouped by twos, fours, eights, etc. That is, the group sizes are powers of two instead of powers of ten. For example, twenty-three can be grouped into eleven groups of two with one left over. The eleven twos can be grouped into five groups of four with one group of two left over. Continuing along the same lines, we find that twenty-three can be described as one sixteen, zero eights, one four, one two, and one one, which is abbreviated 10111two, or simply 10111 if the context is clear.

Conversion Algorithm

The process that we used to determine the binary representation of 23 can be described in general terms to determine the binary representation of any positive integer n. A general description of a process such as this one is called an algorithm. Since this is the first algorithm in the book, we will first write it out using less formal language than usual, and then introduce some “algorithmic notation.” If you are unfamiliar with algorithms, we refer you to Section 17.1

  1. Start with an empty list of bits.
  2. Assign the variable k the value n.
  3. While k's value is positive, continue performing the following three steps until k becomes zero and then stop.
    1. divide k by 2, obtaining a quotient q (often denoted k div 2) and a remainder r (denoted (kmod2)).
    2. attach r to the left-hand side of the list of bits.
    3. assign the variable k the value q.

Example 1.4.1: An Example of Conversion to Binary

To determine the binary representation of 41 we take the following steps:

  • 41=2×20+1List=1
  • 20=2×10+0List=01
  • 10=2×5+0List=001
  • 5=2×2+1List=1001
  • 2=2×1+0List=01001
  • 1=2×0+1List=101001

Therefore, 41=101001two

The notation that we will use to describe this algorithm and all others is called pseudocode, an informal variation of the instructions that are commonly used in many computer languages. Read the following description carefully, comparing it with the informal description above. Appendix B, which contains a general discussion of the components of the algorithms in this book, should clear up any lingering questions. Anything after // are comments.

Algorithm 1.4.1: Binary Conversion Algorithm

An algorithm for determining the binary representation of a positive integer.

Input: a positive integer n.

Output: the binary representation of n in the form of a list of bits, with units bit last, twos bit next to last, etc.

  1. k := n //initialize k
  2. L := { } //initialize L to an empty list
  3. While k > 0 do
    1. q := k div 2 //divide k by 2
    2. r:= k mod 2
    3. L: = prepend r to L //add r to the front of L
    4. k:= q //reassign k

Here is a Sage version of the algorithm with two alterations. It outputs the binary representation as a string, and it handles all integers, not just positive ones.

01def binary_rep(n):
02    if n==0:
03        return '0'
04    else:
05        k=abs(n)
06        s=''
07        while k>0:
08            s=str(k%2)+s
09            k=k//2
10        if n < 0:
11            s='-'+s
12        return s
13  
14binary_rep(41)

Now that you've read this section, you should get this joke.

clipboard_e69925d16eeea499b8278cc6b8e749193.png
Figure 1.4.1: With permission from Randall Munroe, http://xkcd.com.

Exercises

Exercise 1.4.1

Find the binary representation of each of the following positive integers by working through the algorithm by hand. You can check your answer using the sage cell above.

  1. 31
  2. 32
  3. 10
  4. 100
Answer
  1. 11111
  2. 100000
  3. 1010
  4. 1100100

Exercise 1.4.2

Find the binary representation of each of the following positive integers by working through the algorithm by hand. You can check your answer using the sage cell above.

  1. 64
  2. 67
  3. 28
  4. 256

Exercise 1.4.3

What positive integers have the following binary representations?

  1. 10010
  2. 10011
  3. 101010
  4. 10011110000
Answer
  1. 18
  2. 19
  3. 42
  4. 1264

Exercise 1.4.4

What positive integers have the following binary representations?

  1. 100001
  2. 1001001
  3. 1000000000
  4. 1001110000

Exercise 1.4.5

The number of bits in the binary representations of integers increases by one as the numbers double. Using this fact, determine how many bits the binary representations of the following decimal numbers have without actually doing the full conversion.

  1. 2017
  2. 4000
  3. 4500
  4. 250
Answer
  1. There is a bit for each power of 2 up to the largest one needed to represent an integer, and you start counting with the zeroth power. For example, 2017 is between 210=1024 and 211=2048, and so the largest power needed is 210. Therefore there are 11 bits in binary 2017.
  2. 11
  3. 12
  4. 13
  5. 51

Exercise 1.4.6

Let m be a positive integer with n-bit binary representation: an1an2a1a0 with an1=1 What are the smallest and largest values that m could have?

Exercise 1.4.7

If a positive integer is a multiple of 100, we can identify this fact from its decimal representation, since it will end with two zeros. What can you say about a positive integer if its binary representation ends with two zeros? What if it ends in k zeros?

Answer

A number must be a multiple of four if its binary representation ends in two zeros. If it ends in k zeros, it must be a multiple of 2k.

Exercise 1.4.8

Can a multiple of ten be easily identified from its binary representation?


This page titled 1.4: Binary Representation of Positive Integers is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?