🧠 Bit Manipulation — The Complete Guide (From Basics to Interviews)

Bit manipulation is one of those topics that looks scary, feels tricky, but is actually small, logical, and extremely powerful once the mental model clicks.

This article covers everything you need:

fundamentals
patterns
edge cases
interview tricks
real-world usage

Why Bit Manipulation Exists

At the lowest level, computers don’t understand numbers like 5 or 10.

They understand bits:

1 → ON
0 → OFF

Bit manipulation is about directly controlling these ON/OFF switches instead of relying on slower or heavier operations like division, modulo, or extra memory.

That’s why it appears in:

operating systems
permissions
compression
networking
interviews

Binary Representation (Foundation)

Every number is stored in binary.

Example:

5  →  101

Each bit position represents a power of 2.

Position:  2   1   0
Value:     4   2   1
Bits:      1   0   1   → 5

Signed Numbers & Two’s Complement (IMPORTANT)

Java stores negative numbers using two’s complement.

Steps to get -5:

Write 5 in binary → 00000101
Flip bits → 11111010
Add 1 → 11111011

Why this matters:

Right shift (>>) preserves sign
Unsigned shift (>>>) fills with zero
Loops using shifts can break for negatives

Interviewers love asking this verbally.

Bitwise Operators (Your Toolbox)

Operator	Meaning	Simple idea
`&`	AND	both bits must be 1
`	`	OR
`^`	XOR	bits are different
`~`	NOT	flip all bits
`<<`	Left shift	multiply by 2
`>>`	Right shift	divide by 2 (signed)
`>>>`	Unsigned shift	divide by 2 (safe)

Single-Bit Operations (Most Asked)

1. Set kth bit

n |= (1 << k);

2. Get kth bit

boolean isSet = (n & (1 << k)) != 0;

3. Clear kth bit

n &= ~(1 << k);

4. Toggle kth bit

n ^= (1 << k);

Common Checks Using Bits

Even or Odd

(n & 1) == 0

Power of 2

n > 0 && (n & (n - 1)) == 0

Power of 4

n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0

Counting Bits

Optimized: Brian Kernighan’s Algorithm

int count = 0;
while (n > 0) {
    n = n & (n - 1);
    count++;
}

Why it works:

n & (n - 1) removes the rightmost set bit
Loop runs only for number of 1s

Hamming Distance

Number of differing bits between two numbers.

int x = a ^ b;
int distance = 0;
while (x > 0) {
    x = x & (x - 1);
    distance++;
}

Used in:

error detection
networking
interview problems

XOR Patterns (Extremely Important)

XOR Rules

a ^ a = 0
a ^ 0 = a

Find Single Unique Element

int res = 0;
for (int n : arr) res ^= n;

Find Two Unique Elements

int xor = 0;
for (int n : arr) xor ^= n;

int rightMostBit = xor & -xor;

int a = 0, b = 0;
for (int n : arr) {
    if ((n & rightMostBit) != 0) a ^= n;
    else b ^= n;
}

This separates numbers into two groups.

Masking (State Control)

Mask = one number storing many ON/OFF decisions

Example:

mask = 1010

Used for:

permissions
feature flags
toggles

Check permission

(mask & (1 << i)) != 0

Subsets Using Bit Masking

Given:

[A, B, C]

Total subsets = 2^n

Each number from 0 to 2^n - 1 represents one subset.

🛠️ PART 6: SIMPLE CODE (DON’T PANIC)

int[] arr = {10, 20, 30};
int n = arr.length;

for (int mask = 0; mask < (1 << n); mask++) {
    System.out.print("{ ");
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            System.out.print(arr[i] + " ");
        }
    }
    System.out.println("}");
}

What’s happening:

outer loop → tries every ON/OFF combination
inner loop → checks which bits are ON

That’s it.

Bitmask DP (Advanced but Complete)

Used when:

states are small
choices are ON/OFF

Examples:

Traveling Salesman
Subset sum
Scheduling

Concept:

Store DP state as a bitmask instead of arrays.

(Keep this as a future deep dive.)

Edge Cases Interviewers Expect

n = 0
negative numbers
overflow on 1 << 31
shift limits
XOR assumptions breaking

Optimization Tips (Senior Thinking)

Replace % 2 with & 1
Prefer n & (n - 1) for counting
Use masks instead of arrays for flags
Avoid looping all 32 bits unnecessarily
Use >>> when sign doesn’t matter

Real-World Uses

OS permissions (read/write/execute)
Feature toggles
Bitmap indexing
Compression
Networking protocols

Mental Cheat Sheet (Save This)

Set bit       → n |= (1 << k)
Get bit       → (n & (1 << k)) != 0
Clear bit     → n &= ~(1 << k)
Toggle bit    → n ^= (1 << k)
Remove last 1 → n & (n - 1)
Even / Odd    → n & 1
Power of 2    → n > 0 && (n & (n - 1)) == 0

Thank you for your time and engagement. check out this article

Command Palette