Bit Manipulation

Bit Manipulation means working directly with the 0s and 1s inside an integer.

Four one-line moves — read, set, clear, drop — demonstrated on n=12:

                        1
                        bit i of n:        (n >> i) & 1
                      
                        2
                        set   bit i:       n | (1 << i)
                      
                        3
                        clear bit i:       n & ~(1 << i)
                      
                        4
                        drop lowest 1:     n & (n - 1)
                      
                        5
                        check power of 2:  n > 0 && (n & (n-1)) == 0
                      

The key idea:

Create a mask with 1 << i, then use AND, OR, XOR, or NOT depending on what you need.

Recognition Cheat Sheet

Main Trigger

Bit position i → create mask 1 << i → choose the operation.

1. Create a Bit Mask

int mask = 1 << i;

For example:

i = 2

1 << 2

0001
 ↓
0100

So bit 2 is represented by:

1 << 2

2. Check a Bit

Ask:

Is bit i currently 1?

public boolean isBitSet(int num, int i) {
    return (num & (1 << i)) != 0;
}

def is_bit_set(num, i):
    return (num & (1 << i)) != 0

bool isBitSet(int num, int i) {
    return (num & (1 << i)) != 0;
}

function isBitSet(num, i) {
  return (num & (1 << i)) !== 0;
}

Example:

num  = 0101
mask = 0100

0101
0100
----
0100  → bit is set

Recognition

“Is bit i set?” → AND

3. Set a Bit

Turn bit i ON.

public int setBit(int num, int i) {
    return num | (1 << i);
}

def set_bit(num, i):
    return num | (1 << i)

int setBit(int num, int i) {
    return num | (1 << i);
}

function setBit(num, i) {
  return num | (1 << i);
}

OR guarantees that the selected bit becomes 1.

Recognition

“Turn bit ON” → OR

4. Clear a Bit

Turn bit i OFF.

public int clearBit(int num, int i) {
    return num & ~(1 << i);
}

def clear_bit(num, i):
    return num & ~(1 << i)

int clearBit(int num, int i) {
    return num & ~(1 << i);
}

function clearBit(num, i) {
  return num & ~(1 << i);
}

~ flips the mask:

1 << i   →  00000100
~mask    →  11111011

AND then forces that bit to 0.

Recognition

“Turn bit OFF” → AND + NOT

5. Toggle a Bit

Flip:

0 → 1
1 → 0

public int toggleBit(int num, int i) {
    return num ^ (1 << i);
}

def toggle_bit(num, i):
    return num ^ (1 << i)

int toggleBit(int num, int i) {
    return num ^ (1 << i);
}

function toggleBit(num, i) {
  return num ^ (1 << i);
}

XOR with 1 flips the bit.

Recognition

“Flip/toggle bit” → XOR

6. Get Bit Value

Return exactly 0 or 1.

public int getBit(int num, int i) {
    return (num >> i) & 1;
}

def get_bit(num, i):
    return (num >> i) & 1

int getBit(int num, int i) {
    return (num >> i) & 1;
}

function getBit(num, i) {
  return (num >> i) & 1;
}

Think:

Shift bit i to the rightmost position
        ↓
AND with 1
        ↓
0 or 1

Recognition

“Get the ith bit” → Shift + AND

7. Useful Bit Operations

These appear frequently in interviews.

Check if number is odd

boolean isOdd = (num & 1) != 0;

Check if number is even

boolean isEven = (num & 1) == 0;

Remove the lowest set bit

num = num & (num - 1);

Example:

101100
101011
------
101000

Count set bits

int count = Integer.bitCount(num);

Pattern Evolution

Create mask
   ↓
1 << i
   ↓
Check   → num & mask
Set     → num | mask
Clear   → num & ~mask
Toggle  → num ^ mask
Get     → (num >> i) & 1

Common Mistakes

1. Checking against 1

Wrong:

(num & (1 << i)) == 1

Correct:

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

The result can be 2, 4, 8, etc., not just 1.

2. Forgetting parentheses

Use:

num & (1 << i)

not:

num & 1 << i

3. Confusing OR and XOR

OR  → turn ON
XOR → flip

Interview Rule

Check → AND Set → OR Clear → AND + NOT Toggle → XOR Get → Shift + AND

The one pattern to remember:

int mask = 1 << i;

Start with the mask, then choose the operation based on what the question asks.