Project 4: Two’s-Complement Range Explorer

Show signed and unsigned interpretations for any bit width.

Quick Reference

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate 8-12 hours
Main Programming Language C or Python (Alternatives: Rust, Go)
Alternative Programming Languages Rust, Go
Coolness Level Level 3
Business Potential Level 1
Prerequisites Two’s complement, Bit widths
Key Topics signed ranges, overflow, sign extension

1. Learning Objectives

By completing this project, you will:

  1. Translate between representations with explicit rules.
  2. Validate and normalize input at the byte level.
  3. Produce outputs that are deterministic and testable.

2. All Theory Needed (Per-Concept Breakdown)

Two’s Complement

Fundamentals Two’s complement is the dominant way to represent signed integers in modern systems. The same bit pattern can represent an unsigned value or a signed value, depending on context. In two’s complement, negative values are encoded by inverting the bits and adding one. This scheme is preferred because addition and subtraction work the same for signed and unsigned values, which simplifies hardware and software. The sign bit is the most significant bit; if it is 1, the value is negative.

Deep Dive into the concept Two’s complement works because it makes arithmetic consistent across signedness. If you take a binary adder and add two values, the result is correct whether those values are signed or unsigned, as long as you interpret the final bits according to the chosen representation. This is the foundational advantage over earlier representations such as sign-magnitude or ones’ complement.

The representable range for n bits is -2^(n-1) to 2^(n-1)-1. The asymmetry is real: there is one extra negative number because zero has only one representation. The most negative value is represented by a 1 in the sign bit and 0s elsewhere. For 8 bits, this is 10000000, which equals -128. The most positive value is 01111111, which equals 127.

Converting a negative integer into two’s complement form is a mechanical process: write the absolute value in binary, invert all bits, then add one. Converting back is the same: if the sign bit is set, invert and add one to recover the magnitude, then apply the negative sign. This is not merely a trick; it is the mathematical structure of modular arithmetic on 2^n.

Sign extension is critical when you widen a signed value. If you move from 8 bits to 32 bits, you must replicate the sign bit into the new high bits so the numeric value remains the same. Zero-extension would misinterpret negative values as large positives. Many real-world bugs in binary parsing come from this mistake.

Overflow in signed arithmetic is subtle. If you add two positives and get a negative, you have overflow. If you add two negatives and get a positive, you have overflow. Because overflow in many languages is undefined or wraps silently, you should detect it explicitly in safety-critical code. In your projects, treat overflow as a signal that your input or range check is incorrect.

How this fit on projects This concept is a primary pillar for this project and appears again in other projects in this folder.

Definitions & key terms

  • Two’s Complement definition, scope, and usage in this project context.
  • Key vocabulary used throughout the implementation.

Mental model diagram

[Input] -> [Rule/Conversion] -> [Value] -> [Representation]

How it works (step-by-step, with invariants and failure modes)

  1. Identify the input representation and its constraints.
  2. Apply the conversion or interpretation rules.
  3. Validate bounds and emit a canonical output.
  4. Invariant: the underlying value is preserved across representations.
  5. Failure modes: invalid digits, width overflow, or order mismatch.

Minimal concrete example

INPUT: small example value
PROCESS: apply the core rule in this concept
OUTPUT: normalized representation

Common misconceptions

  • Confusing representation with value.
  • Skipping validation because “inputs look right”.

Check-your-understanding questions

  1. Explain the concept in your own words.
  2. Predict the output of a simple conversion scenario.
  3. Why does this concept matter for correct parsing?

Check-your-understanding answers

  1. The concept is the rule set that maps representation to meaning.
  2. The output follows the defined rules and preserves value.
  3. Without it, you will misinterpret bytes or bit fields.

Real-world applications

  • Binary file parsing and validation
  • Protocol field extraction
  • Debugging with hexdumps

Where you’ll apply it

  • In this project, during the core parsing and output steps.
  • Also used in: P01-universal-base-converter, P03-bitwise-logic-calculator, P09-hexdump-clone.

References

  • “Computer Systems: A Programmer’s Perspective” - Ch. 2
  • “Code” by Charles Petzold - Ch. 7-8

Key insights This concept is a repeatable rule that transforms raw bits into reliable meaning.

Summary You can only trust your output when you apply this concept deliberately and consistently.

Homework/Exercises to practice the concept

  1. Do a manual conversion or extraction by hand.
  2. Build a tiny test case and predict the output.

Solutions to the homework/exercises

  1. The manual process should match your tool output.
  2. If the output differs, revisit your assumptions about representation.

3. Project Specification

3.1 What You Will Build

Build a focused tool that takes structured input, applies the project-specific transformations, and emits a precise, verifiable output. Include input validation, clear error messages, and deterministic formatting. Exclude any optional UI features until the core logic is correct.

3.2 Functional Requirements

  1. Validated Input: Reject malformed or out-of-range values.
  2. Deterministic Output: Same input always yields the same output.
  3. Human-Readable Display: Show results in both hex and binary where relevant.

3.3 Non-Functional Requirements

  • Performance: Must handle small files or values instantly.
  • Reliability: Must not crash on invalid inputs.
  • Usability: Outputs must be unambiguous and aligned.

3.4 Example Usage / Output

$ run-tool --example
[expected output goes here]

3.5 Data Formats / Schemas / Protocols

  • Input: simple CLI arguments or a small config file.
  • Output: fixed-width hex, optional binary, and labeled fields.

3.6 Edge Cases

  • Empty input
  • Invalid digits
  • Maximum-width values
  • Unexpected file length

3.7 Real World Outcome

The learner should be able to run the tool and compare output against a known reference with no ambiguity.

3.7.1 How to Run (Copy/Paste)

  • Build commands: make or equivalent
  • Run commands: ./tool --args
  • Working directory: project root

3.7.2 Golden Path Demo (Deterministic)

A known input produces a known output that matches a prewritten test vector.

3.7.3 If CLI: exact terminal transcript

$ ./tool --demo
[result line 1]
[result line 2]

4. Solution Architecture

4.1 High-Level Design

[Input] -> [Parser] -> [Core Logic] -> [Formatter] -> [Output]

4.2 Key Components

Component Responsibility Key Decisions
Parser Validate and normalize input Strict digit validation
Core Logic Apply conversion or extraction rules Keep math explicit
Formatter Render hex/binary/text views Fixed-width alignment

4.4 Data Structures (No Full Code)

  • Fixed-width integer values
  • Byte buffers for file I/O
  • Simple structs for labeled fields

4.4 Algorithm Overview

Key Algorithm: Core Transformation

  1. Parse input into a canonical internal value.
  2. Apply project-specific conversion or extraction rules.
  3. Format the result for display.

Complexity Analysis:

  • Time: O(n) in input size
  • Space: O(1) to O(n) depending on buffering

5. Implementation Guide

5.1 Development Environment Setup

# Use a standard compiler and a minimal build script

5.2 Project Structure

project-root/
├── src/
│   ├── main.ext
│   ├── parser.ext
│   └── formatter.ext
├── tests/
│   └── test_vectors.txt
└── README.md

5.3 The Core Question You’re Answering

“How do I transform a raw representation into a reliable value and show it clearly?”

5.4 Concepts You Must Understand First

  • See the Theory section above and confirm you can explain each concept without notes.

5.5 Questions to Guide Your Design

  1. How will you validate inputs?
  2. How will you normalize outputs for comparison?
  3. How will you handle errors without hiding failures?

5.6 Thinking Exercise

Before coding, draw the data flow from input to output and label every transformation step.

5.7 The Interview Questions They’ll Ask

  1. “How do you validate binary or hex input?”
  2. “How do you detect overflow or width mismatch?”
  3. “Why is deterministic output important?”
  4. “How would you test your tool with known vectors?”

5.8 Hints in Layers

Hint 1: Start by parsing and validating a single fixed-size input.

Hint 2: Implement the core transformation in isolation and test it.

Hint 3: Add formatting after correctness is proven.

Hint 4: Compare outputs against a trusted reference tool.

5.9 Books That Will Help

Topic Book Chapter
Data representation “Computer Systems: A Programmer’s Perspective” Ch. 2
Number systems “Code” by Charles Petzold Ch. 7-8

5.10 Implementation Phases

Phase 1: Foundation (2-4 hours)

Goals:

  • Input parsing
  • Basic validation

Tasks:

  1. Implement digit validation.
  2. Parse into internal value.

Checkpoint: Parse test vectors correctly.

Phase 2: Core Functionality (4-8 hours)

Goals:

  • Core transformation logic
  • Primary output format

Tasks:

  1. Implement core math rules.
  2. Render hex and binary outputs.

Checkpoint: Output matches known results.

Phase 3: Polish & Edge Cases (2-4 hours)

Goals:

  • Error handling
  • Edge cases

Tasks:

  1. Add invalid input tests.
  2. Add max-width tests.

Checkpoint: No crashes on invalid input.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Input format hex/dec/bin support all flexibility
Output width fixed/variable fixed compare easily

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Validate conversions known vectors
Integration Tests CLI parsing sample files
Edge Case Tests boundaries max/min values

6.2 Critical Test Cases

  1. Zero input: output should be zero in all bases.
  2. Max width: output should not overflow.
  3. Invalid digit: error message, no crash.

6.3 Test Data

inputs: 0, 1, 255, 256
expected: 0x0, 0x1, 0xFF, 0x100

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Wrong base incorrect output re-check digit map
Overflow wrapped values add bounds checks
Misalignment messy output pad columns

7.2 Debugging Strategies

  • Compare against a trusted tool for random inputs.
  • Print intermediate values in binary.

7.3 Performance Traps

  • Avoid reading entire files when streaming is enough.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add binary output padding.
  • Add uppercase/lowercase hex toggles.

8.2 Intermediate Extensions

  • Add batch conversion from a file.
  • Add JSON output mode.

8.3 Advanced Extensions

  • Add big-integer support.
  • Add a reversible binary patch feature.

9. Real-World Connections

9.1 Industry Applications

  • Binary file parsing and validation tools
  • Protocol debugging utilities
  • xxd-like hex tools
  • file-type identification utilities

9.3 Interview Relevance

  • Bit manipulation and data representation questions

10. Resources

10.1 Essential Reading

  • “Computer Systems: A Programmer’s Perspective” - Ch. 2
  • “Code” by Charles Petzold - Ch. 7-8

10.2 Video Resources

  • University lecture on data representation (search by course name)