MANIPULATION BIT

Complete Study Notes • Binary • Operators • Tricks • Problems

Brute Force → Optimal Approach | Time & Space Complexity | Code Snippets

01 Decimal ↔ Binary 02 1s & 2s Complement 03 Bitwise Operators

04 Shift Operators 05 Negative Numbers 06 Bit Tricks

07 Check / Set / Clear Bit 08 Toggle / Remove Set Bit 09 Power of 2 Check

10 Count Set Bits 11 Swap Two Numbers 12 Single Number I/II/III

13 Power Set (Subsets) 14 XOR in Range 15 Divide without */ ÷

16 Min Bit Flips to Goal 17 Prime Factors & Sieve 18 Power Exponentiation

■ Key Insight: Bit manipulation is generally FASTER than generic methods — O(1) operations
instead of O(log n) or O(n)

Bit Manipulation — Complete Study Notes Page 1

 Decimal ↔ Binary Conversion
01
Why does this matter?

Computers only understand 0 and 1 — every integer is stored in binary. Understanding conversions is
the foundation of ALL bit manipulation.

DECIMAL → BINARY
Algorithm: Keep dividing by 2 until the number becomes 1.
At each step, record the remainder (0 or 1).
When the number reaches 1, read remainders from bottom to top — that is your binary.

Step n n÷2 Remainder

1 7 3 1 ← (read last)

2 3 1 1

3 (stop) 1 — 1 ← (read first)

(7)■■ → (111)■
Read remainders bottom-to-top: 1, 1, 1

Another example — (13)■■ → (1101)■:

13 ÷ 2 = 6 R1 | 6 ÷ 2 = 3 R0 | 3 ÷ 2 = 1 R1 | quotient=1
Read remainders bottom-to-top: 1, 1, 0, 1 → 1101

Code: Decimal → Binary (String)

o o o Code

string convert2Binary(int n) {
string res = "";
while (n != 1) {
if (n % 2 == 1) res += "1";
else res += "0";
n = n / 2;
}
reverse(res); // We collected from LSB, reverse to get MSB first
return res;
}

■ T: O(log■ n) | S: O(log■ n) — there are log■ n remainders to store

BINARY → DECIMAL
Algorithm: Start from the Right-Most Bit (RMB), index = 0. Move left, incrementing the index.

Decimal = Σ (bit × 2^index)

Example: (1101)■ → ?
Index: 3 2 1 0 (right to left)

Bit Manipulation — Complete Study Notes Page 2

 Bits: 1 1 0 1
Calculation: 1×2³ + 1×2² + 0×2¹ + 1×2■ = 8 + 4 + 0 + 1 = 13

Code: Binary String → Decimal

o o o Code

int convert2Decimal(string x) {
int len = [Link]();
int p2 = 1; // starts at 2^0 = 1
int num = 0;
for (int i = len-1; i >= 0; i--) { // start from RMB
if (x[i] == "1") // add only if bit is 1
num = num + p2;
p2 = p2 * 2; // increase 2-multiplier
}
return num;
}

■ T: O(len) | S: O(1)

Bit Manipulation — Complete Study Notes Page 3

 How Computers Store Integers & Complements
02
Computer storage of int x = 13

An int is 32 bits. The rightmost 4 bits hold 13 (1101), the remaining 28 bits are filled with 0.

long/long → 64 bits. The 31st bit (sign bit) is reserved for sign: 0 = positive, 1 = negative.

1■■ Complement
Step 1: Write the number in binary.
Step 2: Flip all bits (0→1, 1→0).
Example: (13)■■ = (1101)■ → flip → (0010)■

2■ Complement
Step 1: Find the 1■■ complement (flip all bits).
Step 2: Add 1 to the result.
Example: 13 → (1101)■ → flip → (0010)■ → +1 → (0011)■

Why 2's complement?

Computers store negative numbers using 2's complement. For -13:

① Take binary of 13: (0...01101)

② Find its 2's complement: flip → (1...10010), then +1 → (1...10011)

③ The leading '1' in the sign bit indicates it's negative.

The same result is also 2's complement. Negative numbers always have 1 as their sign bit.

Largest & Smallest Integers

Value Binary Pattern Decimal

INT_MAX 0 11111...1 (31 ones) 2³¹ - 1 = 2,147,483,647

INT_MIN 1 00000...0 (31 zeros) -2³¹ = -2,147,483,648

Important: NOT (~) operator

~x = -(x+1) in signed integers. So ~5 = -6.

Why? ~5 flips all bits, giving the 1s complement. Add the sign → -(5+1) = -6.

And ~(-6) = 5 — they are inverses!

Bit Manipulation — Complete Study Notes Page 4

 Bitwise Operators: AND, OR, XOR
03
AND (&) Both bits 1 → 1; else 0 Selects/Extracts bits

OR (|) Any bit 1 → 1; both 0 → 0 Sets bits

XOR (^) Odd # of 1s → 1; even # → 0 Toggles bits / detects difference

NOT (~) Flips all bits ~x = -(x+1)

Worked Examples
AND: x = 13 & 7 = 5
o o o Code

1101 (13)
& 0111 (7)
■■■■■■
0101 = 5

Why AND = 5?

Only bits that are 1 in BOTH numbers stay as 1. The bit at position 3 in 13 (=8) has no matching 1 in 7,
so it gets cleared.

OR: x = 13 | 7 = 15
o o o Code

1101 (13)
| 0111 (7)
■■■■■■
1111 = 15

XOR: x = 13 ^ 7 = 10
o o o Code

01101 (13)
^ 00111 (7)
■■■■■■■■
01010 = 8 + 2 = 10

XOR Key Properties (Must Know!)

① a ^ a = 0 (same number XOR itself = 0)

② a ^ 0 = a (XOR with 0 returns same number)

③ XOR of odd count of 1s → 1; even count → 0

④ Commutative & Associative: a^b = b^a and (a^b)^c = a^(b^c)

⑤ Used to SWAP two numbers without a third variable (see Section 6)

Bit Manipulation — Complete Study Notes Page 5

 Shift Operators: << and >>
04
RIGHT SHIFT » (Divide by 2^k)
x >> k = x / 2^k
The rightmost k bits are dropped off the cliff. Empty bits on the left are filled with 0 (for positive numbers).

Expression Binary before Binary after Decimal

13 » 1 00001101 00000110 6 (=13/2)

13 » 2 00001101 00000011 3 (=13/4)

13 » 4 00001101 00000000 0 (=13/16)

Pattern observation (Right Shift)

When we do 13»1: (1101)→(110), we notice:

13 = 1×2³+1×2²+0×2¹+1×2■

6 = 1×2²+1×2¹+0×2■ — same bits but each power reduced by 1!

The change is just extra multiples of 2 being removed. Hence x»k = x/2^k.

LEFT SHIFT « (Multiply by 2^k)

num << k = num × 2^k
Bits shift left. The leftmost bits fall off. Empty spots on the right are filled with 0.
o o o Code

13 << 1 = 26
// 00001101 → 00011010 = 26 = 13 × 2

// The new bits gain extra powers of 2: 0×2■ + 0×2■ + 1×2■ + 1×2³ + 0×2² + 1×2¹ +
0×2■
// Pattern: num << k = num × 2^k

■ Overflow Warning

(2³¹ - 1) « 1 → OVERFLOW! When leftmost bit shifts off the sign bit, the result wraps around to a large
negative number.

Always check: if shifting left by k bits, make sure you have room.

Binary Search optimization using shift

Instead of (low + high) / 2, use (low + high) » 1

Why? Division can overflow if low + high exceeds INT_MAX. Right shift handles it safely.

T: O(log N) worst if n = 2³¹

Bit Manipulation — Complete Study Notes Page 6

 Must-Know Bit Manipulation Tricks
05
TRICK 1 — Swap Two Numbers Without a Temp Variable
Classic: a=5, b=6. Without using any third variable, swap them.

Why XOR works for swap

Recall: a^a=0 and a^0=a

Step 1: a = a^b (a now holds combined info)

Step 2: b = a^b = (a^b)^b = a^(b^b) = a^0 = a ✓

Step 3: a = a^b = (a^b)^a = b^(a^a) = b^0 = b ✓

o o o Code

a = a ^ b; // step 1
b = a ^ b; // step 2: b gets original a
a = a ^ b; // step 3: a gets original b

■ Important: This method fails if a and b point to the SAME memory location. Always prefer temp variable in
practice.

TRICK 2 — XOR with 0 returns same number, XOR with itself = 0

5 ^ 5 = 0 | 5 ^ 0 = 5
Used in: Single Number I, XOR in range problems

General Note on Bit Manipulation Speed

Generally, bit manipulation is NOT faster than generic way — UNLESS the operation itself is O(log
n) or O(n) in the generic approach but O(1) in bit manipulation.

Example: Checking power of 2 is O(log n) naively but O(1) with bits.

For most problems till now: T → O(1)

Bit Manipulation — Complete Study Notes Page 7

 Operations on the i-th Bit
06
Check i-th bit
Is bit i set (1) or not (0)?
o o o Code

Brute Force: Convert to binary, traverse to bit i → O(log n)

// Optimal Approach 1: LEFT SHIFT

if (N & (1 << i)) != 0) return true; // bit is set
else return false; // not set

// How: (1<<i) places a 1 right below the i-th bit

// AND with N: if bit i is 1 → result != 0; if 0 → result = 0

// Optimal Approach 2: RIGHT SHIFT

// Move i-th bit to position 0, then AND with 1
if ((N >> i) & 1 == 0) → not set
else → set

Set i-th bit

Force bit i to 1
o o o Code

// Place a 1 right below the i-th bit using (1<<i)

// Perform OR operation
N | (1 << i)

// Why OR? At the i-th bit: 0 OR 1 = 1, 1 OR 1 = 1

// Other bits: 0 in (1<<i) → OR does NOT change original bits

// Example: N=9 (1001), i=2

// 1001
// |0100 <- (1<<2)
// 1101 = 13
// If already set, it does NOT alter it.

Clear i-th bit

Force bit i to 0 (unset it)
o o o Code

// We need 0 at position i, 1 at all others

// Create: ~(1<<i) — flip all bits of (1<<i)
// (1<<2) = 00100 → ~(1<<2) = 11011
// AND with N: other places have 1, so AND transfers them
// At i-th bit: if 1 → 1 & 0 = 0 ✓ if 0 → 0 & 0 = 0 ✓
N & ~(1 << i)

// T → O(1) for most problems

Bit Manipulation — Complete Study Notes Page 8

 Toggle i-th bit
Flip bit i (0→1, 1→0)
o o o Code

// Use XOR operator

// Place 1 right below i-th bit and XOR
N ^ (1 << i)

// Why XOR? At i-th bit:

// if bit == 0 → 0 XOR 1 = 1 (changed to 1) ✓
// if bit == 1 → 1 XOR 1 = 0 (changed to 0) ✓
// Other places: no. of ones unchanged, bits transferred

// Example: N=13 (1101), i=2

// 1101
// ^ 0100
// 1001 → 9

Check: if((N>>i)&1==0) | Set: N|(1<<i) | Clear: N&~(1<<i) |

Toggle: N^(1<<i)
All T → O(1)

Bit Manipulation — Complete Study Notes Page 9

 Remove Last Set Bit & Check Power of 2
07
REMOVE LAST SET BIT (Rightmost)
N & (N - 1)
Turns off the rightmost set bit

Observation: When you subtract 1 from N, the last set bit flips to 0 and all bits to its right become 1.
AND with original N: last set bit and below become 0 (since N-1 has 0 there now), other bits unchanged.

N Binary of N N-1 Binary N & (N-1)

12 1100 1011 1000 = 8

13 1101 1100 1100 = 12

16 10000 01111 00000 = 0

40 101000 100111 100000 = 32

Pattern in N and N-1:

The last set bit of N becomes 0, and all bits to its right become 1 (the exact inverse of N for those
positions).

CHECK IF NUMBER IS A POWER OF 2

Key observation

If N is a power of 2, it has EXACTLY ONE set bit. Examples:

16 = 10000 (1 set bit), 32 = 100000 (1 set bit)

Using N & (N-1): removes the last set bit. If N is power of 2, only one bit exists → result = 0.

if (N & (N-1) == 0) → Power of 2 ✓ else → NOT power of 2

T → O(1)

o o o Code

bool isPowerOf2(int N) {
return (N > 0) && ((N & (N-1)) == 0);
// N>0 handles edge case N=0 which would give false positive
}

Bit Manipulation — Complete Study Notes Page 10

 Count the Number of Set Bits
08
BRUTE FORCE — Check Each Bit
o o o Code

int countSetBits_BF(int n) {
int cnt = 0;
while (n > 1) {
cnt += (n & 1); // instead of n%2==1, use (n&1)
n = n >> 1; // instead of n=n/2, use n>>1 (faster!)
}
if (n == 1) cnt++; // handle last bit
return cnt;
}

■ T: O(log n) | S: O(1)
Why use (n&1) instead of (n%2==1)? Because & is a hardware instruction — faster than modulo.
Also: n»1 is faster than n/2 for the same reason.

OPTIMAL — Brian Kernighan Algorithm

Brian Kernighan's key insight

N & (N-1) turns off the LAST set bit.

So each iteration removes one set bit. We count how many times we can do this before N reaches 0.

T → O(number of set bits) = O(31) worst case = O(1)!

o o o Code

int countSetBits(int n) {
int cnt = 0;
while (N != 0) {
N = N & (N-1); // remove last set bit
cnt++;
}
return cnt;
}

// T → O(No. of set bits) = O(31) if N is INT_MAX

// S → O(1)

Walkthrough — N = 84 (1010100)
Step N (binary) N & (N-1) cnt

1 1010100 = 84 1010000 = 80 1

2 1010000 = 80 1000000 = 64 2

3 1000000 = 64 0000000 = 0 3

Result: 3 set bits in 84. ✓ (84 = 64+16+4 = 3 powers of 2)

Bit Manipulation — Complete Study Notes Page 11

 Minimum Bit Flips to Convert start → goal
09
Problem

Given start=10 (1010) and goal=7 (0111), find the minimum number of bit flips needed to convert start
to goal.

Key Insight: XOR gives 1 wherever bits differ

XOR of start and goal marks all positions where they differ — those are exactly the bits we need to flip!
o o o Code

start ^ goal → 1010 ^ 0111 = 1101 (3 set bits)

// Number of set bits in (start^goal) = minimum flips needed

ans = start ^ goal;

cnt = countSetBits(ans); // use Brian Kernighan!
return cnt;

Why does XOR work here?

XOR gives 1 only where the two bits are different. So every 1 in (start^goal) represents a position that
needs to be flipped.

Answer = popcount(start ^ goal)

popcount = count set bits

Alternative: Loop through all 32 bits

ans = start ^ goal

cnt = 0

for (i = 0 → 31): if (ans & (1«i)) → cnt++

return cnt

T → O(31) = O(1) | S → O(1)

Bit Manipulation — Complete Study Notes Page 12

 Single Number I — Find the Unique Element
10
Problem

Given an array where every element appears TWICE except one. Find that one. Range: -10■ ≤ nums[i]
≤ 10■

Example: [4, 1, 2, 1, 2] → return 4

Approach 1 (Brute Force) — HashMap

Store count of each number in a map. Traverse and find element with count = 1.
T: O(n log n) + O(m) | S: O(m) where m = distinct elements

Approach 2 (Optimal) — XOR

XOR magic: cancel pairs

Since every element appears twice, XOR all elements together.

Pairs cancel: a^a = 0. Only the single element survives.

XOR is commutative, so order does not matter.

4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4 ✓

o o o Code

int singleNumber(vector<int>& nums) {

int xorr = 0;
for (int i = 0; i < n-1; i++)
xorr = xorr ^ nums[i];
return xorr;
}
// T → O(N) | S → O(1)

Bit Manipulation — Complete Study Notes Page 13

 Single Number II — Every element 3x except one
11
Problem

Given an array where every element appears THRICE except one. Find that one.

Example: [5,5,5,2,4,4,4] → return 2

Approach 1 — HashMap: O(n log n) time, O(n) space

Approach 2 — Sorting: sort, check triplets → O(N log N)
Approach 3 (Better) — Compare Each Bit of All Numbers
For each bit position (0→31), count how many numbers have that bit set.
If count % 3 ≠ 0, then the single element has that bit set.
■ Why? If all elements appear 3 times, bit count at every position is divisible by 3. The extra 1s come only
from the single element.
o o o Code

int singleNumber(vector<int>& nums) {

int ans = 0;
for (int bitIndex = 0; bitIndex <= 31; bitIndex++) {
int cnt = 0;
for (int i = 0; i < n-1; i++)
if (nums[i] & (1 << bitIndex)) cnt++;
if (cnt % 3 == 1) // this bit belongs to single element
ans = ans | (1 << bitIndex); // set it in answer
}
return ans;
}
// T → O(N×32) | S → O(1)

Approach 4 (Optimal) — Buckets (ones & twos)

Bucket Concept

ones: stores element if it appears odd times so far (appears once currently)

twos: stores element if it appears twice so far

threes: bucket (but we delete from ones & twos, so no need to track threes)

Condition: if nums[i] is in ones AND it appears again → move to twos

Condition: if nums[i] is in twos AND appears again → delete from twos (appeared 3× = gone)

o o o Code

// Add to ones if not in twos: ones = (ones ^ nums[i]) & ~twos

// Add to twos if was in ones: twos = (twos ^ nums[i]) & ~ones
int ones = 0, twos = 0;
for (int i = 0; i < n-1; i++) {
ones = (ones ^ nums[i]) & ~twos;

Bit Manipulation — Complete Study Notes Page 14

 twos = (twos ^ nums[i]) & ~ones;
}
return ones; // single element survives in "ones"
// T → O(N) | S → O(1)

Bit Manipulation — Complete Study Notes Page 15

 Single Number III — Two Elements Appear Once
12
Problem

Array where every element appears TWICE except TWO numbers. Find both.

Example: [2,4,2,6,3,7,7,3] → return [4, 6] (in any order)

Strategy: XOR + Buckets

Step 1: XOR all elements → remaining = a^b (a and b are our two unique numbers)
Step 2: a and b must differ by at least 1 bit (they are distinct). Find that differing bit.
Step 3: Use that bit to separate all numbers into 2 buckets. Each bucket's XOR = one unique number.

o o o Code

long long xorr = 0;

for (int i = 0; i < n; i++) xorr ^= nums[i];

// Find rightmost set bit (where a and b differ)

long long rightmost = (xorr & (xorr - 1)) ^ xorr;
// Note: use long to avoid overflow if nums[i] = -2^31

long long b1 = 0, b2 = 0; // two buckets

for (int i = 0; i < n; i++) {
if (nums[i] & rightmost) b1 ^= nums[i]; // bit is set → bucket 1
else b2 ^= nums[i]; // bit not set → bucket 2
}
return {b1, b2};
// T → O(2N) | S → O(1)

Why find the rightmost set bit?

a^b has 1s at all positions where a and b differ. We pick ANY one of these positions (rightmost for
simplicity).

All numbers with this bit set go to b1; others to b2.

The two unique numbers land in different buckets. Pairs XOR to 0 in their bucket. So each bucket XOR
= unique number.

Bit Manipulation — Complete Study Notes Page 16

 Power Set — Generate All Subsets
13
Problem

Given nums = [1, 2, 3], generate all 2■ subsets: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

Key Insight: Binary representation of numbers 0 → 2■-1

For N=3 items, there are 2³=8 subsets. Number each subset 0 to 7.
The binary representation of each number tells you which items to include: bit i = 1 means include nums[i].

Number Binary (bit2 bit1 bit0) Subset

0 0 0 0 []

1 0 0 1 [1] (bit0 set → take nums[0])

2 0 1 0 [2] (bit1 set → take nums[1])

3 0 1 1 [1,2]

4 1 0 0 [3]

5 1 0 1 [1,3]

6 1 1 0 [2,3]

7 1 1 1 [1,2,3]

0 = Not Take, 1 = Take

o o o Code

vector<vector<int>> powerSet(vector<int>& nums) {

int n = [Link]();
int subsets = 1 << n; // = 2^n
vector<vector<int>> ans;
for (int num = 0; num < subsets; num++) { // 0 to 2^n-1
vector<int> list;
for (int i = 0; i < n; i++) { // check each bit
if (num & (1 << i)) // if bit i is set
[Link](nums[i]); // include nums[i]
}
[Link](list);
}
return ans;
}
// T → O(N × 2^N) | S → O(2^N × N)

Bit Manipulation — Complete Study Notes Page 17

 XOR of Numbers in Given Range
14
Part 1: XOR from 1 to N
Problem

Given N, find XOR of all numbers 1, 2, 3, ..., N

Example: N=4 → 1^2^3^4 = (1^2)^(3^4) = 3^7 = 4

Brute Force: Loop 1 to N, XOR each → T: O(N)

Optimal: Pattern in XOR of 1 to N:

N XOR(1..N) N%4 Pattern

1 1 1 return 1

2 3 2 return N+1

3 0 3 return 0

4 4 0 return N

5 1 1 return 1

6 7 2 return N+1

7 0 3 return 0

8 8 0 return N

o o o Code

int func(int N) {
if (N % 4 == 1) return 1;
if (N % 4 == 2) return N + 1;
if (N % 4 == 3) return 0;
return N; // N % 4 == 0
}
// T → O(1) | S → O(1)

Part 2: XOR of numbers in range [L, R]

Use prefix XOR: XOR(L..R) = XOR(1..R) ^ XOR(1..L-1)
Why? XOR is self-inverse — elements before L appear in both and cancel out.
o o o Code

int xorRange(int L, int R) {

return func(L-1) ^ func(R);
}
// T → O(1) | S → O(1)

Bit Manipulation — Complete Study Notes Page 18

 Divide Two Integers without × or ÷
15
Problem

Divide dividend by divisor without using multiplication (*) or division (/) operators.

Result must be in range [-2³¹, 2³¹-1]. Example: 22 ÷ 3 = 7

Edge case: if dividend = -2³¹ and divisor = -1, result = 2³¹ which overflows → return INT_MAX

Brute Force — Keep Subtracting

o o o Code

int divide_BF(int n, int d) {

int sum = 0, cnt = 0;
while (sum + d <= n) {
sum += d;
cnt++;
}
return cnt;
}
// T → O(dividend) → TLE for large inputs!

Optimal — Binary Powers of Divisor

Key Insight

Instead of subtracting d once at a time, subtract d×2^k at each step (the largest multiple of d that fits).

Example: 22 ÷ 3. Can we remove 3×2²=12? Yes (22≥12). Can we remove 3×2³=24? No.

So: 22 - 12 = 10, ans += 4. Then 10 - 6 = 4, ans += 2. Then 4 - 3 = 1, ans += 1. Total = 7.

o o o Code

long divide(long n, long d) {

int sign = 1;
if ((n>0 && d<0) || (n<0 && d>=0)) sign = -1;
n = abs(n); d = abs(d);
long ans = 0;
while (n >= d) {
int cnt = 0;
while (n >= (d << (cnt+1))) cnt++; // find largest power
ans += (1 << cnt); // add 2^cnt to answer
n -= d * (1 << cnt); // same as d × 2^cnt
}
// Handle overflow edge cases
if (ans >= 2^31 && sign == true) return INT_MAX;
if (ans >= 2^31 && sign == false) return INT_MIN;
return sign ? ans : (-1 * ans);

Bit Manipulation — Complete Study Notes Page 19

 }
// T → O(log■N)² | S → O(1)

Bit Manipulation — Complete Study Notes Page 20

 Advanced Maths: Prime Factors of a Number
16
Problem

Find all PRIME factors of N. Example: N=60 → return [2, 3, 5]

(60 = 2×2×3×5, but only unique primes: 2, 3, 5)

Brute Force
o o o Code

for (i=0; i<=N; i++) {

if (n%i == 0 && isPrime(i))
[Link](i);
}
// T → O(N × √N) | S → O(7) ≈ O(1)

Better Approach — Factor out each prime

We don't need to check isprime separately! Just iterate i=2 to √N:
If i divides N, divide N by i completely (while N%i==0, N=N/i), add i to list.
After the loop, if N>1, then N itself is a large prime — add N.
o o o Code

for (int i = 2; i*i <= N; i++) {

if (N % i == 0) {
[Link](i);
while (N % i == 0) N = N/i; // remove all factors of i
}
}
if (N > 1) [Link](N); // remaining N is a prime > √N
// T → O(√N × log N) | S → O(1)

// More optimal: for(i=2; i<=N; i++) — same logic, T→O(√N × logN)

Why only check up to √N?

If N has a factor larger than √N, the corresponding co-factor must be smaller than √N — and we would
have already found it.

Example: N=36. √36=6. Factors: 2,3,4,6 (all ≤6) and 9,12,18,36 (>6 but paired with 4,3,2,1).

Optimal for Multiple Queries — SPF (Sieve of Smallest Prime Factors)

Precompute SPF[i] = smallest prime factor of i for all i up to 10■.
o o o Code

// Precompute SPF
for (i = 1 → 10^5) spf[i] = i;
for (i = 2; i*i <= 10^5; i++) {
if (spf[i] == i) { // i is prime
for (j = i*i; j <= 10^5; j += i)

Bit Manipulation — Complete Study Notes Page 21

 if (spf[j] == j) spf[j] = i;
}
}
// For each query n, factorize in O(log n):
while (n != 1) { print(spf[n]); n = n / spf[n]; }
// T → O(N log log N + Q log N) | S → O(N)

Bit Manipulation — Complete Study Notes Page 22

 Sieve of Eratosthenes — All Primes till N
17
Problem

Given N, find all prime numbers from 2 to N.

Example: N=10 → [2, 3, 5, 7]

Brute Force: Check each i from 2 to N if prime → T: O(N × √N)

Optimal: Sieve of Eratosthenes

① Mark all numbers 2 to N as prime (1).
② Start at i=2. Mark all multiples of 2 (from 2×2) as not prime (0).
③ Move to next unmarked number, repeat.
④ Key optimization: start marking from i×i (not 2×i), since smaller multiples already marked.
⑤ Only go up to √N — if i×i > N, no new composites to mark.
o o o Code

void sieve(int N) {
bool prime[N+1];
fill(prime, prime+N+1, true);
prime[0] = prime[1] = false;
for (int i = 2; i*i <= N; i++) {
if (prime[i]) {
for (int j = i*i; j <= N; j += i)
prime[j] = false; // mark composite
}
}
// Collect primes
for (int i = 2; i <= N; i++)
if (prime[i]) [Link](i);
}
// T → O(N log(log N) + O(N)) ≈ O(N log log N)
// S → O(N)

Why start from i×i?

For prime i, all multiples i×2, i×3, ..., i×(i-1) were already marked by earlier primes.

The first unmarked multiple of i must be i×i. This optimization reduces marking redundancy.

Bit Manipulation — Complete Study Notes Page 23

 Power Exponentiation — Fast Power (pow(x, n))
18
Problem

Compute x^n efficiently. Example: pow(2, 5) = 32

Range: x can be up to 10■, n can be large. Must handle negative n.

Brute Force: Multiply x, n times → T: O(N)

Optimal: Binary Exponentiation

Key Insight — Use binary representation of n

x^20 = x^(10+10) = x^10 × x^10 → just 1 multiplication, not 10!

x^21 = x × x^20 → if n is odd, extract one x and solve x^(n-1)

If n is even: x^n = (x²)^(n/2) → square x, halve n

Each step halves n → only O(log n) steps!

o o o Code

double myPow(double x, long long n) {

if (n < 0) { x = 1.0/x; n = -n; } // handle negative exponent
double ans = 1.0;
while (n > 0) {
if (n % 2 == 1) { // n is odd → same as (n&1) == 1
ans = ans * x;
n = n - 1;
} else { // n is even
n = n / 2; // same as n >>= 1
x = x * x; // square x
}
}
return ans;
}
// T → O(log N) | S → O(1)

Dry Run: x=16, n=5 (odd → n-1=4, x same, ans×=16)

Step x n ans n odd/even

Start 16 5 1 odd

1 16 4 16 even

2 256 2 16 even

3 65536 1 16 odd

16×65536=10485
4 65536 0 76 stop

Final ans = 32 × 65536 = 1,048,576 = 16■ ✓ (just 4 steps instead of 5)

Bit Manipulation — Complete Study Notes Page 24

 Quick Reference — All Bit Tricks at a Glance
★
Operation Code Notes

Check i-th bit (N»i) & 1 OR if(N&(1«i)) 0=not set, 1=set

Set i-th bit N | (1«i) Force bit to 1

Clear i-th bit N & ~(1«i) Force bit to 0

Toggle i-th bit N ^ (1«i) Flip 0↔1

Remove last set bit N & (N-1) Rightmost 1 cleared

Power of 2 check N>0 && (N&(N-1))==0 T→O(1)

Count set bits while(N){N=N&(N-1);cnt++} Brian Kernighan

Swap a,b a^=b; b^=a; a^=b; No temp var needed

Right shift x » k = x / 2^k Drop k LSBs

Left shift x « k = x × 2^k Add k zero LSBs

XOR all → single no. xorr ^= nums[i] for all i Pairs cancel

Min flips to convert popcount(start ^ goal) XOR marks differences

Power Set for num in 0..(1«n)-1 T→O(N×2^N)

XOR 1..N Pattern on N%4 T→O(1)

Fast Power Binary exponentiation T→O(log N)

Prime factors Loop i=2 to √N T→O(√N × logN)

All primes till N Sieve of Eratosthenes T→O(N log log N)

General rule: bit manipulation is O(1) for single-number ops,

O(N) for array ops
Use (n&1) instead of n%2, use n>>1 instead of n/2 — both are faster!

Bit Manipulation — Complete Study Notes Page 25