ReviseAlgo Logo

Bit Manipulation

Bit Fundamentals

Master Bit Manipulation foundations: binary formats, signed shifts, and core AND, OR, XOR, NOT operations.

Last Updated: August 2, 2026 • 12 min read

1. Introduction

What is Bit Manipulation?

Bit Manipulation is the act of algorithmically manipulating bits (binary digits) inside data words directly. Instead of working with abstractions like lists or objects, we modify the raw 0s and 1s stored in memory registers.

Why study it?

Bit manipulation operations run in a single CPU clock cycle, making them extremely fast. They are frequently tested in interviews to evaluate your understanding of low-level machine architecture, memory allocation, and performance tuning.

Where is it Used?

  • Color Manipulation: Deconstructing 32-bit pixel words into individual Red, Green, Blue, and Alpha channels.
  • Cryptography: Standard ciphers (like AES) use XOR gates and left/right shifts to scramble text.

    • 2. Mental Model: The Panel of Light Switches

    Imagine a wall panel with 8 light switches:

  • Each switch represents a single bit (either 0 for Off or 1 for On).
  • An 8-bit integer is simply a specific configuration of these 8 switches.
  • AND (&): Only turns a light on if both corresponding input switches are on.
  • OR (|): Turns a light on if at least one input switch is on.
  • XOR (^): Turns a light on only if the two input switches are in different positions (one is on, the other is off).

    • 3. Core Bitwise Operations & Shift Mechanics

    Signed Integers: Two's Complement

    Negative integers are represented in binary using Two's Complement: 1. Take the absolute positive binary value. 2. Invert all bits (flip 0s to 1s and vice versa). 3. Add 1 to the result. Example: To find -5 in 8-bit binary: positive 5 is 00000101. Inverting bits yields 11111010. Adding 1 yields 11111011 (which is -5).

    Arithmetic vs. Logical Shifts

  • Left Shift (<<): Shifting bits to the left, filling empty spaces on the right with 0. Equivalent to multiplying the number by 2ᵏ.
  • Arithmetic Right Shift (>>): Shifting bits to the right while preserving the sign bit (filling the left spaces with the most significant bit). Equivalent to dividing by 2ᵏ.
  • Logical Right Shift (>>>): Shifting bits to the right while filling the left spaces with 0 regardless of the sign (yielding an unsigned number). Note: Python does not have a native >>> operator because it uses arbitrary-precision integers, but it can be simulated using bitwise masks.

    • 4. Visualizing Shift Operations

    Arithmetic Right Shift (>>) vs. Logical Right Shift (>>>) on a negative 8-bit byte:

    5. Real-World Examples

  • Subnet Mask Routing: Evaluating if an IP address fits a network interface by checking (ip & mask) == subnet.
  • RGB Color Extraction: Extracting color channels from a hex integer:
    • ```java int red = (rgb >> 16) & 0xFF; int green = (rgb >> 8) & 0xFF; int blue = rgb & 0xFF; ```

    6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test basic operations:
  • "What does XORing a number with itself result in?" -> A ^ A = 0. This is the core property used in problems like "Single Number".
  • "What is the difference between arithmetic and logical right shifts?" -> Arithmetic right shift (>>) preserves the negative sign bit by filling the left slots with 1s. Logical right shift (>>>) always fills left slots with 0s.

    • Common Mistakes

    Warning: 1. Mixing Logical and Bitwise Operators: Writing if (a & b) instead of if (a && b). Double symbols (&&, ||) are short-circuit logical evaluations, whereas single symbols (&, |) are binary operations.
    > 2. Forgetting Precedence: Attempting int val = 1 << i + 1. Because addition + has higher precedence than shift <<, this evaluates as 1 << (i + 1). Always wrap bit operations in parentheses: (1 << i) + 1.

    7. Summary

  • AND (&): Intersects bits. OR (|): Unifies bits.
  • XOR (^): Differs bits. Self-inverse: A ^ A = 0.
  • Shifts: << multiplies by 2, >> divides by 2 (keeps sign), >>> divides by 2 (flips sign to positive).

    • 8. Quiz

    Question 1: What is the binary value of ~0 (NOT 0) in 32-bit signed integers? Answer: -1 (represented as all 32 bits set to 1: 11111111111111111111111111111111).
    Question 2: What is the result of 12 ^ 12 ^ 5 ^ 3 ^ 5? Answer: 3. The duplicates cancel out due to XOR properties: 12 ^ 12 = 0 and 5 ^ 5 = 0. Thus, 0 ^ 0 ^ 3 = 3.
    Question 3: If x = -1, what is the result of x >>> 1 in Java? Answer: 2147483647 (represented as Integer.MAX_VALUE). The sign bit is shifted right and replaced by 0, converting it to the largest positive integer.
    Question 4: True or False: In C++, the result of right shifting a signed negative number is undefined by the language specification. Answer: True (historically). While most compilers implement arithmetic shifts, standard C++ specifications treated right shifts of signed negative numbers as implementation-defined until modern specifications resolved it.
    Question 5: What arithmetic operation is equivalent to value << 3? Answer: Multiplying value by 8 (2³ = 8).