Number Systems

Equation

In general, if the radix of a number is , then the value of is:

(see summation notation)

Binary

Info

Binary consists of numbers 0 and 1. Each digit represents 32, 16, 8, 4, 2, 1 from right to left. I.e powers of 2.

Example

Convert to base-10.

solution

Example

Convert to binary

solution
Keep dividing by 2 until the quotient is 0, keeping track of the remainder.

Number Quotient Remainder
38 19 0
19 9 1
9 4 1
4 2 0
2 1 0
1 0 1

The number is (bottom to top of the remainder column)

Signed Integers

Definition

A sign bit is the first (leftmost) bit of a binary number. 0 indicates a positive, 1 indicates negative.

First bit, aka most significant bit (msb)

NB: msB means most significant byte

Sign and Magnitude

So he [Anwar Hasan] taught us sign and magnitude because it's shit. Ok.
- Kegan

Info

Use a sign bit at the front, and the rest of the number is magnitude.

Example

  • is
  • is

One's Complement

Info

Use a sign bit at the front, and then take the complement of all the other bits.

Example

  • is
  • is

Two's Complement Form

AKA signed two's complement (S2C)

Info

Use a sign bit at the front, take the complement of all the other bits, and add 1.

Example

  • is
  • is

Theorem

Let be an n-bit s2c of negative , then

Computers implement arithmetic mod . A given bit sequence represents an equivalence class

Negation methods

  1. Take 1's complement, then add 1
  2. Complement the bits to the left of the rightmost 1

To go backwards, interpret the sign bit as and add all the other bits.

Figure

Arithmetic

Addition and subtraction are easy in two's complement form. Add two numbers as you normally would. To subtract two numbers, just take two's complement of the other number and add it.

Example

We know in base 10, . In binary, we have:

Discarding the bit on the left, we have , which indeed is .

Integer Overflow

Info

Range of -bit numbers:

  • Unsigned:
  • Signed:
Definition

Overflow occurs when an operation result exceeds the range

Example

For , if we try , we get , which is actually in two's complement

Detecting overflow: both operands have the same sign and the result is a different sign

Equation

You can implement this boolean expression as a SOP.

Sign Extension

Info

To increase the "space" of the integer, replicate the msb

Example

Shifting

todo Change formatting with underbraces, also note that this should be for multiplication and division, and the techniques are shifting

Example

Shift left bits: multiply by

Example

Shift right byts: divide by

Octal

Info

Octal involves digits to

Example

Convert to base-10.

solution

Example

Convert to octal.

solution
Keep dividing by 8 until the quotient is 0, keeping track of the remainder.

Number Quotient Remainder
420 52 4
52 6 4
6 0 6

The number is (bottom to top of the remainder column)

Hexadecimal

Info

Hexadecimal involves digits to , with digits , , , , , and shown using letters A, B, C, D, E, and F respectively.

Example

Convert to base-10.

solution

Example

Convert to hexadecimal.

solution
Keep dividing by 16 until the quotient is 0, keeping track of the remainder.

Number Quotient Remainder
109 6 13 (D)
6 0 6

The number is (bottom to top of the remainder column)

Converting Between Number Systems

Other than base 10.

Octal and Binary

Info

Octal to Binary: replace each octal symbol by its 3-bit binary representation
Binary to Octal: start from the least significant end (right), and group 3 binary bits into their corresponding octal symbol

Example

Convert to binary.

solution

Example

Convert to octal.

solution

Hex and Binary

Info

Hex to Binary: replace each hex symbol by its 4-bit binary representation
Binary to Hex: start from the least significant end (right), and group 4 binary bits into their corresponding hex symbol

Example

Convert to binary.

solution

Example

Convert to hex.

solution