Project 3: Bitwise Logic Calculator

The Core Question: “How do computers perform logic and make decisions at the most fundamental level, below even arithmetic?”

Project Overview

Attribute	Value
Difficulty	Intermediate
Time Estimate	Weekend (10-16 hours)
Main Language	Python
Alternative Languages	C, C++, Java, Rust
Prerequisites	Project 1 completed, comfort with programming logic, basic binary understanding
Key Topics	Bitwise AND, OR, XOR, NOT, shifts, bit masking, flags

Learning Objectives
Deep Theoretical Foundation
Project Specification
Real World Outcome
The Core Question You’re Answering
Concepts You Must Understand First
Questions to Guide Your Design
Thinking Exercise
The Interview Questions They’ll Ask
Hints in Layers
Books That Will Help
Self-Assessment Checklist

1. Learning Objectives

By completing this project, you will:

Master all bitwise operators: Instantly recognize when to use AND, OR, XOR, NOT, and shifts
Visualize operations at the bit level: See operations not as magic but as parallel boolean logic
Understand practical bit manipulation: Know why x & 1 checks odd/even and how to set/clear specific bits
Implement flag systems: Store multiple boolean values efficiently in a single integer
Decode real-world applications: Understand permission flags, subnet masks, and feature toggles
Reason about two’s complement: Explain why ~5 is not -5 in signed arithmetic
Build intuition for bit tricks: Recognize common patterns like x & (x-1) and their purposes

2. Deep Theoretical Foundation

2.1 What Bitwise Operations Actually Are

At the hardware level, bitwise operations are performed in parallel on every bit. When you write a & b, the CPU computes the AND of each bit position simultaneously:

          PARALLEL BIT-LEVEL OPERATION
          ============================

          a = 1010 1100  (0xAC = 172)
          b = 1111 0000  (0xF0 = 240)

          Each column is computed independently:

          Bit 7:  1 AND 1 = 1
          Bit 6:  0 AND 1 = 0
          Bit 5:  1 AND 1 = 1
          Bit 4:  0 AND 1 = 0
          Bit 3:  1 AND 0 = 0
          Bit 2:  1 AND 0 = 0
          Bit 1:  0 AND 0 = 0
          Bit 0:  0 AND 0 = 0

          Result: 1010 0000  (0xA0 = 160)

This is fundamentally different from arithmetic operations which must carry values between bit positions.

2.2 The Boolean Logic Foundation

Every bitwise operation corresponds to a boolean function. Understanding these truth tables is essential:

          BOOLEAN TRUTH TABLES
          ====================

          AND (&)         OR (|)          XOR (^)         NOT (~)
          -------         ------          -------         -------
          A B | A&B       A B | A|B       A B | A^B       A | ~A
          ----+----       ----+----       ----+----       --+---
          0 0 | 0         0 0 | 0         0 0 | 0         0 | 1
          0 1 | 0         0 1 | 1         0 1 | 1         1 | 0
          1 0 | 0         1 0 | 1         1 0 | 1
          1 1 | 1         1 1 | 1         1 1 | 0

          KEY INSIGHTS:
          - AND: Output is 1 ONLY if BOTH inputs are 1 (like multiplication)
          - OR:  Output is 0 ONLY if BOTH inputs are 0 (like capped addition)
          - XOR: Output is 1 if inputs DIFFER (difference detector)
          - NOT: Simply flips the bit

2.3 The Bitwise Operators in Detail

AND (&) - The Bit Selector

AND is used to mask or select specific bits:

          USING AND AS A MASK
          ===================

          Goal: Extract the lower 4 bits (nibble) of a byte

          Value:    0110 1101  (0x6D = 109)
          Mask:     0000 1111  (0x0F = 15)
                    ---------
          Result:   0000 1101  (0x0D = 13)

          The mask "allows" bits where it has 1s,
          and "blocks" bits where it has 0s.

          Common uses:
          - x & 1           Check if x is odd (tests bit 0)
          - x & 0xFF        Extract lowest byte
          - x & ~(1 << n)   Clear bit n

OR (|) - The Bit Setter

OR is used to set specific bits without affecting others:

          USING OR TO SET BITS
          ====================

          Goal: Set bit 4 (turn it to 1)

          Value:    0110 0001  (0x61 = 97)
          Mask:     0001 0000  (0x10 = 16)
                    ---------
          Result:   0111 0001  (0x71 = 113)

          OR with 1 forces a bit to 1.
          OR with 0 leaves a bit unchanged.

          Common uses:
          - x | (1 << n)    Set bit n
          - flags | FLAG    Add a flag to a set

XOR (^) - The Bit Flipper

XOR is used to toggle bits and has remarkable mathematical properties:

          XOR PROPERTIES
          ==============

          Self-inverse:       A ^ A = 0
          Identity:           A ^ 0 = A
          Commutativity:      A ^ B = B ^ A
          Associativity:      (A ^ B) ^ C = A ^ (B ^ C)

          Toggle bits:
          Value:    0110 1101  (0x6D)
          Mask:     0000 1111  (0x0F)
                    ---------
          Result:   0110 0010  (0x62)  <- Lower 4 bits flipped!

          The XOR Swap Trick:
          a = a ^ b
          b = a ^ b    // b now has original a
          a = a ^ b    // a now has original b

          How it works:
          Step 1: a' = a ^ b
          Step 2: b' = a' ^ b = (a ^ b) ^ b = a
          Step 3: a'' = a' ^ b' = (a ^ b) ^ a = b

NOT (~) - The Bit Inverter

NOT flips every bit, but beware of two’s complement:

          NOT AND TWO'S COMPLEMENT
          ========================

          For 8-bit unsigned:
          ~0    = 1111 1111 = 255
          ~255  = 0000 0000 = 0

          For 8-bit signed (two's complement):
          ~0    = 1111 1111 = -1
          ~5    = 1111 1010 = -6   (NOT ~5 is not -5!)

          Why ~5 = -6:
          In two's complement: -x = ~x + 1
          Therefore: ~x = -x - 1 = -(x + 1)
          So: ~5 = -(5 + 1) = -6

          Useful identity: -x = ~x + 1 (two's complement negation)

2.4 Shift Operations

Shifts move bits left or right, with different behaviors:

          LEFT SHIFT (<<)
          ===============

          Value:    0001 0110  (0x16 = 22)
          << 2:     0101 1000  (0x58 = 88)

          Bits shift left, zeros fill from right.
          Each left shift MULTIPLIES by 2.

          22 << 1 = 44   (22 * 2)
          22 << 2 = 88   (22 * 4)
          22 << 3 = 176  (22 * 8)

          CAUTION: Bits shifted off the left are LOST!
          0x80 << 1 = 0x00 (for 8-bit)


          RIGHT SHIFT (>>)
          ================

          Two types:
          1. Logical shift (unsigned): Fill with zeros
          2. Arithmetic shift (signed): Fill with sign bit

          Unsigned:
          Value:    1000 0100  (0x84 = 132)
          >> 2:     0010 0001  (0x21 = 33)

          Signed (negative number):
          Value:    1000 0100  (-124 in signed 8-bit)
          >> 2:     1110 0001  (-31, sign extended)

          In Python: >> always does arithmetic shift for negative numbers
          In C: >> behavior for signed values is implementation-defined!

2.5 Common Bit Manipulation Patterns

          ESSENTIAL BIT MANIPULATION PATTERNS
          ===================================

          Set bit n:        x | (1 << n)
          Clear bit n:      x & ~(1 << n)
          Toggle bit n:     x ^ (1 << n)
          Check bit n:      (x >> n) & 1  or  x & (1 << n)

          Clear lowest set bit:     x & (x - 1)
            0110 & 0101 = 0100

          Isolate lowest set bit:   x & (-x)
            0110 & 1010 = 0010

          Check if power of 2:      x && !(x & (x - 1))
            Powers of 2 have exactly one bit set

          Count set bits (popcount): Many algorithms exist

          Create mask of n bits:    (1 << n) - 1
            (1 << 4) - 1 = 0b1111 = 15

2.6 Why `x & 1` Checks for Odd/Even

          ODD/EVEN CHECK EXPLAINED
          ========================

          In binary, the ONLY difference between even and odd
          is the least significant bit (bit 0):

          0 = 0000    (even)  bit 0 = 0
          1 = 0001    (odd)   bit 0 = 1
          2 = 0010    (even)  bit 0 = 0
          3 = 0011    (odd)   bit 0 = 1
          4 = 0100    (even)  bit 0 = 0
          5 = 0101    (odd)   bit 0 = 1
          6 = 0110    (even)  bit 0 = 0
          7 = 0111    (odd)   bit 0 = 1

          x & 1 extracts bit 0:
          - If bit 0 is 0 -> x & 1 = 0 -> even
          - If bit 0 is 1 -> x & 1 = 1 -> odd

          This is FASTER than x % 2 because:
          - AND is a single CPU instruction
          - Division/modulo requires many cycles

2.7 Storing Multiple Flags in One Byte

          FLAG STORAGE - 8 FLAGS IN 1 BYTE
          =================================

          Define flag positions:
          FLAG_READ    = 0b00000001  (bit 0, value 1)
          FLAG_WRITE   = 0b00000010  (bit 1, value 2)
          FLAG_EXECUTE = 0b00000100  (bit 2, value 4)
          FLAG_HIDDEN  = 0b00001000  (bit 3, value 8)
          FLAG_SYSTEM  = 0b00010000  (bit 4, value 16)
          FLAG_ARCHIVE = 0b00100000  (bit 5, value 32)

          Operations:
          permissions = 0

          # Grant read + write
          permissions = permissions | FLAG_READ | FLAG_WRITE
          permissions = 0b00000011

          # Check if readable
          if (permissions & FLAG_READ):
              print("Can read!")

          # Revoke write
          permissions = permissions & ~FLAG_WRITE
          permissions = 0b00000001

          # Toggle hidden
          permissions = permissions ^ FLAG_HIDDEN
          permissions = 0b00001001

3. Project Specification

3.1 What You Will Build

A command-line bitwise calculator that:

Accepts two operands in decimal, hex, or binary
Performs bitwise operations (AND, OR, XOR, NOT, shifts)
Displays results with visual binary alignment
Shows step-by-step bit-level explanation

3.2 Example Usage

$ bitwise_calc 0xAC AND 0xF0
$ bitwise_calc 42 OR 15
$ bitwise_calc 0b11001010 XOR 0b10101010
$ bitwise_calc NOT 0xFF
$ bitwise_calc 1 LSHIFT 4
$ bitwise_calc 128 RSHIFT 3

3.3 Output Format

Every operation should produce aligned binary visualization:

$ bitwise_calc 0xAC AND 0xF0

================================================================================
                         BITWISE LOGIC CALCULATOR
                         Operation: AND (&)
================================================================================

INPUT VALUES
--------------------------------------------------------------------------------
  Operand A:  0xAC (172 decimal)
  Operand B:  0xF0 (240 decimal)

BINARY VISUALIZATION
--------------------------------------------------------------------------------

      Bit Position: 7 6 5 4 3 2 1 0
                    ─────────────────
  A = 0xAC (172):   1 0 1 0 1 1 0 0
                    & & & & & & & &     (AND each column)
  B = 0xF0 (240):   1 1 1 1 0 0 0 0
                    ─────────────────
  Result:           1 0 1 0 0 0 0 0

RESULT
--------------------------------------------------------------------------------
  Binary:   0b10100000
  Hex:      0xA0
  Decimal:  160

OPERATION EXPLANATION
--------------------------------------------------------------------------------
  AND (&) outputs 1 only when BOTH bits are 1.

  Bit 7: 1 AND 1 = 1
  Bit 6: 0 AND 1 = 0
  Bit 5: 1 AND 1 = 1
  Bit 4: 0 AND 1 = 0
  Bit 3: 1 AND 0 = 0
  Bit 2: 1 AND 0 = 0
  Bit 1: 0 AND 0 = 0
  Bit 0: 0 AND 0 = 0

================================================================================

3.4 Functional Requirements

Requirement	Description
Input Formats	Accept decimal (42), hex (0xAC), binary (0b1010)
Operations	AND, OR, XOR, NOT, LSHIFT, RSHIFT
Output Formats	Show binary, hex, and decimal results
Visualization	Aligned binary with operation symbols
Bit Width	Handle 8, 16, 32, or 64-bit values (auto-detect or specify)
Explanation	Show per-bit breakdown of operation

4. Real World Outcome

When you complete this project, here is exactly what your tool will produce:

Example 1: Understanding Permission Flags

$ bitwise_calc 0x755 AND 0x007

================================================================================
                         BITWISE LOGIC CALCULATOR
                         Operation: AND (&)
                         Context: Unix Permission Extraction
================================================================================

INPUT VALUES
--------------------------------------------------------------------------------
  File Permissions:  0x755 (1877 decimal)
                     rwxr-xr-x in Unix notation

  Mask (Others):     0x007 (7 decimal)
                     Isolates "others" permission bits

BINARY VISUALIZATION (12-bit)
--------------------------------------------------------------------------------

      Bit Position: 11 10  9  8  7  6  5  4  3  2  1  0
                    ─────────────────────────────────────
      Owner         User         Group        Others
      ──────        ─────        ─────        ──────
  A = 0x755:         0  1  1  1  0  1  0  1  0  1  0  1
                     &  &  &  &  &  &  &  &  &  &  &  &
  B = 0x007:         0  0  0  0  0  0  0  0  0  1  1  1
                    ─────────────────────────────────────
  Result:            0  0  0  0  0  0  0  0  0  1  0  1

RESULT
--------------------------------------------------------------------------------
  Binary:   0b000000000101
  Hex:      0x005
  Decimal:  5
  Meaning:  Others have read (r) + execute (x) permissions

HOW MASKING WORKS
--------------------------------------------------------------------------------
  The mask 0x007 has 1s only in the "others" position.
  AND with 1 preserves the bit; AND with 0 clears it.

  Result: The "others" permissions = r-x (read, no write, execute)

================================================================================

Example 2: Setting Feature Flags

$ bitwise_calc 0x01 OR 0x04

================================================================================
                         BITWISE LOGIC CALCULATOR
                         Operation: OR (|)
                         Context: Adding Feature Flags
================================================================================

INPUT VALUES
--------------------------------------------------------------------------------
  Current Flags:   0x01 (1 decimal)
                   Only FLAG_ENABLE is set

  New Flag:        0x04 (4 decimal)
                   FLAG_VERBOSE

BINARY VISUALIZATION (8-bit)
--------------------------------------------------------------------------------

  Flag Meanings:    7   6   5   4   3   2   1   0
                   DBG AUD LOG NET VRB SIL WRN ENB
                   ─────────────────────────────────
  Current (0x01):   0   0   0   0   0   0   0   1
                    |   |   |   |   |   |   |   |   (OR each column)
  Add (0x04):       0   0   0   0   0   1   0   0
                   ─────────────────────────────────
  Result:           0   0   0   0   0   1   0   1

RESULT
--------------------------------------------------------------------------------
  Binary:   0b00000101
  Hex:      0x05
  Decimal:  5

  Active flags: FLAG_ENABLE + FLAG_VERBOSE

OPERATION EXPLANATION
--------------------------------------------------------------------------------
  OR (|) outputs 1 if EITHER bit is 1.

  - Existing flags (1s) are preserved
  - New flag (bit 2) is added
  - No flags are removed

  This is why OR is used to "add" or "enable" flags.

================================================================================

Example 3: Network Subnet Masking

$ bitwise_calc 192.168.1.105 AND 255.255.255.0

================================================================================
                         BITWISE LOGIC CALCULATOR
                         Operation: AND (&)
                         Context: Network Address Calculation
================================================================================

INPUT VALUES
--------------------------------------------------------------------------------
  IP Address:     192.168.1.105
  Subnet Mask:    255.255.255.0 (/24 CIDR)

BINARY VISUALIZATION (32-bit, shown as 4 octets)
--------------------------------------------------------------------------------

  Octet 1 (192):  1 1 0 0 0 0 0 0
              &   1 1 1 1 1 1 1 1   (255)
              =   1 1 0 0 0 0 0 0   (192)

  Octet 2 (168):  1 0 1 0 1 0 0 0
              &   1 1 1 1 1 1 1 1   (255)
              =   1 0 1 0 1 0 0 0   (168)

  Octet 3 (1):    0 0 0 0 0 0 0 1
              &   1 1 1 1 1 1 1 1   (255)
              =   0 0 0 0 0 0 0 1   (1)

  Octet 4 (105):  0 1 1 0 1 0 0 1
              &   0 0 0 0 0 0 0 0   (0)
              =   0 0 0 0 0 0 0 0   (0)

RESULT
--------------------------------------------------------------------------------
  Network Address:  192.168.1.0
  Host Part Masked: The .105 is zeroed out

EXPLANATION
--------------------------------------------------------------------------------
  Subnet mask 255.255.255.0 means:
  - First 24 bits identify the NETWORK (192.168.1)
  - Last 8 bits identify the HOST (.105)

  ANDing with the mask extracts just the network portion.
  This is how routers determine if two IPs are on the same network!

================================================================================

Example 4: Shift Operations

$ bitwise_calc 0x05 LSHIFT 2

================================================================================
                         BITWISE LOGIC CALCULATOR
                         Operation: LEFT SHIFT (<<)
================================================================================

INPUT VALUES
--------------------------------------------------------------------------------
  Value:    0x05 (5 decimal)
  Shift:    2 positions left

BINARY VISUALIZATION (8-bit)
--------------------------------------------------------------------------------

  Original:        0 0 0 0 0 1 0 1   (5)
                     \   \   \   \
                      \   \   \   \    Shift left by 2
                       \   \   \   \
  After shift:     0 0 0 1 0 1 0 0   (20)
                               ^ ^
                               | |
                               Zeros fill from right

RESULT
--------------------------------------------------------------------------------
  Binary:   0b00010100
  Hex:      0x14
  Decimal:  20

MATHEMATICAL MEANING
--------------------------------------------------------------------------------
  Left shift by n = Multiply by 2^n

  5 << 2 = 5 * 2^2 = 5 * 4 = 20

  This is MUCH faster than actual multiplication!
  CPUs can shift in a single cycle.

WHY LEFT SHIFT MULTIPLIES
--------------------------------------------------------------------------------
  In decimal, adding a zero multiplies by 10:
    5 -> 50 -> 500

  In binary, adding a zero (shifting left) multiplies by 2:
    101 -> 1010 -> 10100
     5  ->  10  ->  20

================================================================================

5. The Core Question You’re Answering

“How do computers perform logic and make decisions at the most fundamental level, below even arithmetic?”

Before there was addition, there was AND. Before subtraction, there was XOR. At the very base of all computation are these four simple operations that work on individual bits:

AND: “Both must be true”
OR: “At least one must be true”
XOR: “Exactly one must be true”
NOT: “The opposite”

Every single thing your computer does, from displaying pixels to encrypting passwords, ultimately reduces to millions of these tiny binary decisions happening billions of times per second.

Secondary Questions This Project Answers

Question	Answer You’ll Discover
Why does `x & 1` check if x is odd?	Odd numbers always have bit 0 set; AND extracts it
How can I store 8 flags in one byte?	Each bit position represents one boolean flag
Why is `x << 3` the same as `x * 8`?	Shifting left by n multiplies by 2^n
Why is `~5` equal to `-6`, not `-5`?	Two’s complement: `~x = -(x+1)`
How do subnet masks work?	AND with mask extracts network portion
How can I swap without a temp variable?	XOR swap: `a^=b; b^=a; a^=b;`

6. Concepts You Must Understand First

Before starting this project, ensure you understand these concepts:

Concept	Why It Matters	Where to Learn	Priority
Binary Number System	All bitwise ops work on binary	P01 of this path, any CS book	Critical
Hexadecimal Notation	Compact way to represent bits	P01, P02 of this path	Critical
Boolean Logic (AND/OR/NOT)	Foundation of all bitwise operations	Discrete math, “Code” by Petzold	Critical
Two’s Complement	Explains why ~x behaves as it does	CS:APP Ch. 2	Important
Positional Notation	Understanding place values in any base	Elementary math, reinforced in P01	Required
Command-Line Argument Parsing	Your tool needs to accept user input	Python: `sys.argv` or `argparse`	Helpful
Integer Overflow	What happens when shifts go too far	CS:APP Ch. 2	Helpful
Operator Precedence	Bitwise ops have surprising precedence	Language reference	Helpful

Truth Tables You MUST Memorize

AND (&)          OR (|)           XOR (^)          NOT (~)
& 0 = 0        0 | 0 = 0        0 ^ 0 = 0        ~0 = 1
& 1 = 0        0 | 1 = 1        0 ^ 1 = 1        ~1 = 0
& 0 = 0        1 | 0 = 1        1 ^ 0 = 1
& 1 = 1        1 | 1 = 1        1 ^ 1 = 0

7. Questions to Guide Your Design

Work through these questions BEFORE writing code:

Input & Parsing

How will you detect whether input is decimal (42), hex (0xAC), or binary (0b1010)?
What happens if the user enters an invalid format? How will you report errors?
Should negative numbers be supported? How does -5 differ from ~5?
How will you handle IP address format (192.168.1.1) as a special case?

Operation Handling

How will you parse operation names? Accept both AND and &?
For NOT, there’s only one operand. How will you handle this differently?
For shifts, the second “operand” is a count, not a value. How do you distinguish?
Should you support chained operations like 0xFF AND 0x0F OR 0x80?

Output & Visualization

How will you determine the appropriate bit width (8, 16, 32, 64)?
How will you align binary digits vertically for clear visualization?
Should you show leading zeros? (0x05 as 0000 0101 vs 101)
How will you format the operation symbol (& or “AND”)?

Real-World Applications

Can you detect and explain common patterns (permission masks, subnet masks)?
How might you add a “verbose” mode that explains WHY each operation is useful?

Design Philosophy

Should the calculator maintain state between operations (like bc)?
Would an interactive REPL mode be valuable, or is one-shot sufficient?
How might you support both decimal and binary output preferences?

8. Thinking Exercise

Before writing any code, work through these operations BY HAND with pencil and paper.

Part 1: AND Operation

Compute 0b11001010 AND 0b10101010:

Step 1: Align the binary numbers

         1 1 0 0 1 0 1 0    (0xCA = 202)
       & 1 0 1 0 1 0 1 0    (0xAA = 170)
         ─────────────────

Step 2: Apply truth table to each column

         Bit 7: 1 AND 1 = ?
         Bit 6: 1 AND 0 = ?
         Bit 5: 0 AND 1 = ?
         Bit 4: 0 AND 0 = ?
         Bit 3: 1 AND 1 = ?
         Bit 2: 0 AND 0 = ?
         Bit 1: 1 AND 1 = ?
         Bit 0: 0 AND 0 = ?

Step 3: Write the result
         ─────────────────
         ? ? ? ? ? ? ? ?    = 0x?? = ???

[Work this out yourself before checking!]

Part 2: OR Operation

Compute 0b00110011 OR 0b11110000:

         0 0 1 1 0 0 1 1    (0x33 = 51)
       | 1 1 1 1 0 0 0 0    (0xF0 = 240)
         ─────────────────
         ? ? ? ? ? ? ? ?    = 0x?? = ???

Part 3: XOR Operation

Compute 0b10101010 XOR 0b11111111:

         1 0 1 0 1 0 1 0    (0xAA = 170)
       ^ 1 1 1 1 1 1 1 1    (0xFF = 255)
         ─────────────────
         ? ? ? ? ? ? ? ?    = 0x?? = ???

Notice: XOR with 0xFF is the same as NOT!

Part 4: Bit Shift

Compute 0b00001011 << 3:

Original:    0 0 0 0 1 0 1 1    (11)
                   \   \   \
                    \   \   \   (shift left 3)
                     \   \   \
After:       0 1 0 1 1 0 0 0    = ???

Verify: Is the result equal to 11 * 8 = 88?

Part 5: Practical Application

You have a permission byte where:

Bit 0: Read permission
Bit 1: Write permission
Bit 2: Execute permission

Current permissions: 0b00000101 (read + execute, no write)

Task A: Use OR to ADD write permission

Current:     0 0 0 0 0 1 0 1
           | 0 0 0 0 0 0 1 0    (bit 1 = write)
             ─────────────────
             ? ? ? ? ? ? ? ?    Should be read + write + execute

Task B: Use AND with NOT to REMOVE execute permission

Current:     0 0 0 0 0 1 0 1
NOT mask:  ~ 0 0 0 0 0 1 0 0    = 0b11111011 (everything except bit 2)
           & Current
             ─────────────────
             ? ? ? ? ? ? ? ?    Should be read + write only

9. The Interview Questions They’ll Ask

After completing this project, you will be ready for these common interview questions:

Conceptual Questions

1. “What is the difference between & and &&?”

Expected answer:

& is BITWISE AND: operates on each bit independently
&& is LOGICAL AND: evaluates truth of operands, short-circuits
5 & 3 = 1 (0101 & 0011 = 0001)
5 && 3 = True (both non-zero)

Bonus: Explain short-circuit evaluation: && stops if first operand is false.

2. “How do you check if a number is odd using bitwise operations?”

Expected answer:

is_odd = (x & 1) == 1

Explanation: Odd numbers always have bit 0 set to 1.

3. “What does x & (x-1) do?”

Expected answer: Clears the lowest set bit.

x     = 0110 1100
x-1   = 0110 1011
x&x-1 = 0110 1000

Application: Count set bits (popcount) by looping until x becomes 0. Also: Check if power of 2: x & (x-1) == 0 means x has exactly one bit set.

4. “Why is ~0 equal to -1 and not some large positive number?”

Expected answer: Two’s complement representation.

~0 flips all bits: 0...0 becomes 1...1
In two’s complement, 1...1 represents -1
Identity: -x = ~x + 1, so ~0 + 1 = 0, meaning ~0 = -1

Practical Coding Questions

5. “Swap two integers without using a temporary variable.”

a = a ^ b
b = a ^ b  # b now has original a
a = a ^ b  # a now has original b

6. “Set the Nth bit of an integer.”

x = x | (1 << n)

7. “Clear the Nth bit of an integer.”

x = x & ~(1 << n)

8. “Toggle the Nth bit of an integer.”

x = x ^ (1 << n)

Systems/Networking Questions

9. “How do subnet masks work?”

Expected answer: The subnet mask is ANDed with an IP address to extract the network portion. Bits where the mask is 1 are the network address; bits where the mask is 0 are the host address.

Example: 192.168.1.105 AND 255.255.255.0 = 192.168.1.0 (network address)

10. “Explain Unix file permissions in terms of bitwise operations.”

Expected answer:

Each digit (e.g., 755) is 3 bits: read (4), write (2), execute (1)
Checking permission: (mode & permission_bit) != 0
Adding permission: mode | permission_bit
Removing permission: mode & ~permission_bit

Optimization Questions

11. “Why might you use x << 3 instead of x * 8?”

Expected answer:

Shifting is a single CPU instruction, multiplication is multiple
Modern compilers often optimize x * 8 to x << 3 anyway
But explicit shifts can be clearer in low-level code

12. “Implement popcount (count of set bits) efficiently.”

Basic approach (your calculator should show this):

count = 0
while x:
    x = x & (x - 1)  # Clear lowest set bit
    count += 1

Optimal: Use built-in CPU instruction (__builtin_popcount in C/GCC).

10. Hints in Layers

If you get stuck, reveal hints one at a time. Each layer provides more specific guidance.

Challenge 1: Parsing Input in Multiple Bases

Layer 1: General Direction

Python’s int() function can parse different bases. The key is detecting which base the input uses.

Layer 2: More Specific Guidance

# Python's int() with base 0 auto-detects!
int("42", 0)      # 42 (decimal)
int("0x2A", 0)    # 42 (hex)
int("0b101010", 0) # 42 (binary)
int("0o52", 0)    # 42 (octal)

Layer 3: Implementation Sketch

def parse_value(s):
    """Parse a string as int, auto-detecting base."""
    s = s.strip()
    try:
        return int(s, 0)  # Auto-detect base from prefix
    except ValueError:
        raise ValueError(f"Cannot parse '{s}' as a number")

Layer 4: Complete Solution with Edge Cases

def parse_value(input_str):
    """
    Parse a numeric string, auto-detecting base.
    Supports: decimal (42), hex (0xAC, 0XAC), binary (0b101, 0B101)
    """
    s = input_str.strip().lower()

    # Handle negative numbers
    negative = s.startswith('-')
    if negative:
        s = s[1:]

    try:
        value = int(s, 0)
        return -value if negative else value
    except ValueError:
        # Maybe it's an IP address?
        if '.' in s:
            return parse_ip_address(s)
        raise ValueError(f"Cannot parse '{input_str}' as a number")

def parse_ip_address(ip_str):
    """Convert IP address to 32-bit integer."""
    octets = ip_str.split('.')
    if len(octets) != 4:
        raise ValueError(f"Invalid IP address: {ip_str}")

    result = 0
    for octet in octets:
        result = (result << 8) | int(octet)
    return result

Challenge 2: Formatting Binary Output with Proper Alignment

Layer 1: General Direction

Use Python’s string formatting to create fixed-width binary strings, then add spacing between nibbles (groups of 4 bits).

Layer 2: More Specific Guidance

# Format as binary with leading zeros
f"{42:08b}"   # '00101010' (8 bits)
f"{42:016b}"  # '0000000000101010' (16 bits)

# Use bin() for variable width
bin(42)       # '0b101010' (no leading zeros)

Layer 3: Implementation Sketch

def format_binary(value, width=8):
    """Format as binary with spaces between nibbles."""
    binary = f"{value:0{width}b}"
    # Insert spaces every 4 bits: "01010101" -> "0101 0101"
    return ' '.join(binary[i:i+4] for i in range(0, len(binary), 4))

Layer 4: Complete Solution with Alignment

def format_binary(value, width=8, group_size=4):
    """
    Format a value as binary with grouped digits.

    Args:
        value: The integer to format
        width: Total bit width (8, 16, 32, 64)
        group_size: Bits per group (usually 4 for nibbles)
    """
    # Handle negative numbers (show as unsigned)
    if value < 0:
        value = value & ((1 << width) - 1)

    binary = f"{value:0{width}b}"
    groups = [binary[i:i+group_size] for i in range(0, width, group_size)]
    return ' '.join(groups)

def print_aligned_operation(a, b, result, op_symbol, width=8):
    """Print an aligned bitwise operation visualization."""
    a_bin = format_binary(a, width)
    b_bin = format_binary(b, width)
    r_bin = format_binary(result, width)

    # Build separator based on width
    sep_len = len(a_bin)

    print(f"  A = 0x{a:0{width//4}X}:   {a_bin}")
    print(f"    {op_symbol * (sep_len // 2)}".center(sep_len + 16))
    print(f"  B = 0x{b:0{width//4}X}:   {b_bin}")
    print(f"              {'-' * sep_len}")
    print(f"  Result:     {r_bin}")

Challenge 3: Implementing the NOT Operation Correctly

Layer 1: General Direction

The ~ operator in Python works on arbitrary-precision integers, which means ~5 gives -6, not what you might expect for a fixed-width NOT.

Layer 2: More Specific Guidance

For a true bitwise NOT with fixed width, you need to XOR with a mask of all 1s:

# 8-bit NOT
not_x = x ^ 0xFF

# 16-bit NOT
not_x = x ^ 0xFFFF

Layer 3: Implementation Sketch

def bitwise_not(value, width=8):
    """Compute NOT with fixed bit width."""
    mask = (1 << width) - 1  # Creates width 1-bits
    return value ^ mask

Layer 4: Complete Solution with Explanation

def bitwise_not(value, width=8):
    """
    Compute fixed-width bitwise NOT.

    Python's ~ operator gives -(x+1) due to infinite precision.
    For 8-bit: ~5 in Python = -6
    But we want: ~5 in 8-bit = 250 (0b11111010)

    Solution: XOR with all 1s of the appropriate width.
    """
    mask = (1 << width) - 1  # e.g., width=8 -> 0xFF
    result = value ^ mask

    # For display purposes, also show what Python's ~ gives
    python_not = ~value

    print(f"Input:             0x{value:0{width//4}X} ({value})")
    print(f"{width}-bit NOT:          0x{result:0{width//4}X} ({result})")
    print(f"Python ~:          {python_not} (infinite precision)")
    print()
    print(f"Why the difference?")
    print(f"  Python's ~ gives -(x+1) = -({value}+1) = {python_not}")
    print(f"  Fixed-width NOT: flip all {width} bits")

    return result

Challenge 4: Creating Visual Alignment for Binary Operations

Layer 1: General Direction

Think of each bit position as a column. You want to align operands vertically and show the operation happening per-column.

Layer 2: More Specific Guidance

Use consistent spacing and consider showing:

Bit position numbers as a header
Each operand on its own line
Operation symbols between operands
A separator line
The result

Layer 3: Implementation Sketch

def visualize_operation(a, b, op, result, width=8):
    # Header with bit positions
    positions = "  Bit: " + " ".join(f"{i:2d}" for i in range(width-1, -1, -1))
    print(positions)
    print("       " + "─" * (width * 3))

    # Operands with operation
    a_bits = [str((a >> i) & 1) for i in range(width-1, -1, -1)]
    b_bits = [str((b >> i) & 1) for i in range(width-1, -1, -1)]

    print(f"  A:   " + "  ".join(a_bits))
    print(f"  {op}:   " + "  ".join([op[0]] * width))
    print(f"  B:   " + "  ".join(b_bits))
    print("       " + "─" * (width * 3))

    r_bits = [str((result >> i) & 1) for i in range(width-1, -1, -1)]
    print(f"  =:   " + "  ".join(r_bits))

Layer 4: Complete Polished Solution

def visualize_bitwise_operation(a, b, op_name, result, width=8):
    """
    Create a beautiful ASCII visualization of a bitwise operation.
    """
    op_symbols = {
        'AND': '&', 'OR': '|', 'XOR': '^',
        'LSHIFT': '<<', 'RSHIFT': '>>'
    }
    symbol = op_symbols.get(op_name, op_name)

    # Calculate spacing
    col_width = 3
    total_width = width * col_width

    # Header with bit positions
    header = "".join(f"{i:>{col_width}}" for i in range(width-1, -1, -1))
    separator = "─" * total_width

    # Convert to bit strings
    def bits_to_str(val):
        return "".join(f"{((val >> i) & 1):>{col_width}}"
                       for i in range(width-1, -1, -1))

    # Print visualization
    print(f"\n  Bit Position: {header}")
    print(f"                {separator}")
    print(f"  A = {a:>{width//4 + 3}}:  {bits_to_str(a)}")
    print(f"      {symbol:^{width//4 + 3}}   " +
          "".join(f"{symbol:>{col_width}}" for _ in range(width)))
    print(f"  B = {b:>{width//4 + 3}}:  {bits_to_str(b)}")
    print(f"                {separator}")
    print(f"  Result:       {bits_to_str(result)}")
    print()

Challenge 5: Handling Shift Operations with Explanation

Layer 1: General Direction

Shifts are different from other binary operations: the second operand is a count, not a value to combine bit-by-bit. Show arrows or movement to visualize the shifting.

Layer 2: More Specific Guidance

For left shift, show bits moving left with zeros filling from the right. For right shift, show bits moving right with either zeros (logical) or sign bits (arithmetic) filling from the left.

Layer 3: Implementation Sketch

def visualize_shift(value, shift_amount, direction, width=8):
    if direction == 'left':
        result = (value << shift_amount) & ((1 << width) - 1)
        fill_char = '0'
        arrow = '←'
    else:
        result = value >> shift_amount
        fill_char = '0'  # or '1' for negative signed values
        arrow = '→'

    # Show the movement
    bits_before = format_binary(value, width)
    bits_after = format_binary(result, width)

    print(f"Before: {bits_before}")
    print(f"        " + arrow * shift_amount + " shift {direction} by {shift_amount}")
    print(f"After:  {bits_after}")

Layer 4: Complete Solution with Mathematical Explanation

def visualize_shift(value, shift_amount, direction, width=8):
    """
    Visualize a shift operation with arrows and explanation.
    """
    mask = (1 << width) - 1

    if direction == 'left':
        result = (value << shift_amount) & mask
        lost_bits = (value >> (width - shift_amount)) & ((1 << shift_amount) - 1)
        multiplier = 2 ** shift_amount
        arrow = "<<"
    else:
        result = value >> shift_amount
        lost_bits = value & ((1 << shift_amount) - 1)
        multiplier = 2 ** shift_amount
        arrow = ">>"

    # Create bit-by-bit visualization
    def format_with_markers(val, shift, direction):
        bits = f"{val:0{width}b}"
        if direction == 'left':
            # Mark bits that will be lost
            lost = bits[:shift]
            kept = bits[shift:]
            return f"[{lost}]{kept}"
        else:
            kept = bits[:-shift] if shift > 0 else bits
            lost = bits[-shift:] if shift > 0 else ""
            return f"{kept}[{lost}]"

    print(f"\n  Operation: {value} {arrow} {shift_amount}")
    print(f"  ─────────────────────────────────")
    print()
    print(f"  Original ({value}):")
    print(f"    Binary:  {value:0{width}b}")
    print(f"    Marked:  {format_with_markers(value, shift_amount, direction)}")
    print(f"             [brackets] = bits that will be {'lost' if direction == 'left' else 'shifted out'}")
    print()

    if direction == 'left':
        print(f"  After LEFT shift by {shift_amount}:")
        print(f"    Each bit moves {shift_amount} position(s) left")
        print(f"    {shift_amount} zero(s) fill in from the right")
        if lost_bits:
            print(f"    Lost bits: {lost_bits:0{shift_amount}b} ({lost_bits})")
    else:
        print(f"  After RIGHT shift by {shift_amount}:")
        print(f"    Each bit moves {shift_amount} position(s) right")
        print(f"    {shift_amount} zero(s) fill in from the left")
        if lost_bits:
            print(f"    Lost bits: {lost_bits:0{shift_amount}b} ({lost_bits})")

    print()
    print(f"  Result ({result}):")
    print(f"    Binary:  {result:0{width}b}")
    print(f"    Hex:     0x{result:0{width//4}X}")
    print(f"    Decimal: {result}")
    print()

    # Mathematical explanation
    print(f"  Mathematical Meaning:")
    if direction == 'left':
        print(f"    {value} << {shift_amount} = {value} * 2^{shift_amount}")
        print(f"                 = {value} * {multiplier}")
        print(f"                 = {value * multiplier}")
        if value * multiplier != result:
            print(f"    (Truncated to {width} bits: {result})")
    else:
        print(f"    {value} >> {shift_amount} = {value} / 2^{shift_amount}")
        print(f"                 = {value} / {multiplier}")
        print(f"                 = {value // multiplier} (integer division)")

    return result

11. Books That Will Help

Concept	Book	Chapter/Section	Why It Helps
Logic Gates	Code by Petzold	Ch. 10-11 “Logic and Switches”	Explains physical reality behind AND/OR/NOT
Boolean Algebra	Code by Petzold	Ch. 12 “A Binary Adding Machine”	How logic gates combine to do arithmetic
Bit-Level Operations	CS:APP by Bryant & O’Hallaron	2.1.7-2.1.9	Formal treatment of bitwise ops in C
Two’s Complement	CS:APP by Bryant & O’Hallaron	2.2	Why ~x = -(x+1) and other signed behavior
Bitwise Operators in C	K&R C	Ch. 2.9	Canonical reference for C operators
Bit Manipulation Tricks	Hacker’s Delight by Warren	Throughout	Hundreds of clever bit manipulation algorithms
Subnet Masks	Any networking book	IP addressing chapter	Real-world application of bitwise AND
File Permissions	The Linux Programming Interface	Ch. 15	Unix permissions as bit flags

12. Self-Assessment Checklist

Conceptual Understanding

Before moving on, you should be able to:

Write the truth table for AND, OR, XOR, and NOT from memory
Explain why x & 1 tests for odd/even
Explain why x & (x-1) clears the lowest set bit
Convert between ~x and -(x+1) in two’s complement
Explain why left shift multiplies by powers of 2
Describe how subnet masks use bitwise AND
Explain how Unix permissions use bitwise OR and AND

Implementation Skills

Your calculator should correctly:

Parse decimal, hex, and binary input formats
Handle AND, OR, XOR, NOT, LSHIFT, RSHIFT operations
Display aligned binary visualization
Show results in binary, hex, and decimal
Explain each operation in human-readable terms
Handle edge cases (negative numbers, overflow)

Mental Fluency

You should be able to mentally compute:

0xFF AND 0x0F = 0x0F (lower nibble extracted)
0x0F OR 0xF0 = 0xFF (nibbles combined)
0xAA XOR 0xFF = 0x55 (bits flipped)
1 << 4 = 16 (bit 4 set)
128 >> 3 = 16 (divide by 8)

Growth Verification

You can explain bitwise operations to someone else without notes
You recognize bitwise operations in production code
You consider bit manipulation when solving problems
You understand flag-based APIs (like Unix file permissions)

Extensions and Challenges

Beginner Extensions

Color output: Highlight set bits in green, cleared bits in red
Interactive mode: REPL that maintains last result for chaining
Expression mode: Parse expressions like (0xFF AND 0x0F) OR 0x80

Intermediate Extensions

IP address mode: Accept and display IP addresses with subnet math
Permission calculator: Unix-style chmod visualization
Bit counting: Add POPCOUNT, CLZ (count leading zeros), CTZ
Two’s complement mode: Show signed interpretations alongside unsigned

Advanced Extensions

Arbitrary width: Support 128-bit or arbitrary precision
Floating-point bits: Show IEEE-754 representation
Assembly output: Show equivalent x86/ARM instructions
Performance comparison: Benchmark bitwise vs arithmetic equivalents

Real-World Connections

Security and Cryptography

XOR cipher: plaintext ^ key = ciphertext; ciphertext ^ key = plaintext
Hash functions: Heavy use of XOR, rotations, and shifts
Random number generators: Bit manipulation for pseudo-randomness

Systems Programming

Memory-mapped I/O: Setting individual control bits
Hardware registers: Each bit controls a different function
File systems: Permission bits, flags, attributes

Graphics and Games

Color manipulation: RGBA packed into 32 bits
Tile maps: Compact storage of terrain types
Collision detection: Bitmask-based spatial hashing

Networking

Subnet calculations: Network address = IP AND mask
Protocol headers: Flags and options packed into bits
Checksums: XOR-based error detection

This project guide was created for the Binary & Hexadecimal learning path. For the complete learning path, see the project index. For prerequisites, complete P01: Universal Number Base Converter first.

Project 3: Bitwise Logic Calculator

Project Overview

Table of Contents

1. Learning Objectives

2. Deep Theoretical Foundation

2.1 What Bitwise Operations Actually Are

2.2 The Boolean Logic Foundation

2.3 The Bitwise Operators in Detail

AND (&) - The Bit Selector

OR (|) - The Bit Setter

XOR (^) - The Bit Flipper

NOT (~) - The Bit Inverter

2.4 Shift Operations

2.5 Common Bit Manipulation Patterns

2.6 Why x & 1 Checks for Odd/Even

2.7 Storing Multiple Flags in One Byte

3. Project Specification

3.1 What You Will Build

3.2 Example Usage

3.3 Output Format

3.4 Functional Requirements

4. Real World Outcome

Example 1: Understanding Permission Flags

Example 2: Setting Feature Flags

Example 3: Network Subnet Masking

Example 4: Shift Operations

5. The Core Question You’re Answering

Secondary Questions This Project Answers

6. Concepts You Must Understand First

Truth Tables You MUST Memorize

7. Questions to Guide Your Design

Input & Parsing

Operation Handling

Output & Visualization

Real-World Applications

Design Philosophy

8. Thinking Exercise

Part 1: AND Operation

Part 2: OR Operation

Part 3: XOR Operation

Part 4: Bit Shift

Part 5: Practical Application

9. The Interview Questions They’ll Ask

Conceptual Questions

Practical Coding Questions

Systems/Networking Questions

Optimization Questions

10. Hints in Layers

Challenge 1: Parsing Input in Multiple Bases

Challenge 2: Formatting Binary Output with Proper Alignment

Challenge 3: Implementing the NOT Operation Correctly

Challenge 4: Creating Visual Alignment for Binary Operations

Challenge 5: Handling Shift Operations with Explanation

11. Books That Will Help

Recommended Reading Order

12. Self-Assessment Checklist

Conceptual Understanding

Implementation Skills

Mental Fluency

Growth Verification

Extensions and Challenges

Beginner Extensions

Intermediate Extensions

Advanced Extensions

Real-World Connections

Security and Cryptography

Systems Programming

Graphics and Games

Networking

2.6 Why `x & 1` Checks for Odd/Even