Project 3: Data Lab Clone
Project 3: Data Lab Clone
Build a bit-manipulation puzzle framework that enforces operator restrictions, runs property-based tests, and produces clear failure explanations—mastering hardware-style thinking through constraints.
Quick Reference
| Attribute | Value |
|---|---|
| Difficulty | Advanced |
| Time Estimate | 1-2 weeks |
| Language | C (Alternatives: Rust, Zig, C++) |
| Prerequisites | Solid C, comfort writing tests, Project 2 (Bitwise Data Inspector) recommended |
| Key Topics | Bit-level operators, Boolean algebra, property-based testing, undefined behavior |
| CS:APP Chapters | 2 |
1. Learning Objectives
By completing this project, you will:
- Think at the bit level: Derive solutions using only fundamental bitwise operations
- Master Boolean algebra: Apply De Morgan’s laws, absorption, and distribution fluently
- Understand operator restrictions: See why constraints force deeper understanding
- Internalize edge cases: Know INT_MIN, MAX_INT, and boundary behaviors cold
- Build property-based tests: Generate adversarial inputs that catch subtle bugs
- Produce diagnostic output: Explain failures in ways that teach, not just report
- Avoid undefined behavior: Recognize and prevent implementation-defined traps
2. Deep Theoretical Foundation
2.1 Bitwise Operators in Depth
Every bit-manipulation puzzle ultimately decomposes into these primitive operations:
AND (&) - The Masking Operator
┌────────────────────────────────────────────────────────────────┐
│ BITWISE AND (&) │
├────────────────────────────────────────────────────────────────┤
│ │
│ Truth Table: Example: │
│ A B A&B 0b11001010 │
│ 0 0 0 & 0b10101100 │
│ 0 1 0 ────────────── │
│ 1 0 0 0b10001000 │
│ 1 1 1 │
│ │
│ Key Uses: │
│ - Extract bits (masking): x & 0x0F gets lower 4 bits │
│ - Clear bits: x & ~mask clears bits where mask is 1 │
│ - Test bits: (x & mask) != 0 tests if any masked bits set │
│ │
│ Algebraic Properties: │
│ - Commutative: a & b = b & a │
│ - Associative: (a & b) & c = a & (b & c) │
│ - Identity: x & ~0 = x (all 1s) │
│ - Annihilator: x & 0 = 0 │
│ - Idempotent: x & x = x │
│ │
└────────────────────────────────────────────────────────────────┘
OR (|) - The Combining Operator
┌────────────────────────────────────────────────────────────────┐
│ BITWISE OR (|) │
├────────────────────────────────────────────────────────────────┤
│ │
│ Truth Table: Example: │
│ A B A|B 0b11001010 │
│ 0 0 0 | 0b10101100 │
│ 0 1 1 ────────────── │
│ 1 0 1 0b11101110 │
│ 1 1 1 │
│ │
│ Key Uses: │
│ - Set bits: x | mask sets bits where mask is 1 │
│ - Combine flags: flags = FLAG_A | FLAG_B │
│ - Create masks: 0 | (1 << n) creates single-bit mask │
│ │
│ Algebraic Properties: │
│ - Commutative: a | b = b | a │
│ - Associative: (a | b) | c = a | (b | c) │
│ - Identity: x | 0 = x │
│ - Annihilator: x | ~0 = ~0 (all 1s) │
│ - Idempotent: x | x = x │
│ │
└────────────────────────────────────────────────────────────────┘
XOR (^) - The Toggle/Difference Operator
┌────────────────────────────────────────────────────────────────┐
│ BITWISE XOR (^) │
├────────────────────────────────────────────────────────────────┤
│ │
│ Truth Table: Example: │
│ A B A^B 0b11001010 │
│ 0 0 0 ^ 0b10101100 │
│ 0 1 1 ────────────── │
│ 1 0 1 0b01100110 │
│ 1 1 0 │
│ │
│ Key Uses: │
│ - Toggle bits: x ^ mask flips bits where mask is 1 │
│ - Swap without temp: a^=b; b^=a; a^=b; │
│ - Detect difference: (a ^ b) is 0 iff a == b │
│ - Parity: x ^ x ^ x ^ ... reduces odd/even count │
│ │
│ Algebraic Properties: │
│ - Commutative: a ^ b = b ^ a │
│ - Associative: (a ^ b) ^ c = a ^ (b ^ c) │
│ - Identity: x ^ 0 = x │
│ - Self-inverse: x ^ x = 0 │
│ - Double XOR: a ^ b ^ b = a │
│ │
└────────────────────────────────────────────────────────────────┘
NOT (~) - The Complement Operator
┌────────────────────────────────────────────────────────────────┐
│ BITWISE NOT (~) │
├────────────────────────────────────────────────────────────────┤
│ │
│ Truth Table: Example (8-bit): │
│ A ~A ~ 0b11001010 │
│ 0 1 ────────────── │
│ 1 0 0b00110101 │
│ │
│ Key Uses: │
│ - Two's complement negation: -x = ~x + 1 │
│ - Clear bits: x & ~mask │
│ - All 1s mask: ~0 │
│ - Test all bits clear: !(~x) means all bits are 1 │
│ │
│ Critical Insight: │
│ ~x + 1 = -x (two's complement negation) │
│ Therefore: ~x = -x - 1 = -(x+1) │
│ │
│ Algebraic Properties: │
│ - Double negation: ~~x = x │
│ - De Morgan: ~(a & b) = ~a | ~b │
│ - De Morgan: ~(a | b) = ~a & ~b │
│ │
└────────────────────────────────────────────────────────────────┘
Left Shift (<<) - Multiplication by Powers of 2
┌────────────────────────────────────────────────────────────────┐
│ LEFT SHIFT (<<) │
├────────────────────────────────────────────────────────────────┤
│ │
│ Operation: Example (8-bit): │
│ x << n 0b00001011 << 2 │
│ = x * 2^n ────────────── │
│ 0b00101100 │
│ │
│ Key Uses: │
│ - Multiply by 2^n: x << 3 = x * 8 │
│ - Create bit mask: 1 << n has bit n set │
│ - Align to position: value << bit_position │
│ │
│ DANGER - Undefined Behavior: │
│ - Shifting by >= width of type is UNDEFINED │
│ - 1 << 32 on 32-bit int is UNDEFINED │
│ - Negative shift amount is UNDEFINED │
│ - Shifting signed negative values has impl-defined bits │
│ │
│ Safe Pattern: │
│ 1U << n (use unsigned to avoid sign bit issues) │
│ Ensure: 0 <= n < bit_width │
│ │
└────────────────────────────────────────────────────────────────┘
Right Shift (>>) - Division by Powers of 2
┌────────────────────────────────────────────────────────────────┐
│ RIGHT SHIFT (>>) │
├────────────────────────────────────────────────────────────────┤
│ │
│ Two Types: │
│ │
│ LOGICAL (unsigned): Fill with 0s │
│ 0b10110000 >> 2 = 0b00101100 │
│ │
│ ARITHMETIC (signed): Fill with sign bit │
│ 0b10110000 >> 2 = 0b11101100 (if negative) │
│ 0b01110000 >> 2 = 0b00011100 (if positive) │
│ │
│ Key Uses: │
│ - Divide by 2^n: x >> 3 = x / 8 (rounds toward -inf) │
│ - Extract bit: (x >> n) & 1 gets bit n │
│ - Sign extension: x >> 31 gives all 1s if negative │
│ │
│ DANGER - Implementation Defined: │
│ - Right shift of negative signed values: behavior varies! │
│ - Most compilers use arithmetic shift, but NOT guaranteed │
│ │
│ Safe Pattern: │
│ Use unsigned for logical shift │
│ For arithmetic: explicitly test sign bit │
│ │
└────────────────────────────────────────────────────────────────┘
2.2 Common Bit Manipulation Patterns and Identities
These patterns appear repeatedly in bit puzzles:
Sign Extension and Propagation
// Get sign bit (for 32-bit int)
int sign = (x >> 31) & 1;
// Sign mask: all 1s if negative, all 0s if positive
int sign_mask = x >> 31; // Arithmetic shift
// Apply sign: select between positive and negative result
// result = sign_mask ? negative_val : positive_val
int result = (sign_mask & negative_val) | (~sign_mask & positive_val);
Testing Conditions Without Comparisons
// Is x zero?
// !!x is 0 if x==0, 1 otherwise
int is_nonzero = !!x;
int is_zero = !x;
// Is x negative?
int is_negative = (x >> 31) & 1;
// Is x positive (not zero, not negative)?
int is_positive = !((x >> 31) | !x);
// Do x and y have same sign?
int same_sign = !((x ^ y) >> 31);
Absolute Value Without Branching
// Method: (x ^ mask) - mask where mask = x >> 31
int mask = x >> 31; // All 1s if negative, all 0s if positive
int abs_x = (x ^ mask) - mask;
// Why this works:
// If x >= 0: mask = 0, so (x ^ 0) - 0 = x
// If x < 0: mask = -1, so (x ^ -1) - (-1) = ~x + 1 = -x
Conditional Selection (Ternary Without Branching)
// Select a if condition, else b
// condition must be 0 or 1
int result = (condition & a) | (~condition & b); // WRONG if condition != 0,-1
// Correct version: expand condition to full mask
int mask = ~condition + 1; // 0 -> 0, nonzero -> all 1s (only works for 0/1)
// Better: arithmetic shift
int mask = ((!condition) << 31) >> 31; // 0 if true, -1 if false... wait, inverted!
// Cleanest:
int mask = ~(!!condition) + 1; // 0 -> 0, nonzero -> -1 (all 1s)
int result = (mask & a) | (~mask & b);
Detecting Powers of Two
// x is power of 2 if x > 0 and only one bit is set
// x & (x-1) clears the lowest set bit
int is_power_of_2 = x && !(x & (x - 1));
// With only bitwise ops (harder):
// Need to check exactly one bit set AND not zero AND not negative
2.3 De Morgan’s Laws for Bits
De Morgan’s laws are essential for transforming expressions:
┌────────────────────────────────────────────────────────────────┐
│ DE MORGAN'S LAWS │
├────────────────────────────────────────────────────────────────┤
│ │
│ Law 1: ~(a & b) = ~a | ~b │
│ Law 2: ~(a | b) = ~a & ~b │
│ │
│ Proof (bitwise, for each bit position): │
│ │
│ a b a&b ~(a&b) ~a ~b ~a|~b │
│ 0 0 0 1 1 1 1 = ~(a&b) │
│ 0 1 0 1 1 0 1 │
│ 1 0 0 1 0 1 1 │
│ 1 1 1 0 0 0 0 │
│ │
│ Application - Negating Conditions: │
│ NOT (x AND y) becomes (NOT x) OR (NOT y) │
│ NOT (x OR y) becomes (NOT x) AND (NOT y) │
│ │
│ Example - Transform !(a & b) when you can't use !: │
│ !(a & b) = (!a) | (!b) │
│ But what is !x in terms of bitwise? │
│ !x = (x == 0) = 1 when all bits zero │
│ │
└────────────────────────────────────────────────────────────────┘
Extended De Morgan Patterns
// Negating complex conditions
// !(a && b) = !a || !b
// !(a || b) = !a && !b
// In bitwise terms (where && and || are logical):
// If we represent true/false as -1/0 (all 1s/all 0s):
// ~(a & b) = ~a | ~b works directly
// For 0/1 representation, need conversion:
// Convert 0/1 to 0/-1: mask = ~(x - 1) or mask = -x (if x is 0 or 1)
2.4 Algebraic Properties of Bit Operations
Understanding these lets you simplify and transform expressions:
┌────────────────────────────────────────────────────────────────┐
│ BOOLEAN ALGEBRA IDENTITIES │
├────────────────────────────────────────────────────────────────┤
│ │
│ IDENTITY: │
│ x & 1...1 = x x | 0 = x x ^ 0 = x │
│ │
│ ANNIHILATION: │
│ x & 0 = 0 x | 1...1 = 1...1 │
│ │
│ IDEMPOTENCE: │
│ x & x = x x | x = x │
│ │
│ COMPLEMENT: │
│ x & ~x = 0 x | ~x = 1...1 x ^ x = 0 │
│ │
│ ABSORPTION: │
│ x & (x | y) = x x | (x & y) = x │
│ │
│ DISTRIBUTIVE: │
│ x & (y | z) = (x & y) | (x & z) │
│ x | (y & z) = (x | y) & (x | z) │
│ x ^ (y & z) != (x ^ y) & (x ^ z) [XOR doesn't distribute!] │
│ │
│ XOR SPECIAL: │
│ x ^ y ^ y = x (double XOR cancels) │
│ x ^ y = y ^ x (commutative) │
│ (x ^ y) ^ z = x ^ (y ^ z) (associative) │
│ x & (y ^ z) = (x & y) ^ (x & z) (AND distributes over XOR) │
│ │
└────────────────────────────────────────────────────────────────┘
2.5 Why Certain Operations Are NOT Allowed
The genius of Data Lab is the restriction. Here’s why specific operations are banned:
Why No Conditionals (if, ? :, comparison operators)?
┌────────────────────────────────────────────────────────────────┐
│ THE PEDAGOGICAL PURPOSE OF RESTRICTIONS │
├────────────────────────────────────────────────────────────────┤
│ │
│ High-Level Thinking: Low-Level Reality: │
│ │
│ if (x < 0) How does the CPU actually │
│ return -x; compute this? │
│ else │
│ return x; It uses bit manipulation! │
│ │
│ The conditional HIDES the bit-level truth: │
│ - Sign is just the high bit │
│ - Negation is ~x + 1 │
│ - Selection uses AND/OR masking │
│ │
│ By banning conditionals, you must discover: │
│ int mask = x >> 31; // Sign-extend to all bits │
│ return (x ^ mask) - mask; // Conditional negate │
│ │
│ THIS IS HOW HARDWARE WORKS! │
│ - No branches in combinational logic │
│ - Everything is gates (AND, OR, NOT, XOR) │
│ - Selection is multiplexing via masks │
│ │
└────────────────────────────────────────────────────────────────┘
Why Restrict Operator Count?
The restriction on number of operators forces:
1. Finding the ELEGANT solution, not the brute-force one
2. Understanding algebraic simplifications
3. Thinking like a hardware designer (fewer gates = faster/cheaper)
Example - Is x == y?
Naive: return (x - y == 0); // Uses subtraction and comparison
Better: return !(x ^ y); // Uses XOR and logical NOT (2 ops)
Why No Multiplication/Division?
These operations are EXPENSIVE in hardware:
- Multiplication: O(n^2) gates for n-bit multiply
- Division: Even worse, often iterative
Bit shifts are O(n) - just wire routing!
x * 8 = x << 3 (free in hardware, just route wires)
By banning multiply/divide, you learn to:
- Decompose into shifts: x * 5 = (x << 2) + x
- Think about what operations actually cost
2.6 Property-Based Testing Concepts
Unlike example-based testing (“does f(5) return 10?”), property-based testing verifies invariants over random inputs:
┌────────────────────────────────────────────────────────────────┐
│ PROPERTY-BASED TESTING │
├────────────────────────────────────────────────────────────────┤
│ │
│ Example-Based: │
│ assert(abs(-5) == 5); // One specific case │
│ assert(abs(0) == 0); // Another case │
│ assert(abs(3) == 3); // And another │
│ // But what about INT_MIN? Edge cases? │
│ │
│ Property-Based: │
│ for (random x in int32_range): │
│ assert(abs(x) >= 0); // Non-negative │
│ assert(abs(x) == abs(-x)); // Symmetry │
│ assert(abs(x) * abs(x) >= 0); // Squared >= 0 │
│ if (x != INT_MIN): │
│ assert(abs(abs(x)) == abs(x)); // Idempotent │
│ │
│ Key Properties to Test: │
│ - Identity: f(identity_input) = expected │
│ - Idempotence: f(f(x)) = f(x) │
│ - Symmetry: f(a, b) = f(b, a) for commutative ops │
│ - Inverse: f(g(x)) = x │
│ - Bounds: output always in valid range │
│ - Monotonicity: if x < y then f(x) <= f(y) │
│ │
│ Why This Catches Bugs: │
│ - Random inputs hit cases you'd never think of │
│ - Edge cases (0, -1, INT_MIN, MAX_INT) are generated │
│ - Shrinking finds minimal failing case │
│ │
└────────────────────────────────────────────────────────────────┘
2.7 Undefined Behavior in C
Bit manipulation is a minefield of undefined behavior (UB). Know these:
┌────────────────────────────────────────────────────────────────┐
│ UNDEFINED BEHAVIOR DANGER ZONES │
├────────────────────────────────────────────────────────────────┤
│ │
│ 1. SHIFT BY >= TYPE WIDTH │
│ ────────────────────────── │
│ int x = 1; │
│ x << 32; // UNDEFINED for 32-bit int │
│ x << -1; // UNDEFINED (negative shift) │
│ │
│ Fix: Always check shift amount │
│ if (n >= 0 && n < 32) result = x << n; │
│ │
│ 2. SIGNED OVERFLOW │
│ ───────────────────── │
│ int x = INT_MAX; │
│ x + 1; // UNDEFINED (signed overflow) │
│ │
│ But unsigned is defined: │
│ unsigned u = UINT_MAX; │
│ u + 1; // Defined: wraps to 0 │
│ │
│ 3. NEGATING INT_MIN │
│ ─────────────────── │
│ int x = INT_MIN; // -2147483648 │
│ -x; // UNDEFINED (INT_MAX is 2147483647) │
│ │
│ Two's complement: -INT_MIN = INT_MIN (wraps) │
│ But C says it's undefined for signed types! │
│ │
│ 4. RIGHT SHIFT OF NEGATIVE │
│ ────────────────────────── │
│ int x = -1; │
│ x >> 1; // IMPLEMENTATION-DEFINED (not undefined) │
│ // Usually arithmetic shift, but not guaranteed │
│ │
│ Safe alternative: │
│ (unsigned)x >> 1; // Guaranteed logical shift │
│ │
└────────────────────────────────────────────────────────────────┘
The INT_MIN Problem
// INT_MIN is special in two's complement:
// 32-bit: INT_MIN = -2147483648 = 0x80000000
// There's no positive equivalent! (INT_MAX = 2147483647)
// This breaks many "obvious" implementations:
// BROKEN absolute value:
int abs_broken(int x) {
if (x < 0) return -x; // -INT_MIN is undefined!
return x;
}
// Safe absolute value (returns -1 on INT_MIN, or handle specially):
int abs_safe(int x) {
if (x == INT_MIN) return INT_MAX; // Or handle error
if (x < 0) return -x;
return x;
}
// Bitwise absolute value:
int abs_bits(int x) {
int mask = x >> 31;
return (x ^ mask) - mask;
// For INT_MIN: mask = -1
// (INT_MIN ^ -1) - (-1) = ~INT_MIN + 1 = INT_MIN
// So it returns INT_MIN (wraps), which is what hardware does
}
3. Project Specification
3.1 What You Will Build
A complete bit-manipulation puzzle framework consisting of:
- Puzzle Functions: A set of functions implementing operations using restricted operators
- Restriction Checker: Static analysis to verify operator constraints are met
- Test Harness: Property-based and exhaustive testing for puzzle correctness
- Scoreboard: Grading based on correctness, operator count, and compliance
3.2 Functional Requirements
Puzzle Categories
┌────────────────────────────────────────────────────────────────┐
│ PUZZLE CATEGORIES │
├────────────────────────────────────────────────────────────────┤
│ │
│ Category 1: Bit Manipulation (Chapters 2.1) │
│ - bitAnd(x, y): Implement & using only | and ~ │
│ - getByte(x, n): Extract byte n from x │
│ - logicalShift(x, n): Logical right shift │
│ - bitCount(x): Count number of 1 bits │
│ - rotateRight(x, n): Rotate x right by n bits │
│ │
│ Category 2: Two's Complement (Chapter 2.2-2.3) │
│ - isNegative(x): Return 1 if x < 0 │
│ - isEqual(x, y): Return 1 if x == y │
│ - negate(x): Return -x │
│ - isPositive(x): Return 1 if x > 0 │
│ - absVal(x): Return absolute value │
│ - addOK(x, y): Return 1 if x+y doesn't overflow │
│ │
│ Category 3: Conditionals (Chapter 2 + creativity) │
│ - conditional(x, y, z): Return y if x, else z │
│ - isLessOrEqual(x, y): Return 1 if x <= y │
│ - isAsciiDigit(x): Return 1 if 0x30 <= x <= 0x39 │
│ │
│ Category 4: Floating Point (Chapter 2.4) - Optional │
│ - floatScale2(f): Return 2*f for float bits │
│ - floatInt2Float(x): Convert int to float bits │
│ │
└────────────────────────────────────────────────────────────────┘
Operator Restrictions
Each puzzle specifies:
- Allowed operators: The set of operators that may be used
- Max operators: Maximum number of operators (excluding assignments)
- Forbidden constructs: Control flow, function calls, macros, casts (usually)
Example restriction specification:
/*
* isNegative - return 1 if x < 0, return 0 otherwise
* Example: isNegative(-1) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int isNegative(int x) {
// Your implementation here
}
3.3 Non-Functional Requirements
- Correctness: Pass all test cases including edge cases
- Compliance: Meet operator restrictions exactly
- Portability: Work on 32-bit two’s complement machines (common assumption)
- Documentation: Clear explanations of why each solution works
- Testability: All puzzles have automated verification
3.4 Example Puzzle Implementations
Puzzle: bitAnd
/*
* bitAnd - x & y using only | and ~
* Example: bitAnd(6, 5) = 4
* Legal ops: | ~
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
// De Morgan's Law: x & y = ~(~x | ~y)
return ~(~x | ~y);
}
/*
* Why this works:
*
* De Morgan's Law states: ~(a | b) = ~a & ~b
* Rearranging: a & b = ~(~a | ~b)
*
* Proof by truth table:
* x y ~x ~y ~x|~y ~(~x|~y) x&y
* 0 0 1 1 1 0 0
* 0 1 1 0 1 0 0
* 1 0 0 1 1 0 0
* 1 1 0 0 0 1 1
*
* Column ~(~x|~y) matches column x&y. QED.
*
* Operator count: 4 (two ~, one |, one ~)
*/
Puzzle: isNegative
/*
* isNegative - return 1 if x < 0, return 0 otherwise
* Example: isNegative(-1) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int isNegative(int x) {
// The sign bit is the most significant bit
// Right shift by 31 to move it to position 0
// AND with 1 to isolate it
return (x >> 31) & 1;
}
/*
* Why this works:
*
* In two's complement, negative numbers have MSB = 1, non-negative have MSB = 0.
*
* x >> 31:
* - For negative x (MSB = 1): arithmetic shift fills with 1s, result is -1 (0xFFFFFFFF)
* - For non-negative x (MSB = 0): fills with 0s, result is 0
*
* (x >> 31) & 1:
* - -1 & 1 = 1
* - 0 & 1 = 0
*
* Edge cases:
* - x = 0: 0 >> 31 = 0, 0 & 1 = 0
* - x = -1: -1 >> 31 = -1, -1 & 1 = 1
* - x = INT_MIN: INT_MIN >> 31 = -1, -1 & 1 = 1
* - x = INT_MAX: INT_MAX >> 31 = 0, 0 & 1 = 0
*
* Operator count: 2 (one >>, one &)
*/
Puzzle: isEqual
/*
* isEqual - return 1 if x == y, and 0 otherwise
* Example: isEqual(5, 5) = 1, isEqual(4, 5) = 0
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int isEqual(int x, int y) {
// XOR is zero iff both inputs are identical
// Logical NOT converts 0 to 1, nonzero to 0
return !(x ^ y);
}
/*
* Why this works:
*
* XOR truth table shows: a ^ b = 0 iff a = b
*
* For all 32 bits:
* - If x == y, every bit matches, so x ^ y = 0
* - If x != y, at least one bit differs, so x ^ y != 0
*
* Logical NOT (!):
* - !0 = 1
* - !(nonzero) = 0
*
* Operator count: 2 (one ^, one !)
*/
Puzzle: absVal
/*
* absVal - return absolute value of x
* Example: absVal(-1) = 1
* Assume: You may assume -TMax <= x <= TMax
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 10
* Rating: 4
*/
int absVal(int x) {
// Create a mask that's all 1s for negative, all 0s for non-negative
int mask = x >> 31;
// XOR with mask: toggles all bits if negative, no change if positive
// Subtract mask: adds 1 if negative (since mask = -1), no change if positive
return (x ^ mask) + (~mask + 1);
// Equivalent to: (x ^ mask) - mask
// But we can't use -, so: (x ^ mask) + (~mask + 1) = (x ^ mask) - mask
}
/*
* Why this works:
*
* Let mask = x >> 31:
* - If x >= 0: mask = 0 (all zeros)
* - If x < 0: mask = -1 (all ones)
*
* Case 1: x >= 0
* mask = 0
* x ^ 0 = x
* ~0 + 1 = -(-1) + 1 = 0... wait, that's wrong
*
* Actually: ~mask + 1 = ~0 + 1 = 0xFFFFFFFF + 1 = 0 (overflow to 0)
* So: (x ^ 0) + 0 = x
*
* Case 2: x < 0
* mask = -1 (0xFFFFFFFF)
* x ^ (-1) = ~x
* ~(-1) + 1 = 0 + 1 = 1
* So: ~x + 1 = -x
*
* Simpler version (if subtraction allowed):
* return (x ^ mask) - mask;
*
* Note: For x = INT_MIN, this returns INT_MIN (as expected, since -INT_MIN
* overflows to INT_MIN in two's complement).
*
* Operator count: 6 (>>, ^, ~, +, +, implicit grouping)
*/
Puzzle: conditional
/*
* conditional - same as x ? y : z
* Example: conditional(2, 4, 5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
// Convert x to mask: 0 if x==0, all 1s if x!=0
int mask = ~(!!x) + 1; // !!x is 0 or 1, ~0+1=0, ~1+1=-1
// Select y if mask is all 1s, z if mask is 0
return (mask & y) | (~mask & z);
}
/*
* Why this works:
*
* Step 1: Normalize x to 0 or 1
* !!x = 0 if x == 0
* !!x = 1 if x != 0
*
* Step 2: Create mask
* If !!x == 0: ~0 + 1 = -1 + 1 = 0 (all zeros)
* If !!x == 1: ~1 + 1 = -2 + 1 = -1 (all ones)
*
* Step 3: Select using mask
* If mask == 0: (0 & y) | (-1 & z) = 0 | z = z
* If mask == -1: (-1 & y) | (0 & z) = y | 0 = y
*
* Wait, I had it backwards! Let me fix:
* mask = ~(!!x) + 1 when x != 0 gives ~1 + 1 = -1 (all 1s)
* mask = ~(!!x) + 1 when x == 0 gives ~0 + 1 = 0
*
* So (mask & y) | (~mask & z):
* x != 0: (-1 & y) | (0 & z) = y
* x == 0: (0 & y) | (-1 & z) = z
*
* Operator count: 8 (!, !, ~, +, &, ~, &, |)
*/
3.5 Test Harness Output Example
$ ./btest
Running tests for bits.c...
═══════════════════════════════════════════════════════════════
DATA LAB RESULTS
═══════════════════════════════════════════════════════════════
Puzzle | Score | Ops | Limit | Status
─────────────────|────────|──────|───────|────────
bitAnd | 1 | 4 | 8 | PASS
getByte | 2 | 3 | 6 | PASS
isNegative | 2 | 2 | 6 | PASS
isEqual | 2 | 2 | 5 | PASS
absVal | 4 | 6 | 10 | PASS
conditional | 3 | 8 | 16 | PASS
isLessOrEqual | 3 | 14 | 24 | PASS
logicalShift | 3 | 7 | 20 | PASS
bitCount | 4 | 36 | 40 | PASS
═══════════════════════════════════════════════════════════════
TOTAL SCORE: 24/24 9/9 puzzles solved
═══════════════════════════════════════════════════════════════
Test Statistics:
- Total tests run: 1,845,012
- Exhaustive tests: 9 puzzles (small inputs)
- Random tests: 1,000,000 per puzzle
- Edge case tests: Special values (0, -1, INT_MIN, INT_MAX, ...)
All puzzles PASSED!
3.6 Failure Explanation Example
When a puzzle fails, the harness should explain clearly:
═══════════════════════════════════════════════════════════════
FAILURE REPORT
═══════════════════════════════════════════════════════════════
Puzzle: absVal
Status: FAILED
─────────────────────────────────────────────────────────────────
FAILING TEST CASE:
Input: x = -2147483648 (0x80000000, INT_MIN)
Expected: 2147483648 (but this overflows int!)
Got: -2147483648 (0x80000000)
EXPLANATION:
INT_MIN is a special case in two's complement.
-INT_MIN = INT_MIN because:
~INT_MIN + 1 = 0x7FFFFFFF + 1 = 0x80000000 = INT_MIN
This is the ONLY integer where negation doesn't work as expected.
The reference solution defines absVal(INT_MIN) = INT_MIN.
Your solution returned -2147483648, which MATCHES the reference.
This is actually CORRECT for the two's complement definition.
[Re-running with corrected reference... PASS]
─────────────────────────────────────────────────────────────────
OPERATOR VIOLATION DETECTED:
Puzzle: conditional
Violation: Used disallowed operator '-'
Line 42: return (mask & y) - (~mask & z);
^
Allowed operators: ! ~ & ^ | + << >>
SUGGESTION: Replace subtraction with addition of negation:
a - b --> a + (~b + 1)
─────────────────────────────────────────────────────────────────
4. Solution Architecture
4.1 High-Level Design
┌─────────────────────────────────────────────────────────────────────────┐
│ DATA LAB FRAMEWORK │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ bits.c │ │ dlc.py │ │ btest.c │ │
│ │ (Puzzles) │───▶│ (Checker) │ │ (Tester) │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Operator │ │ │
│ │ │ Violations │ │ │
│ │ └──────────────┘ │ │
│ │ │ │
│ └───────────────────┬───────────────────┘ │
│ ▼ │
│ ┌──────────────┐ │
│ │ Reference │ │
│ │ Solutions │ │
│ │ (hidden) │ │
│ └──────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────┐ │
│ │ Test Engine │ │
│ │ - Edge case tests │ │
│ │ - Random tests │ │
│ │ - Exhaustive tests (small domains) │ │
│ └──────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────┐ │
│ │ Scoreboard │ │
│ └──────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4.2 Component Details
| Component | Responsibility | Implementation |
|---|---|---|
bits.c |
Contains student puzzle implementations | C source file with function stubs |
dlc (Data Lab Checker) |
Verifies operator restrictions | Python/C lexer that counts operators |
btest |
Tests puzzle correctness | C program with reference solutions |
driver.pl |
Orchestrates grading | Perl/Python script |
fshow/ishow |
Helper tools for float/int inspection | Utility programs |
4.3 Data Structures
// Puzzle descriptor
typedef struct {
const char *name; // "absVal"
int (*func)(int); // Pointer to student function
int (*ref)(int); // Pointer to reference solution
int max_ops; // Maximum allowed operators
int rating; // Difficulty rating (1-4)
const char *allowed_ops; // "! ~ & ^ | + << >>"
} PuzzleDesc;
// For two-argument puzzles
typedef struct {
const char *name;
int (*func)(int, int);
int (*ref)(int, int);
int max_ops;
int rating;
const char *allowed_ops;
} PuzzleDesc2;
// Test case
typedef struct {
int input1;
int input2; // 0 for single-arg puzzles
int expected;
const char *description; // "INT_MIN edge case"
} TestCase;
// Test result
typedef struct {
int passed;
int failed;
int total;
int operator_count;
int violation; // 1 if operator violation detected
char *error_message;
} TestResult;
4.4 Test Generation Strategy
┌────────────────────────────────────────────────────────────────┐
│ TEST GENERATION STRATEGY │
├────────────────────────────────────────────────────────────────┤
│ │
│ 1. EDGE CASES (Always tested first) │
│ ──────────────────────────────── │
│ Single-arg puzzles: │
│ - 0, 1, -1 │
│ - INT_MIN (0x80000000) │
│ - INT_MAX (0x7FFFFFFF) │
│ - Powers of 2: 2, 4, 8, ... │
│ - Alternating bits: 0x55555555, 0xAAAAAAAA │
│ - All ones: 0xFFFFFFFF │
│ │
│ Two-arg puzzles: │
│ - Same edge cases for both arguments │
│ - (0, 0), (0, INT_MIN), (INT_MIN, INT_MIN), etc. │
│ - Sign combinations: (+,+), (+,-), (-,+), (-,-) │
│ │
│ 2. RANDOM TESTS (High volume) │
│ ────────────────────────────── │
│ - 100,000+ random 32-bit values │
│ - Bias toward edge regions: │
│ - 50% uniformly random │
│ - 25% near 0 (±1000) │
│ - 25% near boundaries (INT_MIN+k, INT_MAX-k) │
│ │
│ 3. EXHAUSTIVE TESTS (Small domains) │
│ ─────────────────────────────────── │
│ For puzzles with small input domains: │
│ - getByte(x, n): n in 0-3, so test all n │
│ - logicalShift(x, n): n in 0-31, test all n │
│ - isAsciiDigit(x): only care about 8-bit range │
│ │
└────────────────────────────────────────────────────────────────┘
5. Implementation Guide
5.1 Project Structure
data-lab/
├── src/
│ ├── bits.c # Student puzzle implementations
│ ├── bits.h # Puzzle declarations
│ ├── btest.c # Test harness main
│ ├── test_engine.c # Test generation and execution
│ ├── test_engine.h
│ ├── reference.c # Hidden reference solutions
│ └── decl.c # Puzzle descriptors
├── tools/
│ ├── dlc.py # Operator checker (Python)
│ ├── fshow.c # Float bit inspector
│ └── ishow.c # Int bit inspector
├── tests/
│ ├── edge_cases.h # Edge case definitions
│ └── test_vectors.h # Pre-generated test data
├── Makefile
├── driver.pl # Grading script
└── README
5.2 Implementation Phases
Phase 1: Core Infrastructure (Days 1-3)
Goals:
- Set up build system
- Implement operator counting/checking
- Create basic test harness
Tasks:
- Create
bits.cwith puzzle stubs: ```c /*- bits.c - Source file with your solutions. *
- Each function has a maximum number of operators and a rating.
- Your job is to implement the functions using only the allowed operators. */
#include “bits.h”
/*
-
bitAnd - x & y using only and ~ -
Legal ops: ~ - Max ops: 8
- Rating: 1 */ int bitAnd(int x, int y) { return 2; // Replace with your solution }
// … more puzzles …
2. Implement operator checker (`dlc.py`):
```python
#!/usr/bin/env python3
"""
Data Lab Checker - Verifies operator restrictions in bits.c
"""
import re
import sys
from dataclasses import dataclass
from typing import List, Set, Dict
@dataclass
class PuzzleSpec:
name: str
allowed_ops: Set[str]
max_ops: int
# Operator patterns (tokens)
OPERATORS = {
'!': 'logical_not',
'~': 'bitwise_not',
'&': 'bitwise_and',
'^': 'bitwise_xor',
'|': 'bitwise_or',
'+': 'plus',
'-': 'minus',
'<<': 'left_shift',
'>>': 'right_shift',
'*': 'multiply',
'/': 'divide',
'%': 'modulo',
'<': 'less_than',
'>': 'greater_than',
'<=': 'less_equal',
'>=': 'greater_equal',
'==': 'equal',
'!=': 'not_equal',
'&&': 'logical_and',
'||': 'logical_or',
}
def check_operators(source: str, spec: PuzzleSpec) -> tuple[int, List[str]]:
"""Count operators and check for violations."""
violations = []
count = 0
# Simplified tokenization (real version would use proper lexer)
# ... implementation details ...
return count, violations
- Create basic test runner: ```c // btest.c - Basic test harness
#include
// Reference solutions (in real lab, these are hidden) int ref_bitAnd(int x, int y) { return x & y; } int ref_isNegative(int x) { return x < 0; } // …
typedef int (test_func1)(int); typedef int (test_func2)(int, int);
int test_one_arg(const char *name, test_func1 student, test_func1 ref) { int edge_cases[] = {0, 1, -1, INT_MIN, INT_MAX, 0x55555555, 0xAAAAAAAA}; int n_edge = sizeof(edge_cases) / sizeof(edge_cases[0]); int failures = 0;
// Test edge cases
for (int i = 0; i < n_edge; i++) {
int x = edge_cases[i];
int expected = ref(x);
int got = student(x);
if (got != expected) {
printf("FAIL: %s(0x%08x) = 0x%08x, expected 0x%08x\n",
name, x, got, expected);
failures++;
}
}
// Random tests
for (int i = 0; i < 100000; i++) {
int x = rand() ^ (rand() << 15);
int expected = ref(x);
int got = student(x);
if (got != expected) {
printf("FAIL: %s(0x%08x) = 0x%08x, expected 0x%08x\n",
name, x, got, expected);
failures++;
if (failures > 10) {
printf("Too many failures, stopping...\n");
break;
}
}
}
return failures == 0; }
int main() { int score = 0; int total = 0;
printf("Running Data Lab tests...\n\n");
// Test each puzzle
if (test_one_arg("isNegative", isNegative, ref_isNegative)) {
printf(" isNegative: PASS\n");
score += 2;
} else {
printf(" isNegative: FAIL\n");
}
total += 2;
// ... more tests ...
printf("\nTotal Score: %d/%d\n", score, total);
return (score == total) ? 0 : 1; } ```
Checkpoint: Can compile bits.c and run basic tests.
Phase 2: Implement Core Puzzles (Days 4-7)
Goals:
- Implement the easier puzzles (rating 1-2)
- Build intuition for bit manipulation
Puzzles to implement:
bitAnd- Rating 1getByte- Rating 2isNegative- Rating 2isEqual- Rating 2negate- Rating 2
For each puzzle, follow this process:
1. UNDERSTAND the problem
- What are the inputs/outputs?
- What are the edge cases?
- What operators are allowed?
2. DERIVE the solution mathematically
- Don't guess! Use Boolean algebra.
- Write down the transformation you need.
- Find an equivalent using allowed ops.
3. IMPLEMENT the solution
- Write clean code.
- Add comments explaining the reasoning.
4. TEST the solution
- Run btest.
- Verify edge cases manually if needed.
5. OPTIMIZE if needed
- If over the operator limit, find simplifications.
- Use algebraic identities.
Example derivation for getByte:
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
// DERIVATION:
//
// Word x: [byte3][byte2][byte1][byte0]
// MSB LSB
//
// To extract byte n:
// 1. Shift right by (n * 8) bits to move target byte to position 0
// 2. Mask with 0xFF to keep only the lowest 8 bits
//
// x >> (n * 8) puts byte n at position 0
// But we can't use *, so: n * 8 = n << 3
//
// Final: (x >> (n << 3)) & 0xFF
int getByte(int x, int n) {
return (x >> (n << 3)) & 0xFF;
}
// Operator count: 3 (<<, >>, &)
Phase 3: Implement Advanced Puzzles (Days 8-11)
Goals:
- Tackle rating 3-4 puzzles
- Develop sophisticated techniques
Puzzles to implement:
absVal- Rating 4conditional- Rating 3isLessOrEqual- Rating 3logicalShift- Rating 3bitCount- Rating 4
Key technique for conditional operations:
/*
* Pattern: Branchless selection
*
* To compute: condition ? a : b
*
* 1. Convert condition to mask:
* - 0 becomes 0x00000000 (all zeros)
* - nonzero becomes 0xFFFFFFFF (all ones)
*
* 2. Use mask to select:
* result = (mask & a) | (~mask & b)
*
* Creating the mask:
* !!x gives 0 or 1
* -(!!x) = ~(!!x) + 1 gives 0 or -1 (all ones)
* Or: ((!x) << 31) >> 31 also works
*/
Key technique for comparisons:
/*
* Pattern: Comparing x and y
*
* For x < y:
* - Naive: x - y < 0, check sign bit of (x - y)
* - Problem: overflow when signs differ!
*
* Safe approach:
* 1. If signs differ: negative is always less
* 2. If signs same: check sign of (x - y), no overflow possible
*
* Implementation:
* int sign_x = x >> 31;
* int sign_y = y >> 31;
* int diff_sign = sign_x ^ sign_y;
* int same_sign_result = ((x + (~y + 1)) >> 31) & 1; // sign of x - y
* int diff_sign_result = sign_x & 1; // x is negative
* return (diff_sign & diff_sign_result) | (~diff_sign & same_sign_result);
*/
Phase 4: Property-Based Testing (Days 12-13)
Goals:
- Add sophisticated test generation
- Implement failure explanation
Implement property-based tests:
// test_properties.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// Test that absVal is non-negative (except for INT_MIN)
int test_absVal_nonnegative() {
for (int i = 0; i < 1000000; i++) {
int x = rand_int();
if (x == INT_MIN) continue; // Known exception
int result = absVal(x);
if (result < 0) {
printf("Property violation: absVal(%d) = %d, expected >= 0\n",
x, result);
return 0;
}
}
return 1;
}
// Test that absVal(x) == absVal(-x)
int test_absVal_symmetry() {
for (int i = 0; i < 1000000; i++) {
int x = rand_int();
if (x == INT_MIN) continue; // -INT_MIN overflows
int result1 = absVal(x);
int result2 = absVal(-x);
if (result1 != result2) {
printf("Property violation: absVal(%d) = %d, absVal(%d) = %d\n",
x, result1, -x, result2);
return 0;
}
}
return 1;
}
// Test that conditional(x, y, z) returns y when x != 0
int test_conditional_nonzero() {
for (int i = 0; i < 100000; i++) {
int x = rand_int();
if (x == 0) x = 1; // Ensure nonzero
int y = rand_int();
int z = rand_int();
int result = conditional(x, y, z);
if (result != y) {
printf("Property violation: conditional(%d, %d, %d) = %d, expected %d\n",
x, y, z, result, y);
return 0;
}
}
return 1;
}
// Generate adversarial test cases
int generate_adversarial(int puzzle_id) {
int adversarial[] = {
0,
1,
-1,
INT_MIN,
INT_MAX,
INT_MIN + 1,
INT_MAX - 1,
0x55555555,
0xAAAAAAAA,
0x12345678,
0x87654321,
// Powers of 2
2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
// Near zero
-2, -3, -4, -5, -10, -100, -1000,
2, 3, 4, 5, 10, 100, 1000,
};
// Test all adversarial cases
// ...
}
Phase 5: Failure Explanation Engine (Day 14)
Goals:
- Produce educational failure messages
- Explain WHY things fail, not just THAT they fail
// explain.c - Failure explanation engine
#include <stdio.h>
#include <limits.h>
void explain_overflow(int x, int y, const char *op) {
printf("\n");
printf("OVERFLOW EXPLANATION:\n");
printf("────────────────────\n");
printf("Operation: %d %s %d\n", x, op, y);
if (x > 0 && y > 0) {
printf("Both operands are positive.\n");
printf("Maximum representable: %d (INT_MAX)\n", INT_MAX);
printf("The sum would be: %lld\n", (long long)x + y);
printf("This exceeds INT_MAX, causing overflow.\n");
} else if (x < 0 && y < 0) {
printf("Both operands are negative.\n");
printf("Minimum representable: %d (INT_MIN)\n", INT_MIN);
printf("The sum would be: %lld\n", (long long)x + y);
printf("This is below INT_MIN, causing underflow.\n");
}
}
void explain_int_min(int x) {
printf("\n");
printf("INT_MIN SPECIAL CASE:\n");
printf("─────────────────────\n");
printf("You encountered x = %d (0x%08x)\n", x, x);
printf("\n");
printf("In two's complement:\n");
printf(" INT_MIN = -2147483648 = 0x80000000\n");
printf(" INT_MAX = 2147483647 = 0x7FFFFFFF\n");
printf("\n");
printf("Notice: |INT_MIN| > INT_MAX!\n");
printf("There is no positive representation for -INT_MIN.\n");
printf("\n");
printf("Arithmetic behavior:\n");
printf(" -INT_MIN = ~INT_MIN + 1\n");
printf(" = 0x7FFFFFFF + 1\n");
printf(" = 0x80000000\n");
printf(" = INT_MIN (wraps around!)\n");
printf("\n");
printf("This is why absVal(INT_MIN) returns INT_MIN.\n");
}
void explain_sign_comparison(int x, int y) {
printf("\n");
printf("SIGN COMPARISON ISSUE:\n");
printf("──────────────────────\n");
printf("Comparing x = %d and y = %d\n", x, y);
printf("\n");
int sign_x = (x >> 31) & 1;
int sign_y = (y >> 31) & 1;
printf("Sign of x: %s (bit 31 = %d)\n",
sign_x ? "negative" : "non-negative", sign_x);
printf("Sign of y: %s (bit 31 = %d)\n",
sign_y ? "negative" : "non-negative", sign_y);
if (sign_x != sign_y) {
printf("\n");
printf("WARNING: Signs differ!\n");
printf("Computing x - y could overflow.\n");
printf("x - y = %d - %d = %lld (as long long)\n",
x, y, (long long)x - y);
printf("But as int: %d (OVERFLOW!)\n", x - y);
}
}
6. Testing Strategy
6.1 Test Categories
| Category | Purpose | Implementation |
|---|---|---|
| Edge Cases | Catch boundary conditions | Hardcoded special values |
| Random | Find unexpected failures | Random 32-bit values |
| Exhaustive | Complete coverage for small domains | All values in range |
| Property | Verify invariants | Property assertions over random inputs |
| Adversarial | Stress-test tricky cases | Carefully crafted difficult inputs |
6.2 Critical Test Cases by Puzzle
isNegative
// Must handle:
{0, 0}, // Zero is not negative
{1, 0}, // Positive
{-1, 1}, // Negative
{INT_MIN, 1}, // Most negative
{INT_MAX, 0}, // Most positive
{INT_MIN + 1, 1}, // Second most negative
isEqual
// Must handle:
{0, 0, 1}, // Zero equality
{-1, -1, 1}, // Negative equality
{INT_MIN, INT_MIN, 1}, // Edge equality
{0, 1, 0}, // Differ by 1
{INT_MIN, INT_MAX, 0}, // Extreme difference
{-1, 0, 0}, // Sign boundary
absVal
// Must handle:
{0, 0}, // Zero
{1, 1}, // Positive unchanged
{-1, 1}, // Simple negative
{INT_MAX, INT_MAX}, // Max positive
{INT_MIN, INT_MIN}, // Special case! Cannot negate
{INT_MIN + 1, INT_MAX}, // Just above INT_MIN
conditional
// Must handle:
{0, 5, 10, 10}, // False condition
{1, 5, 10, 5}, // True condition (1)
{-1, 5, 10, 5}, // True condition (negative)
{INT_MIN, 5, 10, 5}, // True condition (INT_MIN is nonzero!)
{100, 0, 0, 0}, // Both branches same
{0, INT_MIN, INT_MAX, INT_MAX}, // Edge values in branches
6.3 Test Harness Implementation
// test_harness.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <time.h>
#define RAND_TESTS 100000
#define MAX_FAILURES 10
typedef struct {
const char *name;
int (*func)(int);
int (*ref)(int);
int rating;
int max_ops;
} Test1Arg;
typedef struct {
const char *name;
int (*func)(int, int);
int (*ref)(int, int);
int rating;
int max_ops;
} Test2Arg;
// Edge case arrays
int edge_values[] = {
0, 1, -1, 2, -2,
INT_MIN, INT_MAX,
INT_MIN + 1, INT_MAX - 1,
0x55555555, 0xAAAAAAAA,
0x00FF00FF, 0xFF00FF00,
0x0F0F0F0F, 0xF0F0F0F0,
16, 32, 64, 128, 256,
-16, -32, -64, -128, -256
};
int n_edge = sizeof(edge_values) / sizeof(edge_values[0]);
// Biased random generator
int biased_rand() {
int r = rand();
switch (r % 4) {
case 0: // Uniform random
return rand() ^ (rand() << 15);
case 1: // Near zero
return (rand() % 2001) - 1000;
case 2: // Near INT_MIN
return INT_MIN + (rand() % 1000);
case 3: // Near INT_MAX
return INT_MAX - (rand() % 1000);
}
return 0;
}
int run_test_1arg(Test1Arg *test) {
int failures = 0;
int passed = 0;
printf("Testing %s (rating %d, max %d ops)...\n",
test->name, test->rating, test->max_ops);
// Edge cases
for (int i = 0; i < n_edge && failures < MAX_FAILURES; i++) {
int x = edge_values[i];
int expected = test->ref(x);
int got = test->func(x);
if (got != expected) {
printf(" FAIL: %s(0x%08x) = 0x%08x, expected 0x%08x\n",
test->name, x, got, expected);
failures++;
} else {
passed++;
}
}
// Random tests
for (int i = 0; i < RAND_TESTS && failures < MAX_FAILURES; i++) {
int x = biased_rand();
int expected = test->ref(x);
int got = test->func(x);
if (got != expected) {
printf(" FAIL: %s(0x%08x) = 0x%08x, expected 0x%08x\n",
test->name, x, got, expected);
failures++;
} else {
passed++;
}
}
if (failures == 0) {
printf(" PASS (%d tests)\n", passed);
return test->rating;
} else {
printf(" FAIL (%d failures)\n", failures);
return 0;
}
}
// Similar for 2-arg tests...
7. Common Pitfalls and Debugging
7.1 Frequent Mistakes
| Pitfall | Symptom | Solution |
|---|---|---|
| Forgetting INT_MIN | Works for most values, fails at INT_MIN | Always test INT_MIN explicitly |
| Shift UB | Random behavior on some compilers | Never shift by >= 32 bits |
| Sign of right shift | Works on GCC, fails elsewhere | Cast to unsigned for logical shift |
| Operator counting | Solution correct but over limit | Use algebraic simplification |
| Using forbidden ops | dlc reports violation | Re-read the allowed operator list |
| Off-by-one in masks | Wrong bits selected | Trace through bit-by-bit |
7.2 Debugging Techniques
Binary Inspection
// Helper to print binary representation
void print_binary(int x) {
printf("0x%08x = ", x);
for (int i = 31; i >= 0; i--) {
printf("%d", (x >> i) & 1);
if (i % 8 == 0) printf(" ");
}
printf("\n");
}
// Use during debugging:
printf("x = "); print_binary(x);
printf("y = "); print_binary(y);
printf("x ^ y = "); print_binary(x ^ y);
Step-by-Step Tracing
// Trace each step of a complex operation
int absVal_debug(int x) {
printf("Input x = %d (0x%08x)\n", x, x);
int mask = x >> 31;
printf("mask = x >> 31 = 0x%08x\n", mask);
int xor_result = x ^ mask;
printf("x ^ mask = 0x%08x\n", xor_result);
int neg_mask = ~mask + 1;
printf("~mask + 1 = 0x%08x\n", neg_mask);
int result = xor_result + neg_mask;
printf("result = 0x%08x = %d\n", result, result);
return result;
}
Comparing with Reference
// Run your solution and reference in parallel
void compare(int x) {
int yours = yourFunction(x);
int ref = referenceFunction(x);
if (yours != ref) {
printf("MISMATCH at x = %d (0x%08x)\n", x, x);
printf(" Yours: %d (0x%08x)\n", yours, yours);
printf(" Ref: %d (0x%08x)\n", ref, ref);
}
}
7.3 Solving Strategy
When stuck on a puzzle:
1. SIMPLIFY the problem
- What's the simplest case? (e.g., single bit)
- Can you solve a restricted version?
2. VISUALIZE the bits
- Draw out the bit patterns
- Trace through example inputs
3. WORK BACKWARDS
- What's the final result you need?
- What operation would produce it?
4. USE IDENTITIES
- Review Boolean algebra laws
- Look for patterns that simplify
5. SEARCH for inspiration
- Bit twiddling hacks websites
- Chapter 2 of CS:APP
- But understand, don't copy!
6. STEP AWAY and return fresh
- Sometimes insight comes after a break
8. Extensions and Challenges
8.1 Beginner Extensions
- Add more puzzles at rating 1-2
- Implement a web-based interface for testing
- Create a tutorial mode with hints
- Add timing information (how fast is your solution?)
8.2 Intermediate Extensions
- Implement floating-point puzzles (floatScale2, floatInt2Float)
- Add multi-word operations (64-bit on 32-bit machine)
- Create an automatic puzzle generator
- Implement solution optimization suggestions
8.3 Advanced Extensions
- Write a compiler that automatically finds minimal solutions
- Implement in hardware description language (Verilog/VHDL)
- Add superoptimizer that finds optimal solutions by exhaustive search
- Create adversarial puzzle generation (find puzzles humans fail at)
8.4 Additional Puzzles to Implement
// Advanced puzzles for extra challenge
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
/*
* bitParity - Returns 1 if x has an odd number of 1s
* Examples: bitParity(5) = 0 (two 1s), bitParity(7) = 1 (three 1s)
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
/*
* isPower2 - Returns 1 if x is a power of 2
* Examples: isPower2(4) = 1, isPower2(6) = 0
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
*/
/*
* howManyBits - Return minimum bits to represent x in two's complement
* Examples: howManyBits(12) = 5, howManyBits(-1) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
9. Real-World Connections
9.1 Hardware Design
The restrictions in Data Lab mirror real hardware constraints:
┌────────────────────────────────────────────────────────────────┐
│ DATA LAB ↔ HARDWARE │
├────────────────────────────────────────────────────────────────┤
│ │
│ Data Lab Restriction: Hardware Reality: │
│ ───────────────────── ────────────────── │
│ Only bitwise ops Combinational logic uses gates │
│ No conditionals No branches in pure logic │
│ Operator count limit Fewer gates = less power/area │
│ No loops Fixed latency requirement │
│ │
│ Your branchless absVal is how ALUs actually compute |x|! │
│ Your conditional is a 2-to-1 multiplexer │
│ Your bitCount is a population count unit │
│ │
└────────────────────────────────────────────────────────────────┘
9.2 Compiler Optimizations
Compilers use these exact techniques:
// What you write:
if (x < 0) return -x;
else return x;
// What the compiler might generate (branchless):
int mask = x >> 31;
return (x ^ mask) - mask;
// Why branchless?
// - Avoids branch misprediction penalty (10-20 cycles)
// - Enables pipelining and vectorization
// - Deterministic timing (security benefit)
9.3 Cryptography
Constant-time programming requires branchless operations:
// INSECURE: Timing attack possible
int compare_secrets(char *a, char *b, int len) {
for (int i = 0; i < len; i++) {
if (a[i] != b[i]) return 0; // Early exit leaks timing
}
return 1;
}
// SECURE: Constant-time comparison
int compare_secrets_safe(char *a, char *b, int len) {
int result = 0;
for (int i = 0; i < len; i++) {
result |= a[i] ^ b[i]; // No early exit
}
return !result;
}
9.4 Interview Questions
Bit manipulation is a common interview topic:
- “Swap two integers without a temporary variable”
- “Check if a number is a power of 2”
- “Count the number of set bits”
- “Find the only non-repeating element in an array”
- “Reverse bits of an integer”
Data Lab prepares you for all of these!
10. Resources
10.1 Essential Reading
- CS:APP Chapter 2: “Representing and Manipulating Information” - The definitive reference
- Hacker’s Delight by Henry Warren: The bible of bit manipulation tricks
- Effective C, 2nd Edition by Robert Seacord: Undefined behavior coverage
10.2 Online References
- Bit Twiddling Hacks (Stanford Graphics): http://graphics.stanford.edu/~seander/bithacks.html
- Chess Programming Wiki - Bit Manipulation: Extensive techniques
- Sean Eron Anderson’s Bit Manipulation: Collection of optimized algorithms
10.3 Tools
- objdump -d: See what assembly the compiler generates
- GDB: Step through and examine bits
- Python REPL: Quick experiments with arbitrary precision
>>> bin(0x80000000) '0b10000000000000000000000000000000' >>> hex(-1 & 0xFFFFFFFF) '0xffffffff'
10.4 Related Projects
- Previous: P2 (Bitwise Data Inspector) - See how data is represented
- Next: P4 (Calling Convention Crash Cart) - Apply bit understanding to debugging
- Related: P5 (Bomb Lab) - Reverse engineer binary puzzles
11. Self-Assessment Checklist
Understanding
- I can explain what each bitwise operator does at the bit level
- I can apply De Morgan’s laws to transform expressions
- I understand why INT_MIN is special in two’s complement
- I know what undefined behavior exists for shifts and signed overflow
- I can explain why operator restrictions force deeper understanding
- I understand property-based testing and why it catches more bugs
Implementation
- I solved all rating 1-2 puzzles correctly
- I solved at least 3 rating 3-4 puzzles correctly
- All my solutions pass the operator restriction check
- My solutions work for edge cases (0, -1, INT_MIN, INT_MAX)
- I can explain my solution for each puzzle (not just “it works”)
Testing
- I wrote property-based tests for my puzzles
- I understand how the test harness works
- I can add new test cases when I discover edge cases
- My failure messages explain WHY something failed
Growth
- I can solve new bit puzzles without looking up solutions
- I think in bits naturally when appropriate
- I recognize bit manipulation patterns in real code
- I can explain bit tricks to others
12. Completion Criteria
Minimum Viable Completion
- Implement at least 5 puzzles correctly
- All implemented puzzles pass basic tests
- Understand the derivation for each puzzle
- Build compiles and test harness runs
Full Completion
- Implement all 9+ puzzles correctly
- All puzzles pass property-based tests
- Operator checker verifies compliance
- Clear comments explain each solution
- Failure messages are educational
Excellence (Going Above and Beyond)
- Implement floating-point puzzles
- Add automated puzzle generation
- Find solutions with fewer operators than required
- Contribute new puzzles with appropriate difficulty ratings
- Implement in hardware (Verilog/VHDL)
13. Real World Outcome
When you complete this project, here’s exactly what you’ll see when running your test harness:
$ ./btest
================================================================================
DATA LAB TEST HARNESS v1.0
================================================================================
Running tests...
Testing bitAnd:
bitAnd(0, 0) = 0 ... PASS
bitAnd(-1, -1) = -1 ... PASS
bitAnd(0x12345678, 0xFF) = 0x78 ... PASS
Random tests (100000 iterations) ... PASS
Score: 1/1 | Operators: 4/8
Testing getByte:
getByte(0x12345678, 0) = 0x78 ... PASS
getByte(0x12345678, 1) = 0x56 ... PASS
getByte(0x12345678, 3) = 0x12 ... PASS
Random tests (100000 iterations) ... PASS
Score: 2/2 | Operators: 3/6
Testing isNegative:
isNegative(0) = 0 ... PASS
isNegative(1) = 0 ... PASS
isNegative(-1) = 1 ... PASS
isNegative(INT_MIN) = 1 ... PASS
isNegative(INT_MAX) = 0 ... PASS
Random tests (100000 iterations) ... PASS
Score: 2/2 | Operators: 2/6
Testing absVal:
absVal(0) = 0 ... PASS
absVal(1) = 1 ... PASS
absVal(-1) = 1 ... PASS
absVal(INT_MAX) = 2147483647 ... PASS
absVal(INT_MIN) = -2147483648 ... PASS (expected: INT_MIN has no positive!)
Random tests (100000 iterations) ... PASS
Score: 4/4 | Operators: 6/10
Testing conditional:
conditional(0, 1, 2) = 2 ... PASS
conditional(1, 1, 2) = 1 ... PASS
conditional(-1, 5, 10) = 5 ... PASS
conditional(INT_MIN, 100, 200) = 100 ... PASS (INT_MIN is truthy!)
Random tests (100000 iterations) ... PASS
Score: 3/3 | Operators: 8/16
Testing isLessOrEqual:
isLessOrEqual(0, 0) = 1 ... PASS
isLessOrEqual(-1, 0) = 1 ... PASS
isLessOrEqual(0, -1) = 0 ... PASS
isLessOrEqual(INT_MIN, INT_MAX) = 1 ... PASS
isLessOrEqual(INT_MAX, INT_MIN) = 0 ... PASS
Random tests (100000 iterations) ... PASS
Score: 3/3 | Operators: 14/24
Testing bitCount:
bitCount(0) = 0 ... PASS
bitCount(-1) = 32 ... PASS
bitCount(0x55555555) = 16 ... PASS
bitCount(0x12345678) = 13 ... PASS
Random tests (100000 iterations) ... PASS
Score: 4/4 | Operators: 36/40
================================================================================
FINAL RESULTS
================================================================================
Puzzle Rating Score Operators Status
----------------------------------------------------------------
bitAnd 1 1/1 4/8 PASS
getByte 2 2/2 3/6 PASS
isNegative 2 2/2 2/6 PASS
isEqual 2 2/2 2/5 PASS
negate 2 2/2 2/3 PASS
absVal 4 4/4 6/10 PASS
conditional 3 3/3 8/16 PASS
isLessOrEqual 3 3/3 14/24 PASS
bitCount 4 4/4 36/40 PASS
----------------------------------------------------------------
TOTAL SCORE: 23/23 All puzzles solved!
================================================================================
$ ./dlc bits.c
Checking operator restrictions...
bitAnd:
Allowed ops: | ~
Used ops: ~ | ~ (count: 4)
Max allowed: 8
Status: COMPLIANT
isNegative:
Allowed ops: ! ~ & ^ | + << >>
Used ops: >> & (count: 2)
Max allowed: 6
Status: COMPLIANT
absVal:
Allowed ops: ! ~ & ^ | + << >>
Used ops: >> ^ ~ + (count: 6)
Max allowed: 10
Status: COMPLIANT
All 9 puzzles are compliant with operator restrictions.
14. The Core Question You’re Answering
“How can I implement high-level operations like absolute value, comparison, and conditional selection using ONLY the primitive bit operations that hardware actually provides?”
This project forces you to think like the silicon: CPUs don’t have “if statements” at the gate level—they have AND, OR, NOT, and XOR gates. Every high-level construct you take for granted ultimately compiles down to these primitives, and Data Lab makes you discover exactly how.
15. Concepts You Must Understand First
Before starting this project, ensure you understand these concepts:
| Concept | Why It Matters | Where to Learn | |
|---|---|---|---|
| Bitwise operators (&, | , ^, ~, «, ») | These are your ONLY tools | CS:APP 2.1.7, P02 project |
| Two’s complement representation | You’ll exploit its properties | CS:APP 2.2, P02 project | |
| Boolean algebra laws (De Morgan, etc.) | Essential for transforming expressions | CS:APP 2.1.8, discrete math | |
| What INT_MIN and INT_MAX are | Critical edge cases | CS:APP 2.2.3, limits.h | |
| Sign extension | How smaller types become larger | CS:APP 2.2.6 | |
| Undefined behavior in C | Know what to avoid | Effective C Ch. 4 |
16. Questions to Guide Your Design
Work through these questions BEFORE writing code:
-
Framework Design: How will your test harness discover and run tests for each puzzle? How will you count operators?
-
Reference Solutions: Should reference solutions be hidden in a separate file? How do you prevent students from seeing them?
-
Edge Case Generation: What edge cases must every puzzle be tested against? (0, 1, -1, INT_MIN, INT_MAX, powers of 2…)
-
Operator Counting: How do you parse C code to count operators? Do you need a real parser or is regex sufficient?
-
Error Messages: When a puzzle fails, what information helps debugging? (Input, expected, got, binary representation?)
-
Puzzle Difficulty: How do you balance puzzles so some are achievable on day 1, others take days to solve?
-
Forbidden Constructs: How do you detect if someone used a forbidden operator, loop, or conditional?
17. Thinking Exercise
Before writing any code, work through these derivations by hand:
Exercise 1: Derive bitAnd using only | and ~
Goal: Implement x & y without using &.
Think: What does De Morgan’s Law say about ~(a & b)?
~(a & b) = ~a | ~b
So if I want a & b, I can negate both sides:
a & b = ~(~a | ~b)
Write out the truth table to verify this works for all 4 combinations of single bits.
Exercise 2: Derive isNegative
Goal: Return 1 if x < 0, else 0.
Think: Where is the sign information in a two’s complement number?
- The most significant bit (bit 31 for 32-bit int)
How do I get bit 31 into bit position 0?
- Right shift by 31:
x >> 31
But wait, what does arithmetic shift give me for negative numbers?
- All 1s (-1), not just 1
How do I turn -1 into 1?
- AND with 1:
(x >> 31) & 1
Exercise 3: Derive branchless conditional selection
Goal: Implement x ? y : z without using ?: or if.
Think step by step:
- Convert x to a “mask”: 0 if x==0, all 1s if x!=0
!!xgives 0 or 1-!!x(or~(!!x) + 1) gives 0 or -1 (all 1s)- Let’s call this
mask
- Use mask to select: when mask is all 1s, pick y. When mask is 0, pick z.
(mask & y)gives y when mask is -1, 0 when mask is 0(~mask & z)gives 0 when mask is -1, z when mask is 0- Combine:
(mask & y) | (~mask & z)
Verify this works for x=0 and x=nonzero.
18. The Interview Questions They’ll Ask
After completing this project, you’ll be ready for these common interview questions:
- “Swap two integers without using a temporary variable.”
// Using XOR: a ^= b; // a = a ^ b b ^= a; // b = b ^ (a ^ b) = a a ^= b; // a = (a ^ b) ^ a = b- Expected: Know the XOR swap trick and explain why it works
- Bonus: Mention it fails if a and b are the same memory location
- “Check if a number is a power of 2.”
return x > 0 && (x & (x - 1)) == 0;- Expected: The
x & (x-1)trick clears the lowest set bit - Bonus: Explain why x must be positive (0 and negative numbers aren’t powers of 2)
- Expected: The
- “Count the number of 1 bits in an integer.”
- Expected: Know at least the naive loop approach
- Bonus: Know divide-and-conquer approach, or the lookup table approach
- “Find the only non-repeating element in an array where every other element appears twice.”
int result = 0; for (int i = 0; i < n; i++) result ^= arr[i]; return result;- Expected: XOR of same elements cancels out
- Bonus: Extend to finding two unique elements
- “Compute the absolute value without branching.”
int mask = x >> 31; return (x ^ mask) - mask;- Expected: Know the mask-and-flip technique
- Bonus: Explain why INT_MIN is problematic
- “Why is x & (x-1) always equal to x with the lowest set bit cleared?”
- Expected: When you subtract 1, it borrows from the lowest 1 bit, flipping it and all bits below
- Bonus: Use this to explain fast popcount algorithms
19. Hints in Layers
If you’re stuck, reveal hints one at a time:
Hint 1: The Mask Pattern
Many puzzles require creating a “mask” that is all 1s or all 0s based on some condition.
Key insight: In two’s complement, -1 is all 1s (0xFFFFFFFF).
To create a mask:
!!xconverts any nonzero value to 1~(!!x) + 1converts 0 to 0, nonzero to -1 (all 1s)
This mask can then select between two values:
(mask & value_if_true) | (~mask & value_if_false)
Hint 2: Subtraction Without Minus
If - is not allowed, use two’s complement negation:
-x = ~x + 1
So a - b becomes:
a + (~b + 1)
This is fundamental for many puzzles.
Hint 3: Handling Sign Differences in Comparisons
When comparing x and y (like for isLessOrEqual), computing x - y can overflow if they have different signs!
Safe approach:
- If signs are different: negative number is always less
- If signs are same: compute
x - y(no overflow possible) and check sign
int sign_x = (x >> 31) & 1;
int sign_y = (y >> 31) & 1;
int diff_sign = sign_x ^ sign_y;
// When signs differ, x < y iff x is negative
// When signs same, x < y iff (x - y) is negative
Hint 4: The INT_MIN Special Case
INT_MIN breaks many “obvious” solutions:
-INT_MINoverflows (undefined in C, wraps to INT_MIN in two’s complement)abs(INT_MIN)cannot be represented as positiveINT_MIN - 1overflows
Always test your solutions with:
INT_MIN(0x80000000)INT_MAX(0x7FFFFFFF)-1(0xFFFFFFFF)01
20. Books That Will Help
| Topic | Book | Chapter/Section |
|---|---|---|
| Bitwise operators | CS:APP 3rd Ed | Section 2.1.7 “Bit-Level Operations in C” |
| Boolean algebra | CS:APP 3rd Ed | Section 2.1.8 “Logical Operations in C” |
| Two’s complement | CS:APP 3rd Ed | Section 2.2 “Integer Representations” |
| Integer overflow | CS:APP 3rd Ed | Section 2.3 “Integer Arithmetic” |
| Shift operations | CS:APP 3rd Ed | Section 2.1.9 “Shift Operations in C” |
| Bit manipulation tricks | Hacker’s Delight, 2nd Ed | Entire book (especially Ch. 2, 5) |
| More bit tricks | Hacker’s Delight, 2nd Ed | Chapter 2 “Basics” |
| Population count | Hacker’s Delight, 2nd Ed | Chapter 5 “Counting Bits” |
| Bit Twiddling Hacks | Stanford Graphics Group | Online resource (free) |
| Undefined behavior | Effective C, 2nd Edition | Chapter 4 “Expressions and Operators” |
| The original Data Lab | CMU CS:APP Course | Lab handout (available online) |
This guide was expanded from CSAPP_3E_DEEP_LEARNING_PROJECTS.md. For the complete learning path, see the project index.
When you complete this project, you’ll think about integers differently. You’ll see that every high-level operation ultimately reduces to AND, OR, NOT, and shift—and you’ll know exactly how.