py_08_binary_addition_subtraction_gh.py

#!/usr/bin/env python3
"""
Chapter 8: Binary Addition and Subtraction
Demonstrates binary arithmetic using two's complement
"""

def binary_add(bin1, bin2, bits=8):
    """Add two binary numbers (as strings) with specified bit width"""
    # Convert to integers, add, and convert back
    val1 = int(bin1, 2)
    val2 = int(bin2, 2)
    result = val1 + val2
    
    # Check for overflow
    max_val = (1 << bits) - 1
    overflow = result > max_val
    
    # Mask to bit width
    result = result & max_val
    
    return format(result, f'0{bits}b'), overflow

def twos_complement_add(bin1, bin2):
    """Add two binary numbers in two's complement representation"""
    # Extend to same length
    max_len = max(len(bin1), len(bin2))
    bin1 = bin1.zfill(max_len)
    bin2 = bin2.zfill(max_len)
    
    result = []
    carry = 0
    
    # Add from right to left
    for i in range(max_len - 1, -1, -1):
        bit_sum = int(bin1[i]) + int(bin2[i]) + carry
        result.append(str(bit_sum % 2))
        carry = bit_sum // 2
    
    result.reverse()
    binary_result = ''.join(result)
    
    # Check for overflow in signed arithmetic
    # Overflow if: both operands positive, result negative
    # OR both operands negative, result positive
    sign1 = bin1[0]
    sign2 = bin2[0]
    sign_result = binary_result[0]
    
    overflow = False
    if sign1 == '0' and sign2 == '0' and sign_result == '1':
        overflow = True  # Two positives gave negative
    elif sign1 == '1' and sign2 == '1' and sign_result == '0':
        overflow = True  # Two negatives gave positive
    
    return binary_result, carry, overflow

def twos_complement_subtract(bin1, bin2):
    """Subtract bin2 from bin1 using two's complement"""
    # Subtraction: A - B = A + (-B) = A + two's_complement(B)
    
    # Calculate two's complement of bin2
    flipped = ''.join('0' if bit == '1' else '1' for bit in bin2)
    
    # Add 1
    carry = 1
    twos_comp = list(flipped)
    for i in range(len(twos_comp) - 1, -1, -1):
        if carry == 0:
            break
        if twos_comp[i] == '0':
            twos_comp[i] = '1'
            carry = 0
        else:
            twos_comp[i] = '0'
    
    twos_comp_str = ''.join(twos_comp)
    
    # Now add bin1 + two's_complement(bin2)
    result, final_carry, overflow = twos_complement_add(bin1, twos_comp_str)
    
    return result, twos_comp_str, final_carry

def signed_binary_to_decimal(binary_str):
    """Convert signed two's complement binary to decimal"""
    if binary_str[0] == '0':
        return int(binary_str, 2)
    else:
        # Negative: find two's complement
        flipped = ''.join('0' if bit == '1' else '1' for bit in binary_str)
        magnitude = int(flipped, 2) + 1
        return -magnitude

def main():
    print("=" * 60)
    print("CHAPTER 8: Binary Addition and Subtraction")
    print("=" * 60)
    
    # Example 1: Simple Binary Addition
    print("\n--- Example 1: Binary Addition ---")
    bin1 = "00001101"  # 13
    bin2 = "00001010"  # 10
    
    result, overflow = binary_add(bin1, bin2, 8)
    
    print(f"  {bin1} ({int(bin1, 2)})")
    print(f"+ {bin2} ({int(bin2, 2)})")
    print(f"  {'-' * 8}")
    print(f"  {result} ({int(result, 2)})")
    if overflow:
        print("  Overflow detected!")
    
    # Example 2: Addition with Carry
    print("\n--- Example 2: Addition with Carry ---")
    bin1 = "10110011"
    bin2 = "01011101"
    
    result, carry, overflow = twos_complement_add(bin1, bin2)
    
    print(f"  {bin1}")
    print(f"+ {bin2}")
    print(f"  {'-' * 8}")
    print(f"  {result} (final carry: {carry})")
    
    # Example 3: Subtraction using Two's Complement
    print("\n--- Example 3: Binary Subtraction (A - B = A + (-B)) ---")
    bin1 = "01100100"  # 100
    bin2 = "00101100"  # 44
    
    result, twos_comp, carry = twos_complement_subtract(bin1, bin2)
    
    print(f"Calculate: {int(bin1, 2)} - {int(bin2, 2)}")
    print(f"\nStep 1: Find two's complement of {bin2}")
    print(f"  Original:         {bin2}")
    flipped = ''.join('0' if bit == '1' else '1' for bit in bin2)
    print(f"  One's complement: {flipped}")
    print(f"  Add 1:            {twos_comp}")
    
    print(f"\nStep 2: Add to first number")
    print(f"  {bin1} ({int(bin1, 2)})")
    print(f"+ {twos_comp} ({signed_binary_to_decimal(twos_comp)})")
    print(f"  {'-' * 8}")
    print(f"  {result} ({int(result, 2)})")
    
    # Example 4: Overflow Detection
    print("\n--- Example 4: Overflow in Signed Addition ---")
    
    # Positive overflow
    bin1 = "01100100"  # +100
    bin2 = "00101100"  # +44
    result, carry, overflow = twos_complement_add(bin1, bin2)
    
    print("Adding two positive numbers:")
    print(f"  {bin1} (+{int(bin1, 2)})")
    print(f"+ {bin2} (+{int(bin2, 2)})")
    print(f"  {'-' * 8}")
    print(f"  {result} ({signed_binary_to_decimal(result)})")
    print(f"  Carry into sign: 1, Carry out: {carry}")
    if overflow:
        print("  ⚠ OVERFLOW! Result exceeds 8-bit signed range (-128 to 127)")
    
    # Example 5: Negative Number Addition
    print("\n--- Example 5: Adding Negative Numbers ---")
    # -5 + (-3) = -8
    bin1 = "11111011"  # -5 in two's complement
    bin2 = "11111101"  # -3 in two's complement
    
    result, carry, overflow = twos_complement_add(bin1, bin2)
    
    print(f"  {bin1} ({signed_binary_to_decimal(bin1)})")
    print(f"+ {bin2} ({signed_binary_to_decimal(bin2)})")
    print(f"  {'-' * 8}")
    print(f"  {result} ({signed_binary_to_decimal(result)})")
    print(f"  (Discard carry: {carry})")
    
    # Example 6: Subtraction Table
    print("\n--- Example 6: Binary Subtraction Rules ---")
    print("  0 - 0 = 0")
    print("  1 - 0 = 1")
    print("  1 - 1 = 0")
    print("  0 - 1 = 1 (with borrow)")
    
    print("\n" + "=" * 60)
    print("Key Concepts:")
    print("- Addition: Add bit by bit, propagate carry")
    print("- Subtraction: A - B = A + two's_complement(B)")
    print("- Overflow: Sign bit changes unexpectedly")
    print("- Positive + Positive → Negative = Overflow")
    print("- Negative + Negative → Positive = Overflow")
    print("=" * 60)

if __name__ == "__main__":
    main()