Introduction to Hexadecimal and Data Conversion

Intro to Hexadecimal

• Base 16
• Requires 16 symbols, 0..9 + A,B,C,D,E,F
• Shorthand notation for binary
• Written in C as 0xFA1D37B or 0xfa1d37b

Advantage of Hexadecimal

• Easy to convert between hexadecimal and binary since one hex digit represents four bits
• Example: 1011000100101111 = 1011 0001 0010 1111 = B 1 2 F = 0xB12F

Bytes

• One byte equals 8 bits
• Range of values in binary: 000000002 to 111111112
• Range of values in decimal: 010 to 25510
• Range of values in hexadecimal: 0016 to FF16

Data Sizes

• Kilo, Mega, Giga prefixes can be confusing because they are used in both binary and decimal systems
• This course uses the binary sense of Kilo, Mega, Giga etc.

Conversions

• Every four binary digits convert to one hex digit and vice versa.
• Example: 11001101 = 1100 1101 = CD

Boolean Algebra Truth Tables

• AND:
  • 0 & 0 = 0
  • 0 & 1 = 0
  • 1 & 0 = 0
  • 1 & 1 = 1
• OR:
  • 0 | 0 = 0
  • 0 | 1 = 1
  • 1 | 0 = 1
  • 1 | 1 = 1
• NOT (Complement):
  • ~0 = 1
  • ~1 = 0
• XOR:
  • 0 ^ 0 = 0
  • 0 ^ 1 = 1
  • 1 ^ 0 = 1
  • 1 ^ 1 = 0

Logic Circuits

• Logic gates perform specific logic operations
• They are the building blocks of digital circuits
• OR gate has two or more inputs and one output
• The output is high if any or all inputs are high

Bits

• Computers are binary machines
• Bits are represented as 0 and 1
• Everything on a computer is encoded as a set of bits, including programs and data

Why Bits?

• Electronic implementation is easier using bi-stable elements
• Bits are more reliable to transmit on noisy and inaccurate wires

Bit Vector

• A bit vector is a sequence of bits, but its meaning depends on the type of information it represents and the encoding used.
• Without context, a bit vector has no inherent meaning.

Converting Binary to Decimal

• Sum the value of each binary digit times its power of 2.
• Example: 11001 = 1 * 24 + 1 * 23 + 0 * 22 + 0 * 21 + 1 * 20 = 25

Converting Decimal to Binary

• Divide the number by 2
• The remainder of each division becomes the binary digit
• Repeat until the quotient is 0
• Example: 13 = 1101
  • 13 / 2 = 6 (remainder 1)
  • 6 / 2 = 3 (remainder 0)
  • 3 / 2 = 1 (remainder 1)
  • 1 / 2 = 0 (remainder 1)

Converting Decimal to Hexadecimal

• Divide the number by 16
• The remainder of each division becomes the hex digit
• Repeat until the quotient is 0
• Example: 7562 = 1D8A
  • 7562 / 16 = 472 (remainder 10 = A)
  • 472 / 16 = 29 (remainder 8)
  • 29 / 16 = 1 (remainder 13 = D)
  • 1 / 16 = 0 (remainder 1)

Converting Hexadecimal to Decimal

• Multiply each hexadecimal digit by its corresponding power of 16.
• Sum the results.
• Example: 1D8A = (1 × 16³) + (13 × 16²) + (8 × 16¹) + (10 × 16⁰) = 7562

Negation

• To compute -X for a bit-vector X, compute the complement and add 1: -X = ~X + 1.
• Example: X = 011001 = 25, ~X = 100110 = -26, ~X+1 = 100111 = -25

Addition for Unsigned Numbers

• Standard addition function ignores carry bits and implements modular arithmetic.
• Formula: UAdd(u , v) = (u + v) mod 2w

Addition of Signed Numbers

• True sum requires w+1 bits
• Addition ignores the carry bit
• If TAddw(u, v) >= 2w–1, then sum becomes negative (positive overflow)
• If TAddw(u, v) < –2w–1, then sum becomes positive (negative overflow)

Multiplication

• Task: Computing Exact Product of w-bit numbers x, y (either signed or unsigned)
• Ranges of results:
  • Unsigned multiplication requires up to 2w bits to store result: 0 ≤ x * y ≤ (2w – 1)2 = 22w – 2w+1 + 1
  • Two's complement smallest possible value requires up to 2w-1 bits: x * y ≥ (–2w–1)*(2w–1–1)= –22w–2 + 2w–1
  • Two's complement largest possible value requires up to 2w bits (in one case): x * y ≤ (–2w–1)2 = 22w–2
• Maintaining exact results would need to keep expanding the word size with each product computed.

Multiplication by Power of 2 (Left Shift)

• Multiplication by a power of two is equivalent to the left shift operation.
• Example: u * 2k is the same as u << k

Sign Extension

• Task: Given a w-bit signed integer X, convert it to a (w+k)-bit integer X' with the same value.
• Solution: Make k copies of the sign bit.
• Example: X = xw-1 xw-2...x1x0, X' = xw-1...xw-1xw-1 xw-2...x1x0
• C automatically performs sign extension when converting from a smaller data type to a larger one.

Truncating

• Example: From int to short (from 32-bit to 16-bit)
• High-order bits are truncated, altering the value
• This non-intuitive behavior can lead to bugs in code.
• Example:

  int i = 1572539;
  short si = (short) i;
  printf(" i = %i\n si = %i\n\n ", i, si );
  

• This prints:

  i = 1572539
  si = -325