Number Systems - Binary, Hexadecimal, ASCII

1. Binary (Base-2)

Binary uses only two digits: 0 and 1. It's the foundation of all digital computing.

Place Values

Binary to Decimal Conversion

def binary_to_decimal(binary_str):
    """Convert binary string to decimal"""
    decimal = 0
    power = 0

    # Process right to left
    for bit in reversed(binary_str):
        if bit == '1':
            decimal += 2 ** power
        power += 1

    return decimal

# Examples
print(binary_to_decimal("1011"))     # 11
print(binary_to_decimal("11111111")) # 255
print(binary_to_decimal("10000000")) # 128

# Python built-in
int("1011", 2)  # 11

Decimal to Binary Conversion

def decimal_to_binary(decimal):
    """Convert decimal to binary string"""
    if decimal == 0:
        return "0"

    binary = ""
    while decimal > 0:
        binary = str(decimal % 2) + binary
        decimal = decimal // 2

    return binary

# Examples
print(decimal_to_binary(11))   # "1011"
print(decimal_to_binary(255))  # "11111111"
print(decimal_to_binary(128))  # "10000000"

# Python built-in
bin(11)    # '0b1011'
bin(255)   # '0b11111111'

Binary Arithmetic

Binary Operations (Bitwise)

# AND (&) - Both bits must be 1
  1011  (11)
& 0110  (6)
------
  0010  (2)

# OR (|) - At least one bit must be 1
  1011  (11)
| 0110  (6)
------
  1111  (15)

# XOR (^) - Bits must be different
  1011  (11)
^ 0110  (6)
------
  1101  (13)

# NOT (~) - Invert all bits
~ 1011  (11)
------
  0100  (-12 in two's complement)

# Left Shift (<<) - Multiply by 2^n
1011 << 1 = 10110  (11 → 22, multiply by 2)
1011 << 2 = 101100 (11 → 44, multiply by 4)

# Right Shift (>>) - Divide by 2^n
1011 >> 1 = 0101   (11 → 5, divide by 2)
1011 >> 2 = 0010   (11 → 2, divide by 4)

# Python examples
print(11 & 6)   # 2
print(11 | 6)   # 15
print(11 ^ 6)   # 13
print(~11)      # -12
print(11 << 1)  # 22
print(11 >> 1)  # 5

Common Binary Patterns

Decimal	Binary (8-bit)	Pattern
0	00000000	All zeros
1	00000001	Rightmost bit
127	01111111	Max positive (signed 8-bit)
128	10000000	-128 (signed 8-bit)
255	11111111	All ones (max unsigned)

Two's Complement (Negative Numbers)

Practical Binary Tricks

# Check if number is power of 2
def is_power_of_2(n):
    """Power of 2 has exactly one bit set"""
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_2(8))   # True  (1000)
print(is_power_of_2(6))   # False (0110)

# Count set bits (Brian Kernighan's algorithm)
def count_bits(n):
    """Count number of 1 bits"""
    count = 0
    while n:
        n &= (n - 1)  # Remove rightmost 1
        count += 1
    return count

print(count_bits(13))  # 3 (1101 has three 1s)

# Check if bit i is set
def is_bit_set(num, i):
    """Check if bit at position i is 1"""
    return (num & (1 << i)) != 0

print(is_bit_set(13, 2))  # True  (13 = 1101, bit 2 is 1)
print(is_bit_set(13, 1))  # False (13 = 1101, bit 1 is 0)

# Set bit i
def set_bit(num, i):
    """Set bit at position i to 1"""
    return num | (1 << i)

print(set_bit(8, 0))  # 9 (1000 → 1001)

# Clear bit i
def clear_bit(num, i):
    """Set bit at position i to 0"""
    return num & ~(1 << i)

print(clear_bit(9, 0))  # 8 (1001 → 1000)

# Toggle bit i
def toggle_bit(num, i):
    """Flip bit at position i"""
    return num ^ (1 << i)

print(toggle_bit(8, 0))  # 9 (1000 → 1001)
print(toggle_bit(9, 0))  # 8 (1001 → 1000)

Bitmask Patterns: Using Bits as Sets

A powerful technique: use an integer's bits to represent a set of elements. Each bit position represents whether an element is included (1) or not (0).

# Represent a set using bitmask
# Elements: A=0, B=1, C=2, D=3

# Set {A, D} = bits 0 and 3 set
my_set = (1 << 0) | (1 << 3)  # 0b1001 = 9

# Check if B is in the set
B = 1
if my_set & (1 << B):
    print("B is in set")
else:
    print("B is NOT in set")  # This prints

# Add C to the set
C = 2
my_set |= (1 << C)  # Now 0b1101 = {A, C, D}

# Remove A from the set
A = 0
my_set &= ~(1 << A)  # Now 0b1100 = {C, D}

# Iterate through all elements in the set
def get_elements(bitmask, n_elements):
    """Return list of elements in the bitmask"""
    return [i for i in range(n_elements) if bitmask & (1 << i)]

print(get_elements(0b1101, 4))  # [0, 2, 3] = {A, C, D}

Why Use Bitmasks Instead of Sets?

Operation	Python Set	Bitmask
Check membership	x in my_set O(1)	mask & (1 << x) O(1)
Add element	my_set.add(x) O(1)	mask | (1 << x) O(1)
Union	a | b O(n)	a | b O(1)
Intersection	a & b O(n)	a & b O(1)
Use as dict key	frozenset needed	Integer works directly
Memory	Object overhead	Single integer

Limitation: Bitmasks work best for small sets (≤20-30 elements) since you need 2^n possible states.

Bitmask DP: Subset Problems

Many DP problems involve tracking "which items have been used." Bitmasks make this efficient.

Pattern: Iterate All Subsets

# Iterate through all subsets of n elements
n = 3  # Elements: {0, 1, 2}

for mask in range(1 << n):  # 0 to 7 (2^3 - 1)
    subset = [i for i in range(n) if mask & (1 << i)]
    print(f"{mask:03b} = {subset}")

# Output:
# 000 = []
# 001 = [0]
# 010 = [1]
# 011 = [0, 1]
# 100 = [2]
# 101 = [0, 2]
# 110 = [1, 2]
# 111 = [0, 1, 2]

Example: Traveling Salesman Problem (TSP)

Find the shortest route visiting all cities exactly once and returning to start.

def tsp(dist):
    """
    Traveling Salesman using bitmask DP.
    dist[i][j] = distance from city i to city j

    State: dp[mask][i] = min cost to visit cities in 'mask' ending at city i

    Time: O(n^2 * 2^n)  - much better than O(n!) brute force
    Space: O(n * 2^n)
    """
    n = len(dist)
    INF = float('inf')

    # dp[visited_mask][current_city] = minimum distance
    dp = [[INF] * n for _ in range(1 << n)]

    # Start at city 0
    dp[1][0] = 0  # visited={0}, at city 0, cost=0

    # Try all subsets of cities
    for mask in range(1 << n):
        for current in range(n):
            if dp[mask][current] == INF:
                continue
            if not (mask & (1 << current)):  # current must be in mask
                continue

            # Try extending to each unvisited city
            for next_city in range(n):
                if mask & (1 << next_city):  # Skip if already visited
                    continue

                new_mask = mask | (1 << next_city)
                new_cost = dp[mask][current] + dist[current][next_city]
                dp[new_mask][next_city] = min(dp[new_mask][next_city], new_cost)

    # Find minimum: visit all cities and return to start
    all_visited = (1 << n) - 1  # All bits set
    return min(dp[all_visited][i] + dist[i][0] for i in range(n))


# Example: 4 cities
#        10
#    A ────── B
#    │\      /│
#  20│ \5  4/ │15
#    │  \/   │
#    C ────── D
#        8

dist = [
    [0, 10, 20, 5],   # From A
    [10, 0, 4, 15],   # From B
    [20, 4, 0, 8],    # From C
    [5, 15, 8, 0]     # From D
]

print(tsp(dist))  # 27 (A→D→C→B→A or A→B→C→D→A)

Other Bitmask DP Problems

Problem	State	Meaning
TSP	dp[mask][i]	Min cost visiting 'mask' cities, ending at i
Subset Sum	dp[mask]	Is subset sum achievable?
Assign Tasks	dp[mask]	Min cost assigning tasks in 'mask' to workers
Hamiltonian Path	dp[mask][i]	Can we visit 'mask' vertices ending at i?
Matching	dp[mask]	Ways to match items in 'mask'

Common Bitmask Tricks Summary

# Check if bit i is set
mask & (1 << i)

# Set bit i
mask | (1 << i)

# Clear bit i
mask & ~(1 << i)

# Toggle bit i
mask ^ (1 << i)

# Check if all n bits are set
mask == (1 << n) - 1

# Count set bits
bin(mask).count('1')  # Simple
# or use bit_count() in Python 3.10+

# Get lowest set bit
mask & (-mask)

# Clear lowest set bit
mask & (mask - 1)

# Iterate all subsets of a mask
subset = mask
while subset:
    # process subset
    subset = (subset - 1) & mask

2. Hexadecimal (Base-16)

Hexadecimal uses 16 digits: 0-9, A-F

A=10, B=11, C=12, D=13, E=14, F=15

Why Use Hex?

Hex to Decimal

def hex_to_decimal(hex_str):
    """Convert hex string to decimal"""
    return int(hex_str, 16)

print(hex_to_decimal("2AF"))   # 687
print(hex_to_decimal("FF"))    # 255
print(hex_to_decimal("100"))   # 256

Decimal to Hex

def decimal_to_hex(decimal):
    """Convert decimal to hex string"""
    if decimal == 0:
        return "0"

    hex_chars = "0123456789ABCDEF"
    hex_str = ""

    while decimal > 0:
        hex_str = hex_chars[decimal % 16] + hex_str
        decimal = decimal // 16

    return hex_str

print(decimal_to_hex(687))   # "2AF"
print(decimal_to_hex(255))   # "FF"
print(decimal_to_hex(256))   # "100"

# Python built-in
hex(687)   # '0x2af'
hex(255)   # '0xff'

Binary ↔ Hex Conversion

# Binary to Hex
def bin_to_hex(binary_str):
    """Convert binary string to hex"""
    decimal = int(binary_str, 2)
    return hex(decimal)[2:].upper()  # Remove '0x' prefix

print(bin_to_hex("101011110011"))  # "AF3"

# Hex to Binary
def hex_to_bin(hex_str):
    """Convert hex string to binary"""
    decimal = int(hex_str, 16)
    return bin(decimal)[2:]  # Remove '0b' prefix

print(hex_to_bin("AF3"))  # "101011110011"

Common Hex Values

Decimal	Hexadecimal	Binary	Usage
0	0x00	00000000	Null byte
255	0xFF	11111111	Max byte value
256	0x100	100000000	2 bytes start
65535	0xFFFF	1111111111111111	Max 16-bit unsigned

Hex in Practice

# RGB Colors (hex format)
white = 0xFFFFFF   # Red=FF, Green=FF, Blue=FF
black = 0x000000   # Red=00, Green=00, Blue=00
red   = 0xFF0000   # Red=FF, Green=00, Blue=00
green = 0x00FF00   # Red=00, Green=FF, Blue=00
blue  = 0x0000FF   # Red=00, Green=00, Blue=FF

# Extract RGB components
def get_rgb(color_hex):
    """Extract R, G, B from hex color"""
    r = (color_hex >> 16) & 0xFF
    g = (color_hex >> 8) & 0xFF
    b = color_hex & 0xFF
    return (r, g, b)

print(get_rgb(0xFF5733))  # (255, 87, 51)

# Memory addresses
address = 0x7FFF5FBFF8A0  # Typical stack address
print(f"Address: {address:#018x}")  # 0x00007fff5fbff8a0

# Bit masks
READ_PERMISSION  = 0x04  # 0100
WRITE_PERMISSION = 0x02  # 0010
EXEC_PERMISSION  = 0x01  # 0001

permissions = READ_PERMISSION | WRITE_PERMISSION  # 0x06 (rw-)
has_write = (permissions & WRITE_PERMISSION) != 0  # True

Understanding RGB Colors

RGB (Red, Green, Blue) is an additive color model where colors are created by combining different intensities of red, green, and blue light.

Common RGB Color Values

Color	Hex	R	G	B
Black	#000000	0	0	0
White	#FFFFFF	255	255	255
Red	#FF0000	255	0	0
Green	#00FF00	0	255	0
Blue	#0000FF	0	0	255
Yellow	#FFFF00	255	255	0
Cyan	#00FFFF	0	255	255
Magenta	#FF00FF	255	0	255

Color Bit Depths

The standard hex RGB format (#RRGGBB) represents 24-bit color (8 bits × 3 channels), giving 16,777,216 possible colors.

Bit Depth	Bits per Channel	Total Colors	Notes
8-bit	Indexed palette	256	Old GIFs, early games
16-bit	5-6-5 (R-G-B)	65,536	"High Color"
24-bit	8-8-8	16.7 million	Standard "True Color"
32-bit	8-8-8-8	16.7M + alpha	24-bit + transparency
48-bit	16-16-16	281 trillion	Pro photography/RAW

3. ASCII (American Standard Code for Information Interchange)

ASCII is a character encoding standard that maps characters to numbers (0-127).

ASCII Table (Common Characters)

Decimal	Hex	Binary	Character	Description
0	0x00	00000000	NUL	Null character
10	0x0A	00001010	\n	Line feed (newline)
13	0x0D	00001101	\r	Carriage return
32	0x20	00100000	SPACE	Space character
48-57	0x30-0x39	-	0-9	Digits
65-90	0x41-0x5A	-	A-Z	Uppercase letters
97-122	0x61-0x7A	-	a-z	Lowercase letters

ASCII Conversion

# Character to ASCII
print(ord('A'))   # 65
print(ord('a'))   # 97
print(ord('0'))   # 48
print(ord(' '))   # 32

# ASCII to Character
print(chr(65))    # 'A'
print(chr(97))    # 'a'
print(chr(48))    # '0'
print(chr(32))    # ' '

# String to ASCII codes
def string_to_ascii(s):
    """Convert string to list of ASCII codes"""
    return [ord(c) for c in s]

print(string_to_ascii("Hello"))  # [72, 101, 108, 108, 111]

# ASCII codes to string
def ascii_to_string(codes):
    """Convert list of ASCII codes to string"""
    return ''.join(chr(c) for c in codes)

print(ascii_to_string([72, 101, 108, 108, 111]))  # "Hello"

ASCII Patterns

# Case conversion using bit manipulation
def to_lowercase(char):
    """Convert uppercase to lowercase"""
    return chr(ord(char) | 0x20)  # Set bit 5

def to_uppercase(char):
    """Convert lowercase to uppercase"""
    return chr(ord(char) & ~0x20)  # Clear bit 5

print(to_lowercase('A'))  # 'a'
print(to_uppercase('z'))  # 'Z'

# Toggle case
def toggle_case(char):
    """Toggle between upper and lower case"""
    return chr(ord(char) ^ 0x20)  # Flip bit 5

print(toggle_case('A'))  # 'a'
print(toggle_case('a'))  # 'A'

# Check if character is alphabetic
def is_alpha(char):
    """Check if character is A-Z or a-z"""
    code = ord(char)
    return (65 <= code <= 90) or (97 <= code <= 122)

# Check if character is digit
def is_digit(char):
    """Check if character is 0-9"""
    return 48 <= ord(char) <= 57

4. Practical Applications

Subnet Masks (Networking)

# CIDR notation: 192.168.1.0/24
# /24 means first 24 bits are network, last 8 are host

def cidr_to_netmask(cidr_bits):
    """Convert CIDR to subnet mask"""
    mask = (0xFFFFFFFF << (32 - cidr_bits)) & 0xFFFFFFFF
    return f"{(mask >> 24) & 0xFF}.{(mask >> 16) & 0xFF}.{(mask >> 8) & 0xFF}.{mask & 0xFF}"

print(cidr_to_netmask(24))  # "255.255.255.0"
print(cidr_to_netmask(16))  # "255.255.0.0"
print(cidr_to_netmask(8))   # "255.0.0.0"

# Check if IP is in subnet
def ip_to_int(ip):
    """Convert IP string to integer"""
    parts = [int(x) for x in ip.split('.')]
    return (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3]

def in_subnet(ip, subnet, cidr_bits):
    """Check if IP is in subnet"""
    ip_int = ip_to_int(ip)
    subnet_int = ip_to_int(subnet)
    mask = (0xFFFFFFFF << (32 - cidr_bits)) & 0xFFFFFFFF

    return (ip_int & mask) == (subnet_int & mask)

print(in_subnet("192.168.1.100", "192.168.1.0", 24))  # True
print(in_subnet("192.168.2.100", "192.168.1.0", 24))  # False

File Permissions (Unix)

# Unix permissions: rwx rwx rwx (owner, group, others)
# Each group has 3 bits: read(4), write(2), execute(1)

def permissions_to_octal(read, write, execute):
    """Convert rwx flags to octal"""
    return (4 if read else 0) + (2 if write else 0) + (1 if execute else 0)

# 755 = rwxr-xr-x
owner = permissions_to_octal(True, True, True)     # 7
group = permissions_to_octal(True, False, True)    # 5
others = permissions_to_octal(True, False, True)   # 5

print(f"{owner}{group}{others}")  # "755"

def parse_permissions(octal):
    """Parse octal permissions to rwx string"""
    perms = ""
    for digit in str(octal):
        d = int(digit)
        perms += "r" if d & 4 else "-"
        perms += "w" if d & 2 else "-"
        perms += "x" if d & 1 else "-"
    return perms

print(parse_permissions(755))  # "rwxr-xr-x"
print(parse_permissions(644))  # "rw-r--r--"

UTF-8 Encoding (Beyond ASCII)

# UTF-8 encodes Unicode characters using 1-4 bytes
# ASCII characters (0-127) use 1 byte
# Extended characters use 2-4 bytes

# String to UTF-8 bytes
text = "Hello 世界"
utf8_bytes = text.encode('utf-8')
print(utf8_bytes)  # b'Hello \xe4\xb8\x96\xe7\x95\x8c'
print([hex(b) for b in utf8_bytes])

# UTF-8 bytes to string
decoded = utf8_bytes.decode('utf-8')
print(decoded)  # "Hello 世界"

# Character byte length
def utf8_byte_length(char):
    """Get number of bytes for UTF-8 character"""
    return len(char.encode('utf-8'))

print(utf8_byte_length('A'))   # 1 (ASCII)
print(utf8_byte_length('世'))  # 3 (Chinese character)