Bit Manipulation & Binary Representation

What you'll learn

• 1. The Binary Number System

• Positional Notation

  Every number system is positional -- each digit's value depends on its position. Binary (base 2) works identically, but each position represents a power of 2:

• Decimal to Binary Conversion

  Repeatedly divide by 2 and collect remainders (bottom to top):

• Binary to Decimal Conversion

  Multiply each bit by its positional power of 2 and sum. ---

• 2. Two's Complement: Negative Numbers

• The Problem

  We need a way to represent negative integers using only 0s and 1s, while keeping addition hardware simple.

• How It Works

  For an n-bit integer: 1. Positive numbers are stored normally (leading 0). 2. Negative numbers are stored by inverting all bits and adding 1. To get -5 in 8-bit two's complement:

• Why It Works for Arithmetic

  The beauty of two's complement is that addition of positive and negative numbers uses the same circuitry:

• 8-Bit Two's Complement Range

  ---

• 3. Bitwise Operators

• AND (&) -- Masking and Checking

  Use cases: - Masking: Extract specific bits by ANDing with a mask of 1s in desired positions. - Check if bit is set: n & (1 >) -- Divide by Powers of 2 Arithmetic vs. Logical shift: - Arithmetic shift (>>): preserves sign bit (fills with…

• 4. Common Bit Tricks

• Check if Number is Power of 2

  Sample Input / Output Input: n = 8 (binary 1000) → Output: true (8 is a power of 2) Input: n = 6 (binary 0110) → Output: false (6 is not a power of 2) Input: n = 1 (binary 0001) → Output: true (1 = 2^0 is a power of 2 — edge case) Why it…

• Count Set Bits (Brian Kernighan's Algorithm)

  Sample Input / Output Input: n = 44 (binary 101100) → Output: 3 (three set bits) Input: n = 15 (binary 001111) → Output: 4 (four set bits) Input: n = 0 (binary 0000) → Output: 0 (zero set bits — edge case) Why it works: n & (n-1) always…

• Get / Set / Clear / Toggle the i-th Bit

  Sample Input / Output Input: n = 10 (binary 1010), i = 2 → Set bit 2 → Output: 14 (binary 1110) Input: n = 10 (binary 1010), i = 1 → Clear bit 1 → Output: 8 (binary 1000) Input: n = 10 (binary 1010), i = 3 → Toggle bit 3 → Output: 2 (bin…

• Swap Two Numbers Without a Temp Variable

  Sample Input / Output Input: a = 5, b = 3 → Output: a = 3, b = 5 Input: a = 12, b = 7 → Output: a = 7, b = 12 Input: a = 0, b = -1 → Output: a = -1, b = 0 — works with zero and negatives Why it works: XOR is its own inverse. After step 1…

• Find the Only Non-Repeating Element

  Given an array where every element appears twice except one, find that element. Sample Input / Output Input: [2, 3, 5, 3, 2] → Output: 5 Input: [7] → Output: 7 Input: [0, 1, 0, 1, -5] → Output: -5 — works with negatives and zero Why it w…

• Find Two Non-Repeating Elements

  Given an array where every element appears twice except two, find both. Sample Input / Output Input: [2, 3, 7, 9, 11, 2, 3, 11] → Output: 7, 9 Input: [1, 2, 3, 5, 1, 2] → Output: 3, 5 Input: [0, 0, -1, -2] → Output: -1, -2 — works with n…

• Subset Generation Using Bitmask

  Sample Input / Output Input: elements = ['a', 'b', 'c'] Output: [[], ['a'], ['b'], ['a','b'], ['c'], ['a','c'], ['b','c'], ['a','b','c']] — all 2³ = 8 subsets. Input: elements = ['x', 'y'] Output: [[], ['x'], ['y'], ['x','y']] — all 2² =…

• 5. Bitmask as a Set Representation

  A bitmask can represent a set of integers from a bounded universe {0, 1, ..., k-1} using a single integer of k bits. Set operations become bitwise operations: | Set Operation | Bitwise | Example | |---|---|---| | Union | A \| B | {1,3} \…

• 6. Python Specifics

• Arbitrary Precision Integers

  Unlike C/Java which have fixed 32-bit or 64-bit integers, Python integers have no fixed size. They grow as needed. This means: - No integer overflow. - Negative numbers in Python use a conceptual "infinite" sign extension of 1-bits to th…

• Useful Built-in Functions

• Practical Notes

  ---

• 7. When to Use Bit Manipulation

  Good fit: - Space optimization when storing boolean flags or small sets - Set operations on a universe of bounded size (up to ~20-25 for bitmask DP) - Permissions and feature flags (UNIX file permissions, game states) - Low-level optimiz…

• 8. Complexity Summary

  | Operation | Time | Space | |---|---|---| | Get/Set/Clear/Toggle bit | O(1) | O(1) | | Count set bits (Kernighan) | O(set bits) | O(1) | | Check power of 2 | O(1) | O(1) | | Find unique (XOR) | O(n) | O(1) | | Subset generation | O(2^n…

• 9. Quick Reference Card

  ---

• Related Topics

  - Bit Manipulation Patterns in the Algorithms path covers advanced interview patterns like bit DP, Gray codes, and Hamming distance problems. - Hash Tables use bit manipulation internally for fast modulo operations when table size is a p…