numbers as bits (notes)

1 of 6

bit: something which holds one of two states (usually represented as 0 and 1).

number system: a scheme for symbolically and verbally representing quantity

unary/tally system: a number system in which we make one mark for each count.

positional notation: a number system representing arbitrarily large quantities using a finite set of symbols in “digit places”.

Arabic numerals: the symbols 0 1 2 3 4 5 6 7 9

decimal: Positional notation using 10 symbols (0 1 2 3 4 5 6 7 8 9).

2 of 6

octal: Positional notation using 8 symbols (0 1 2 3 4 5 6 7).

By convention, octal numbers are distinguished by a leading zero:

53           (fifty-three decimal)
053         (five three octal)

hexadecimal / “hex”: Positional notation using 16 symbols (0 1 2 3 4 5 6 7 8 9 A B C D E F). The letters may be written either uppercase or lowercase.

By convention, hex numbers are distinguished by a leading zero x:

53           (fifty-three decimal)
0x53       (five three hex)

binary: Positional notation using 2 symbols (0 1).

By convention, hex numbers are distinguished by a following b:

10           (ten decimal)
10b         (one zero binary)

3 of 6

In positional notation, the quantity represented is a sum of the individual digits each multiplied by a power of the number base. For instance, decimal 827 equals (8 * 102) + (8 * 101) + (7 * 100).

Therefore, to convert from one number base to another, we use this formula to decompose a number into terms that are trivial to convert. So to convert hexadecimal 0x5AB, we break it into (0x5 * 162) + (0xA * 161) + (0xB * 160); 0xA equals decimal 10 and 0xB equals decimal 11, so this becomes (5 * 162) + (10 * 161) + (11 * 160). The only hard part now is calculating powers of 16 and multiplying those powers with other numbers.

When converting in the other direction, from decimal to hex, the hard part is calculating powers in hex and then multiplying and summing hex numbers, e.g. decimal 734 becomes:

(7 * 102) + (3 * 101) + (4 * 100)
(0x7 * 0xA2) + (0x3 * 0xA1) + (0x * 0xA0)

(If you’re not comfortable doing hex arithmetic, this is tricky.)

Conversions from binary to decimal are especially easy, though. Because each digit is either 0 or 1, we don’t have to do real multiplication: anything times 1 is itself and anything times 0 is 0. So, to convert 10101b, we just add the straight powers of 2 that correspond to the digits with 1’s:

24 + 22 + 20
16 + 4 + 1
21                                           = 10101b

Going from decimal to binary is a bit trickier, but relatively easier than other conversions. Just subtract out all the powers of two that make up the number, e.g. decimal 5 is composed of 4 and 1, which are respectively 22 and 20, so in binary, the digit places corresponding to those powers of two have 1’s while all others have zeroes:

4 + 1
22 + 20
101b                                      = 5

It’s possible then to do conversions in your head for small- to moderately-sized binary numbers if you memorize the powers of two (memorizing up to about 220 is reasonable).

4 and 6

Because octal and hex are number bases that are powers of two, they have a special relationship with binary, in short:

  • one digit of octal corresponds directly to three digits of binary
  • one digit of hex corresponds directly to four digits of binary

Consequently, it is trivial to convert between binary and octal or between binary and hex such that these conversions can be done in your head. All it requires is memorizing the three binary digits that correspond to each octal digit and memorizing the four binary digits that correspond to each hex digit. For example, the binary number 1011101101b translates to hex by grouping it into groups of four digits (adding leading zeros, if necessary):

0010 1110 1101

…and then converting each group:

0010b = 0x2
1110b = 0xE
1101b = 0xD

…so we get:

0x2ED = 1011101101b

Going from hex to binary, we convert 0xF7 by simply observing that:

0xF = 1111b
0x7 = 0111b

…and so:

11110111 = 0xF7

This conversion is so easy that programmers use hex as a more compact way of representing binary data.

5 of 6

integer: whole numbers (numbers without a fractional component)

signed / unsigned: A signed representation can represent both positive and negative quantities whereas an unsigned representation can only represent positive quantities.

Given n bits, you can represent 2n different values

For unsigned numbers, n bits represent the range of values from 0 to (2n – 1).

Sign bit: a bit used to denote the sign of a number.

One’s complement form: A negative is represented by taking the positive and flipping all the bits.

Two’s complement form: A negative is represented by taking the positive and flipping all the bits and then adding one.

Whereas in one’s complement form, we have both a negative and positive zero, in two’s complement form, we just have one representation of zero.

Given n bits, two’s complement form can represent the range -(2n-1) up +(2n-1 – 1). For instance, given 8 bits, two’s complement represents -128 up to +127.

Two’s complement is the favored form to represent signed numbers because it requires the simplest circuitry for doing addition.

Excess-n form: n becomes the representation for zero such that all numbers greater than n are positive while all numbers less than n are negative. For instance, in excess-22, 0 is represented as 22, so positive 3 is represented as 25 whereas negative 3 is represented as 19.

Rational number: A quantity which is the ratio of two integers, e.g. 3/5.

Radix-point notation: representation of fractional quantities using a radix-point. The digits to the right of the radix point represent that digit multiplied by a decreasing power of the number base, e.g. 72.341 is (7 * 101) + (2 * 100) + (3 * 10-1) + (4 * 10-2) + (1 * 10-3).

6 of 6

Finite rational: A rational number that can be expressed in fixed-point notation with a finite number of digits. In a given number base, some rationals are not finite. For instance, 1/3 is not finite in decimal, but it is finite in base-3:

0.333333…           (1/3 in decimal)
0.1                          (1/3 in base-3)

When a rational is finite in a number base, its denominator is a product of the factors of that number base raised to some powers. For instance, the factors of 10 are 2 and 5, so if a rational’s denominator equals 2a5b for some positive integers a and b, then it is rational in base 10 (decimal). In the case of binary, the only factor of 2 is 2, so the only rationals finite in binary are those with a denominator equal to 2a for some positive integer a.

Note then, that all rationals that are finite in binary are also finite in decimal because the values 2a are a subset of the values 2a5b. However, it conversley means that only some rationals that are finite in decimal are also finite in binary.

Scientific/engineering notation: representing a quantity as a significand and an exponent (a power of 10, by convention), e.g. 3.64e9 is 3.64 * 109.

Floating-point: the computing equivalent of scientific notation, except in binary with an exponent that is a power of two.  The IEEE (Institute of Electrical and Electronics Engineers) has floating-point format specifications that detail precisely how many bits to use for the significand, how many to use for the exponent, and how to arrange the bits.

As noted above, only some rationals that are finite in decimal are also finite in binary. So the surprising part about binary floating-point representation is that, for example, 0.2 simply can’t be represented (because 0.2 = 1/5, and no value of 2a equals 5). The best we can do to represent 0.2 is approximate.

Here’s an online calculator that shows you the precise floating-point representation of an entered decimal value.

Comments are closed.