2.8: The Binary Mumeral System

Last updated
Save as PDF

Page ID: 81408

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

There are all sorts of reasons why one should give thought to numeral systems using bases different from the familiar base 10. This is especially true of base 2, which is the simplest system of all, and is also (in some sense) the most widely used. What follows is only intended to offer a restricted glimpse into this alternative universe.

Problem 71 The numbers in this item are all written in base 2.

(a) Carry out the addition

$\underset{──────}{\begin{matrix} 11100 \\ + 1110 \end{matrix}}$

without changing the numbers into their base 10 equivalents – simply by applying the rules for base 2 column addition and “carrying”.

(b) Carry out these long multiplications without changing the numbers into their base 10 equivalents – simply by applying the rules for base 2 column multiplication.

(i) $\underset{──────}{\begin{matrix} 10110 \\ \times 10 \end{matrix}}$

(ii) $\underset{──────}{\begin{matrix} 1110 \\ \times 11 \end{matrix}}$

(iii) $\underset{──────}{\begin{matrix} 110 \\ \times 111 \end{matrix}}$

(c) Try to add these fractions (where the numerators and denominators are numerals written in base 2) without changing the fractions into more familiar base 10 form.

$\frac{110}{1111} + \frac{1}{10} + \frac{1001}{1110}$

The next problem invites you to devise divisibility tests for integers written in base 2 like those for base 10 (that is, tests which implement some check involving the base 2 digits in place of carrying out the actual division).

Problem 72 Let N be a positive integer written in base 2. Describe and justify a simple test, based on the digits of N_base2:

(i) for N to be divisible by 2

(ii) for N to be divisible by 3

(iii) for N to be divisible by 4

(iv) for N to be divisible by 5.

Problem 73 A mathematical merchant has a pair of scales and an infinite set of calibrated integral weights with values $w_{0}, w_{1}, w_{2}, \dots$ (where $w_{0} < w_{1} < w_{2} < \dots$ ), but with only one weight of each value.

(a) Suppose that, for each object of positive integer weight w whose weight is to be determined, when the object is placed in one scale pan, the merchant is able to select some combination of his weights $w_{0}, w_{1}, w_{2}, \dots$ to put in the other scale pan to balance, and hence to determine the weight of, the object to be weighed.

(i) If for each weight w there is a unique choice of weights w_i that balance w, prove that the collection of weights must consist of all the powers of 2.

(ii) If every object of unknown integral weight w can be balanced by some collection of the weights w_i, but some weights w can be balanced, or “represented”, in more than one way, is it true that the merchant’s collection of weights has to include all the powers of 2?

(b) What can you prove if the merchant’s set of weights allow him to balance every unknown integer weight w in exactly one way by varying his weighing procedure, so that he can place his “known weights” in either scale pan (either in the same scale pan as the unknown weight to add to its weight, or in the opposite scale pan to balance it)?

Problem 74 Explain how to express any fraction

$\begin{matrix} \frac{m}{2^{n}} \end{matrix}$

where $0 < m < 2^{n}$ as a sum of distinct unit fractions with denominator a power of 2.

You may have heard of an algorithm (a bit like long division) which allows one to compute by hand the square root of any number N given in base 10. The algorithm starts by grouping the digits of N in pairs, starting from the decimal point. It then extracts the square root, digit by digit, with the square root having one digit for each successive pair of digits of N, starting with the left-most pair (which may be a single digit).

We all know how to start the process. For example, if the left most pair of digits in N is “12”, then we know that the square root starts with a “3”. Successive digits are then identified using the algebraic identity

$\begin{matrix} N = {(x + y)}^{2} = x^{2} + 2 x y + y^{2}, \end{matrix}$

where x is the sequence of leading digits in the “partial square root” extracted so far (followed by an appropriate string of 0s), and y stands for the residual part of the required square root.

The key is to concentrate each time on the leading digit Y of the residue “ $N - x^{2}$ “, and at each stage to choose the leading digit Y of y so that $2 x y + y^{2}$ does not exceed $N - x^{2}$ . This sequence of steps is traditionally (and helpfully) laid out in much the same way as long division, where at each stage we subtract the square of the current approximate square root x, from the original number N, and “bring down” the next pair of digits, and then choose the next digit Y in the square root (the leading digit of y) so that “ $2 x y + y^{2}$ “ does not exceed the residue $N - x^{2}$ .

In base 10 each stage requires one to juggle possibilities to decide on the next digit in the partial square root. However, in base 2 the process should be simpler, since at each stage we only have to decide whether the next digit is a 1 or a 0.

Problem 75 Work out how to calculate the square root of any square given in base 2.