Core Concepts You Must Understand First :-

1. Bits work independently — No Carry No interaction :-

When we do normal addition for example: 9 + 5 = 14.
The addition of the 1st position created a carry that changed the 2nd position.

But in the bitwise world (&, |, ^) — There is NO Carry!

Let's look at an XOR example :

     1 0 1 0  (10)
   ^ 1 1 0 0  (12)
     -------
     0 1 1 0  (6)

Notice carefully:

• The 0-th bit of the ans only depends on the 0-th bits of the inputs.
• The 1-st bit of the ans only depends on the 1-st bits of the inputs.

Core Idea :- Every single bit position is completely independent.
What happens at the 3rd bit position has absolutely zero effect on the 4th or 2nd bit position.

This simple observation is exactly what allow us to break down massive $$$O(N^2)$$$ problems into super fast $$$O(30 \times N)$$$ solutions.
We stop looking at the Whole Number and start looking at the Bit Columns one by one.

2. XOR Properties like Algebra — Must Master :-

Maximum of intermediate level bitwise problems involve XOR (^).
XOR has some beautiful mathematical properties that acts like algebra.

You need to remember these 3 Golden Rules:

Rule 1 : Identity :- Anything XOR with 0 remains the same — A ^ 0 = A

Rule 2 : Self inverse :- Anything XOR with itself becomes 0. (They destroy each other) — A ^ A = 0

Rule 3 : Order Doesn't Matter :- You can shuffle the elements any way but result remains same — A ^ B ^ C = C ^ A ^ B

Application :-

Imagine a problem gives you this equation: X ^ A = B, and you need to find the value of X.

In normal math, if X + 2 = 5, you subtract 2 from both sides but in bitwise math, you just XOR both sides by A !

    (X ^ A) ^ A = B ^ A
    X ^ (A ^ A) = B ^ A     // Grouping A together
    X ^ 0       = B ^ A     // cause A ^ A = 0
    X           = B ^ A     // cause X ^ 0 = X

The A just shifted to the other side! X = A ^ B.
This single trick will save you hours of debugging in math based bitwise problems.

3. The Power of MSB :-

The leftmost 1 in a binary number is called the Most Significant Bit (MSB).

In the binary world, there is a fundamental truth :-
"A single bit's value is strictly greater than the sum of ALL the bits to its right combined."

Formula :- 2^k > (2^(k-1) + 2^(k-2) + ... + 2^0)

Let's prove it easily :-

Suppose k = 3. The value is 2^3 = 8.
The sum of all lower bits :- 2^2 + 2^1 + 2^0 = 4 + 2 + 1 = 7 — Notice : 8 > 7 !

Let's look at the binary :-

   2^3   2^2   2^1   2^0
   ---------------------
    1     0     0     0    =  8  (Only 3rd bit is ON)
    0     1     1     1    =  7  (All lower bits are ON)

Even if all the smaller bits team up, they can never beat the single bit on their left.

Why is this important ?
Whenever a problem asks you to "Maximize the XOR" or "Find the lexicographically largest/smallest" you should immediately think of a Greedy Approach. You start checking from the highest bit (bit 30) down to 0, because securing a 1 at a higher position is always better than securing 1s at all lower positions !

4. Numbers in Binary are Actually Math Sets :-

When you see an integer (like 13), stop thinking of it as just a number.
Start thinking of it as a Mathematical Set of items !

• If the k-th bit is 1, it means the k-th item is Present in the set.
• If the k-th bit is 0, the k-th item is Absent.

Once you visualize a number as a Set, bitwise operators become Standard Set Theory operations :-

5. The Most Dangerous Bitwise Bug :-

This is the most common bug that destroys CP ratings.
Bitwise operators (&, |, ^) have a lower priority than equality operators (==, !=).

Look at this code where we want to check if the k-th bit is 0 :

if (x & (1 << k) == 0) {    // its a Deadly BUG !
    cout << "Bit is OFF";
}

Why is it wrong ?
Because == is evaluated first! The compiler calculates ((1 << k) == 0) which is usually false (0).
Then it does x & 0, which is always 0. The logic completely breaks down!

The Golden Rule :-

Whenever you mix bitwise operators with ==, <, >, or != -
always wrap the bitwise operation in an extra pair of parentheses. Safety first!

if ( (x & (1 << k)) == 0 ) { 
    cout << "Bit is OFF";
}

Get into the habit of using brackets in bitwise expressions.
It will save you from painful Wrong Answers (WA) on Hidden Test Cases !

The Power of Column-Wise Thinking :-

Let's look at a classic problem that separates beginners from intermediate problem solvers :

Problem : You are given an array $$$A$$$ of $$$N$$$ integers. You need to find the sum of $$$(A[i] \oplus A[j])$$$ for all pairs $$$(i, j)$$$ where $$$1 \le i \lt j \le N$$$.

If $$$N = 2 \times 10^5$$$ running a nested loop to check every single pair takes $$$O(N^2)$$$ time. This will give Time Limit Exceeded (TLE).

The Core Observation :

Remember the 1st Core Concept ? Bits work independently — No Carry No interaction
This means the $$$k\text{-th}$$$ bit of the answer is completely decided by the $$$k\text{-th}$$$ bits of the array elements.

Instead of adding numbers pair by pair horizontally, we can calculate the total contribution of each bit position vertically !

Let's Solve it Bit by Bit :

Let's take an array : $$$A = [2, 3, 5]$$$ — in binary (looking at the first 3 bits) :

Index 0 (Value 2) :  0  1  0
Index 1 (Value 3) :  0  1  1
Index 2 (Value 5) :  1  0  1
                     |  |  |
Bit Position :       2  1  0

Let's calculate the contribution of each bit column:

1. For Bit Position 0 (Value = $$$2^0 = 1$$$) :

• Look vertically down column 0: The bits are 0, 1, 1.
• Count of 1s (count_1) = 2
• Count of 0s (count_0) = 1
• When does an XOR operation give a 1? Only when we pair a 1 with a 0.
• How many such distinct pairs can we form ? count_1 * count_0 = 2 * 1 = 2 pairs.
• Since each pair contributes $$$2^0$$$ to the sum, total contribution from this bit = $$$2 \times 2^0 = 2$$$.

2. For Bit Position 1 (Value = $$$2^1 = 2$$$) :

• Look vertically down column 1 : The bits are 1, 1, 0.
• count_1 = 2, count_0 = 1
• Number of conflicting pairs = 2 * 1 = 2 pairs.
• Total contribution from this bit = $$$2 \times 2^1 = 4$$$.

3. For Bit Position 2 (Value = $$$2^2 = 4$$$) :

• Look vertically down column 2 : The bits are 0, 0, 1.
• count_1 = 1, count_0 = 2
• Number of conflicting pairs = 1 * 2 = 2 pairs.
• Total contribution from this bit = $$$2 \times 2^2 = 8$$$.

Final Answer = Sum of all bit contributions = $$$2 + 4 + 8 = 14$$$.

Let's Verify :- $$$(2 \oplus 3) + (2 \oplus 5) + (3 \oplus 5) = 1 + 7 + 6 = 14$$$. Perfect !

Beyond XOR : AND and OR Variations :-

This pattern is not just limited to XOR. You can apply it to AND (&) and OR (|) problems too :

• For Bitwise AND (&) : A pair only contributes if both bits are 1.

• For Bitwise OR (|) : A pair contributes if at least one bit is 1.
  It is easier to count the total possible pairs and subtract the pairs where both bits are 0.

Function Code (XOR Sum) :-

long long total_XOR_Sum(vector<int> &A) {
    long long total_sum = 0;
    int n = A.size();
    
    for (int k = 0; k < 30; k++) { 
        long long count_1 = 0;
        for (int i = 0; i < n; i++) {
            if ((A[i] >> k) & 1) {
                count_1++;
            }
        }
        
        long long count_0 = n - count_1;
        
        long long valid_pairs = count_1 * count_0;

        total_sum += valid_pairs * (1LL << k);
    }
    return total_sum;
}

Complexity :- $$$O(30 \cdot N)$$$ time and $$$O(1)$$$ extra space. This easily runs within the 1 second Time Limit for $$$N = 2 \times 10^5$$$.

How Addition Relates to XOR and AND :-

In many Div2 B and C problems, the problem statement mixes standard addition ($$$+$$$) with bitwise operations like XOR or AND. Whenever you see them mixed together, remember This Equation :

Understanding the Logic Behind the Equation :-

Why does this work ? Think back to how you learned addition in elementary school -
When you add two numbers, you calculate the base sums and then add the carries.

Let's look at how bitwise operations do exactly this in binary :

1. XOR (^) is Addition Without Carry :

• 0 + 0 = 0 $$$\rightarrow$$$ 0 ^ 0 = 0
• 1 + 0 = 1 $$$\rightarrow$$$ 1 ^ 0 = 1
• 1 + 1 = 0 (with a carry of 1) $$$\rightarrow$$$ 1 ^ 1 = 0

XOR does the addition perfectly but completely forgets to carry over the bits!

1. AND (&) Finds the Carries :

• A carry is generated only when both bits are 1.
• 1 & 1 = 1, which means a carry is born at this position.

Since a carry moves one position to the left, its value doubles.
Therefore, the total value of all carries combined is exactly $$$2\times(A \& B)$$$.

When you combine Addition without carry with The Carries, you get the true arithmetic sum !

True Sum = (Sum without carry) + (Carries)
A + B    = (A ^ B)             + 2 * (A & B)

Classic CP Problem :- (Reconstruct $$$A$$$ and $$$B$$$)

Problem : You are given two integers, $$$S$$$ (the sum of two numbers) and $$$X$$$ (the XOR of those two numbers). Find if there exist two non negative integers $$$A$$$ and $$$B$$$ such that $$$A + B = S$$$ and $$$A \oplus B = X$$$.

Using our equation, we can immediately figure out what the bitwise AND ($$$A \& B$$$) must be :

From this single formula, we can derive all necessary conditions for a valid solution :

1. $$$S$$$ must be greater than or equal to $$$X$$$ ($$$S \ge X$$$). (because bitwise AND cannot be negative).
2. $$$(S - X)$$$ must be even. (because we need to divide it by 2).
3. No bit can be shared : A fundamental property of bits is that a bit position cannot be 1 in both $$$(A\& B)$$$ and $$$(A \oplus B)$$$ at the same time. If a bit is in the XOR sum, it means the bits of $$$A$$$ and $$$B$$$ were different (1 and 0). If it is in the AND sum, it means both bits were 1. A position cannot have both different and identical bits !

Function Code :-

pair<long long, long long> reconstruct_A_and_B(long long S, long long X) {
    if (S < X || (S - X) % 2 != 0) {
        return {-1, -1}; 
    }
    
    long long AND_val = (S - X) / 2;

    if ((AND_val & X) != 0) {
        return {-1, -1}; 
    }

    long long A = AND_val + X;
    long long B = AND_val;
    
    return {A, B};
}

Why Bitwise AND Only Decreases and OR Only Increases :-

In standard math adding numbers can increase or decrease the sum (if negative).
But in the bitwise world AND and OR act like one way streets.

1. Bitwise AND (&) Never Increases : When you AND two numbers you can only destroy 1s (turn them into 0s).
   You can never create a new 1. Therefore, $$$A \& B \le \min(A, B)$$$.
2. Bitwise OR (|) Never Decreases : When you OR two numbers you can only create 1s (turn 0s into 1s).
   You can never destroy a 1. Therefore, $$$A \ | B \ge \max(A, B)$$$.

The "At Most 30 Changes" Magic Rule :

Because of this one-way nature, a mind-blowing property emerges in CP:

• If you take a number $$$X \le 10^9$$$ and continuously AND it with other numbers, the value can decrease at most 30 times !

Why ?
Because $$$10^9$$$ has at most 30 set bits (1s). Every time the AND value actually changes, it means at least one 1 turned into a 0. Since there are only 30 1s to begin with, the value can drop a maximum of 30 times before it becomes exactly 0.

Real Application :

Problem : You are given an array of $$$N$$$ elements ($$$N = 10^5$$$). You need to find the shortest subarray whose Bitwise AND is $$$\le K$$$.

If you check all subarrays, it’s $$$O(N^2)$$$. But because the AND sum always decreases as you add more elements, this becomes a perfect candidate for Binary Search or Two Pointers !

When you expand the subarray, the AND value drops. When you shrink the subarray, the AND value goes up.
This monotonic (one directional) behavior is the key to solving array-AND type problems.

Lets Visualize The AND Monotonicity :

Lets continuously AND the array : [15, 14, 11, 7]

Start: 15        -> 1 1 1 1  (Value: 15)
& 14 (1110)      -> 1 1 1 0  (Value: 14)  Dropped!
& 11 (1011)      -> 1 0 1 0  (Value: 10)  Dropped!
&  7 (0111)      -> 0 0 1 0  (Value:  2)  Dropped!

Notice how the 1s keep disappearing and the value strictly decreases.

Maximizing the Answer Greedily :-

Remember the 3rd Core Concept ? "The Power of MSB" — We proved that a single 1 at the $$$k\text{-th}$$$ position is worth more than all the 1s combined to its right ($$$2^k \gt 2^{k-1} + \dots + 2^0$$$).

In problems where you need to Maximize or Minimize a bitwise result, you should completely stop looking at the numbers as a whole. Instead, build your answer bit by bit, Starting from The Most Significant Bit (MSB) down to The 0th Bit.

The Strategy:

Suppose you want to maximize an answer. You loop from $$$k = 30$$$ down to $$$0$$$:

1. Assume the $$$k\text{-th}$$$ bit of our answer can be 1.
2. Check if this assumption breaks any rules of the problem.
3. If it is valid, keep the 1.
   It doesn't matter if keeping it forces all lower bits to be 0 because this single 1 is stronger than all of them !
4. If it is invalid, we are forced to set this bit to 0. Move to the next bit.

Classic Problem Example :

Problem : Given an integer $$$A$$$, find an integer $$$X$$$ ($$$0 \le X \le M$$$) such that $$$(A \oplus X)$$$ is maximized.

To maximize $$$(A \oplus X)$$$, we want the binary representation of the result to have 1s at the highest possible positions.
To get a 1 at the $$$k\text{-th}$$$ bit of the result, the $$$k\text{-th}$$$ bit of $$$X$$$ must be the opposite of the $$$k\text{-th}$$$ bit of $$$A$$$.

We iterate from $$$k = 30$$$ down to $$$0$$$.
We try to place the opposite bit in $$$X$$$, but we must make sure that our constructed $$$X$$$ does not exceed $$$M$$$ !

Function Code :

int maximize_XOR(int A, int M) {
    int X = 0;
    for (int k = 30; k >= 0; k--) {

        int bit_A = (A >> k) & 1;
        int wanted_bit = 1 - bit_A; 

        if (wanted_bit == 1) {
            if ((X | (1 << k)) <= M) {
                X |= (1 << k); 
            }
        } 
    }
    return X;
}

Erasing the Past with Prefix XOR

You already know about Prefix Sums. To find the sum of a range $$$[L, R]$$$, you do: Pref[R] - Pref[L-1]. But there is no subtraction (-) operator in bitwise logic. So, how do we find the XOR sum of a range?

We use the Magic Algebra of XOR: $$$A \oplus A = 0$$$. If you XOR the same thing twice, it completely vanishes!

Building the Prefix XOR Array :

Let's build a Prefix XOR array where Pref[i] = A[0] ^ A[1] ^ ... ^ A[i].

Now, suppose you want the XOR sum from index $$$L$$$ to $$$R$$$.
Notice that Pref[R] contains the XOR of ALL elements from the beginning up to $$$R$$$ :
Pref[R] = $$$(A[0] \oplus A[1] \dots \oplus A[L-1]) \oplus (A[L] \dots \oplus A[R])$$$

The unwanted part is the prefix before $$$L$$$, which is exactly Pref[L-1]. If we XOR Pref[R] with Pref[L-1], the unwanted part will be XORed twice, and it will destroy itself !

Visual Proof :

Array $$$A = [3, 1, 4, 6, 2]$$$ — Prefix XOR array :

• Pref[0] = 3
• Pref[1] = 3 ^ 1 = 2
• Pref[2] = 2 ^ 4 = 6
• Pref[3] = 6 ^ 6 = 0
• Pref[4] = 0 ^ 2 = 2

Let's find the Range XOR from $$$L = 1$$$ to $$$R = 3$$$ (which is $$$1 \oplus 4 \oplus 6 = 3$$$).
Using formula: Pref[3] ^ Pref[0] = 0 ^ 3 = 3. It match instantly !

This allows us to ans millions of range XOR queries in $$$O(1)$$$ Constant Time !

Function Code :

vector<int> build_Prefix_XOR(vector<int> &A) {
    int n = A.size();
    vector<int> pref(n);
    
    pref[0] = A[0];
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1] ^ A[i];
    }
    return pref;
}

int query_Range_XOR(vector<int> &pref, int L, int R) {
    if (L == 0) {
        return pref[R]; 
    }
    return pref[R] ^ pref[L - 1];
}

Moving from $$$O(4^N)$$$ to $$$O(3^N)$$$ in Bitmask DP :-

When working with bitmasks, we often represent a group of elements as a single integer (a mask).
A common requirement in little bit advanced DP is :

Problem : Given a specific integer mask, iterate through all of its subsets (submasks) efficiently.

For example, if your mask is 1011 (eleven), its submasks are all binary combinations that only use the bits present in the mask : 1011, 1010, 1001, 1000, 0011, 0010, 0001 and 0000.

The Naive Way :

You could loop from the value of mask down to 0, and check if each number is a valid submask using (i & mask) == i.
If you do this for every possible mask of size $$$N$$$, the time complexity becomes $$$O(2^N \times 2^N) = O(4^N)$$$. If $$$N = 15$$$, $$$4^{15} \approx 10^9$$$ operations, which will cause a TLE.

The Legendary One Liner Loop :

There is a legendary one liner loop that skips all invalid numbers and jumps Only to the valid Submasks :

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {

}

Why (sub - 1) & mask Works Perfectly :

Let's look at the expression: sub = (sub - 1) & mask.

1. When you subtract 1 from a binary number (sub - 1).
   It flips the lowest set bit (1 becomes 0) and turns all the 0s to its right into 1s.
2. By doing a Bitwise AND with the original mask (& mask), we instantly remove any 1s that were not part of our original set.
   It forces the new value to strictly remain a subset of the master mask.

Lets Visualize :

Lets watch the magic loop handle mask = 1011 (Binary for 11) :

Initial : sub = 1011 (11)

1. sub - 1 = 1010.  ->  1010 & 1011 = 1010 (10)   Next submask!
2. sub - 1 = 1001.  ->  1001 & 1011 = 1001 (9)    Next submask!
3. sub - 1 = 1000.  ->  1000 & 1011 = 1000 (8)    Next submask!
4. sub - 1 = 0111.  ->  0111 & 1011 = 0011 (3)    Next submask! (Notice the jump from 8 to 3)
5. sub - 1 = 0010.  ->  0010 & 1011 = 0010 (2)    Next submask!
6. sub - 1 = 0001.  ->  0001 & 1011 = 0001 (1)    Next submask!

The Complexity Miracle :

If you use this loop to iterate through the submasks of all possible masks from $$$0$$$ to ($$$2^N - 1$$$) The total number of operations across the entire solution drops to exactly $$$O(3^N)$$$ due to the binomial theorem.

For $$$N = 15$$$, $$$3^{15} \approx 14$$$ million operations, which executes in a fraction of a second ! Boom !!!

Function Code :

void enumerate_submasks(int mask) {
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        cout << sub << '\n'; 
    }
    cout << 0 << '\n';
}

O(1) Math Operations Without Floats :-

In Part 1, we introduced __builtin_clz (count leading zeros) and __builtin_ctz (count trailing zeros) as handy functions. But at an intermediate level these built-ins are used to replace slow math library functions like log2() or loops to calculate powers of 2.

They run in $$$O(1)$$$ constant time and are infinitely faster and safer than using floating-point math libraries.

Trick 1 : Fastest Way To Calculate $$$\log_2(X)$$$

In many problems you need to find the highest power of 2 that is $$$\le X$$$. This is mathematically equivalent to the floor of $$$\log_2(X)$$$.

Using floor(log2(x)) can suffer from precision inaccuracies cause it uses double to calculate.

The Bitwise Solution : A standard 32-bit integer has 32 bits total (indexed 0 to 31). If you count how many zeros exist before the first 1 (__builtin_clz(X)) you can find the exact bit index of the highest set bit !

Example: X = 8 (Binary: 00000000000000000000000000001000)
Leading Zeros = 28
Highest Bit Position = 31 - 28 = 3. 
Since 2^3 = 8, the math is perfectly accurate!

Trick 2 : Finding the Value of the Highest Power of 2

Once you know the position of the MSB, finding the value of that maximum power of 2 is trivial :

The Deadliest Trap : Passing Zero (0) :

Before using these functions you must know about this dangerous edge case :

Passing 0 into __builtin_clz(0) or __builtin_ctz(0) results in Undefined Behavior.

Because 0 has no set bits and for this your device cannot determine a valid starting or ending point. This will cause your code to return garbage values or completely crash with a runtime failure. Always ensure $$$X \gt 0$$$ before calling them !

Functions Code :

int fast_log2(int x) {
    if (x == 0) return -1;
    return 31 - __builtin_clz(x);
}

long long largest_power_of_2_below(int x) {
    if (x <= 0) return 0;
    return 1LL << (31 - __builtin_clz(x));
}

int lowest_set_bit_position(int x) {
    if (x == 0) return -1;
    return __builtin_ctz(x); 
}

For 64-bit integers (long long) make sure to use the ll versions : __builtin_clzll(x) and __builtin_ctzll(x)
and subtract from 63 instead of 31.

Solving Turn-Based Games Using XOR :-

In Div2 B or C problems you may frequently encounter a specific game scenario : Two Players (Assume Raha & Shadhin) are playing a game with several piles of stones. On each turn, a player can remove any number of stones (at least 1) from a single pile. The player who makes the last valid move (leaving zero stones remaining anywhere) wins the game.

This is the classic Nim Game. Finding a winning strategy using standard loops or greedy choices feels impossible, but Game Theory combined with an elegant XOR trick solves it instantly.

Understanding Winning and Losing States :

Let the sizes of the piles be represented as $$$A_1, A_2, A_3, \dots, A_n$$$.
To determine the winner, you only need to find the bitwise XOR sum of all the pile sizes, known as the Nim-Sum:

• If Nim-Sum $$$\neq 0$$$ : The game is in a Winning Position. The first player Raha can always make a move that forces the Nim-Sum to become exactly 0. With perfect play, Raha is guaranteed to win.
• If Nim-Sum $$$= 0$$$ : The game is in a Losing Position. No matter what Raha does, her move will force the Nim-Sum to become non-zero, giving the advantage back to Shadhin. With perfect play, Shadhin is guaranteed to win.

The Logic Behind This Strategy :

XOR has a unique self canceling property. When the overall Nim-Sum is non-zero, look at its Most Significant Bit (MSB). There must be at least one pile whose binary representation contains a 1 at that exact position. Raha can choose this pile and reduce its stones so that the entire array's XOR sum drops directly to 0.

Because a completely empty game state consists of piles of size $$$0$$$, the final state of the game naturally has a Nim-Sum of $$$0 \oplus 0 \dots \oplus 0 = 0$$$. Therefore, the player who can consistently force the game into a 0 state at the end of their turn will inevitably claim the final move and win.

Lets Visualize :

Suppose we have 3 piles with sizes: [3, 4, 5]

    3 -> 0 1 1
    4 -> 1 0 0
    5 -> 1 0 1
    -----------
    XOR Sum = 0 1 0  (2)

Since the XOR Sum is $$$2$$$ (non-zero), this is a Winning State for Raha. She wants to find a pile $$$A_i$$$ where $$$A_i \oplus \text{Nim-Sum} \lt A_i$$$.
Checking the first pile: $$$3 \oplus 2 = 1$$$, which is less than 3 !

Raha changes the first pile from 3 stones down to 1 stone. The new game state becomes [1, 4, 5]. Let's check the new XOR sum :

     1 -> 0 0 1
     4 -> 1 0 0
     5 -> 1 0 1
    -----------
XOR Sum = 0 0 0  (Perfect ! **Raha** successfully passed a 0 state to **Shadhin**)

No matter how many stones Shadhin removes next, the XOR sum will become non-zero again and which
Allowing Raha to repeat her strategy until she wins. Great ! Raha Wins !!!

Function Code :

string determine_winner(vector<int> &piles) {
    int nim_sum = 0;
    for (int x : piles) {
        nim_sum ^= x;
    }
    
    if (nim_sum != 0) {
        return "Raha";
    } else {
        return "Shadhin";
    }
}