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 
  

This quiz covers the basics of hexadecimal notation and its advantages over binary representation. It includes concepts like byte size, data conversions, and Boolean algebra truth tables. Perfect for students learning about number systems in programming.