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 C or D 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";
    }
}

Know The Bit

Binary is a number system that uses only two digits: 0 and 1. Each digit is called a bit.
A binary number is just a way to represent a decimal number using powers of 2.

 Binary :   1   0   1   0
 Value  :   8   4   2   1

Each position means a power of 2.
If the bit is 1, we take that value.
If the bit is 0, we ignore it.

So: 1010 = 8 + 2 = 10

and 1101 = 8 + 4 + 1 = 13

We usually read binary from right to left, starting from the 0th bit.

This is important because bitwise operations (AND, OR, XOR, NOT and Shifts) work directly on these bits instead of the decimal value. So if you understand binary properly, all bitwise tricks in CP become much easier to understand.

Watch for Better Idea :-

Bitwise AND (&)

Bitwise AND checks two bits one by one.
The result becomes 1 only when both bits are 1.
If any one of the bits is 0, the result becomes 0.
You can simply think: both need to be 1.

Example :

       1010
     & 1001
     ------
       1000  

     10 & 9 = 8

Bitwise OR (|)

Bitwise OR compares two bits one by one.
If at least one bit is 1, the result becomes 1.
Only 0 | 0 gives 0.
You can simply think: one 1 is enough.

Example :

       1010
     | 1001
     ------
       1011

     10 | 9 = 11

Bitwise XOR (^)

Bitwise XOR checks whether two bits are different or not.
If the bits are different, the result becomes 1.
If both bits are same, the result becomes 0.
You can simply think: different means 1.

Example :

       1010
     ^ 1001
     ------
       0011

     10 ^ 9 = 3

Bitwise NOT (~)

Bitwise NOT flips every bit of a number.
All 1 become 0 and all 0 become 1.
It just changes every bit to its opposite value.
This operation works on every bit individually.

Example :

     ~1010 = 0101

     ~10 = -11

Think => Why does this become negative ?
info => ~n = -(n+1) but think How and Why ?

Left Shift (<<)

Left Shift moves all bits to the left by n positions.
Every left shift usually multiplies the number by 2. More shifts mean a bigger value.
New empty places on the right become 0.

Example 1 :

     1010 << 1 = 10100

     10 << 1 = 20

Example 2 :

     0011 << 2 = 1100

     3 << 2 = 12

Right Shift (>>)

Right Shift moves all bits to the right side one by one n times.
Every right shift usually divides the number by 2 (integer / floor division).
Bits on the right side are removed.

Example 1 :

     1010 >> 1 = 0101

     10 >> 1 = 5

Example 2 :

     10100 >> 2 = 00101

     20 >> 2 = 5

1 << x vs 1LL << x

When we write: 1 << x the value 1 is treated as an int. int usually stores up to 32 bits.
So for very large shifts, the value can overflow and give wrong results.

But when we write: 1LL << x the 1LL becomes a long long.
A long long can store up to 64 bits, so it is much safer for large shifts.

I directly use: 1LL << x to stay safe for large values.

Example

     1 << 5

0001 -> 100000

     1 << 5 = 32

Check Odd or Even Number — (check the last bit)

Lets Look at The Binary Numbers from 0 to 6 :-

     000 = 0     
     001 = 1
     010 = 2
     011 = 3
     100 = 4
     101 = 5
     110 = 6
     ............

Now notice carefully:

• Numbers ending with 0 are even
• Numbers ending with 1 are odd

So the last bit represents odd or even.
- If last bit is 1 → number becomes odd
- If last bit is 0 → number becomes even

So to check odd or even, we only need the last bit.

We extract last bit using: x & 1

Because: - 1 & 1 = 1 and 0 & 1 = 0

So it always tells us the last bit directly.

Function:

bool is_Even(int x) {
  return !(x & 1);    
}

Check k-th Bit — Set (On bit) or Not Set (Off bit)

We can check whether any bit is set 1 or not set 0.

Let's take an example: 1101 (13)

Bits:       1 1 0 1
Position:   3 2 1 0

Now suppose we want to check bit at position 2.
We create a mask using: 1 << k
For k = 2 : 1 << 2 = 0100

Now apply:

     1101   (13)
     0100   (1 << 2)
     ----
     0100

Notice: — Result is not 0 So bit at position 2 is Set (ON).
If result becomes 0, then bit is Not Set (OFF).

So The Formula is: x & (1 << k)

Another way to think :-

If we right shift by k, then the k-th bit moves to the last position.

Example: 1101 >> 2 = 0011

Now we can check the last bit using & 1

Formula: (x >> k) & 1

Because: - Result 1 → bit is set - Result 0 → bit is not set

Function:

bool is_Set(int x, int k) {
   return (x & (1 << k));
}

iterate Through All bits of A Number

Sometimes we want to visit every bit of a number one by one.
We simply loop through all bit positions and check each bit.

Usually for int, we check from bit 0 to 31.

We use : (x >> k) & 1

Because:
- Right shift moves the k-th bit to the last position
- & 1 extracts that last bit

Example :

Let's take : x = 13 = 1101

Now check all bits:

     Bit 0 = 1
     Bit 1 = 0
     Bit 2 = 1
     Bit 3 = 1

So we can visit every bit one by one.

Function:

void iterate_Bits(int x) {
   for (int k = 0; k < 32; k++) {
      cout << ((x >> k) & 1) << ' ';
   }
}

Count Set Bits — (manual + popcount)

Set bit means bit value is 1.

Let's take an example: 1 1 0 1 - (13)

Here:
- 1st bit = ON
- 2nd bit = OFF
- 3rd bit = ON
- 4th bit = ON

So total set bits = 3

Manual Method :-

We can check the last bit using & 1

If last bit is 1, then increase count. Then right shift by 1 to check the next bit.

Function :-

int count_Set_Bits(int x) {
   int cnt = 0;
   while (x) {
      cnt += (x & 1);
      x >>= 1;
   }
   return cnt;
}

Built-in Function : (count number of set bits / on bits)

C++ provides a built-in function : __builtin_popcount(x)

Example : int cnt = __builtin_popcount(13); // 3

For long long : __builtin_popcountll(x)

Set and Clear (unset) the k-th Bit

Sometimes we want to turn a bit:
- ON (1) → Set bit
- OFF (0) → Unset/Clear bit

Let's take an example: 1001

Bits:       1 0 0 1
Position:   3 2 1 0

Suppose we want to Set bit at position 1.

We use : x | (1 << k) — Think Why and How ?

Because:- OR with 1 always makes that bit 1

Example :

     1001
     0010
     ----
     1011

So bit at position 1 becomes ON.

Set bit Function:

int set_Bit(int x, int k) {
   return (x | (1 << k));
}

Now suppose we want to Unset/Clear bit at position 3.

We use : x & ~(1 << k)

Because:
- ~(1 << k) makes all bits 1 except k-th bit
- AND with it turns that bit OFF

Example:

     1011
     0111
     ----
     0011

So bit at position 3 becomes OFF.

Unset/Clear bit Function:

int clear_Bit(int x, int k) {
   return (x & ~(1 << k));
}

Toggle/Flip the k-th Bit

Toggle means:
- If bit is 1 → make it 0
- If bit is 0 → make it 1

So it simply flips the bit.

Let's take an example: 1001

Bits:       1 0 0 1
Position:   3 2 1 0

Suppose we want to toggle bit at position 1.

We use : x ^ (1 << k) — Think Why and How ?

Because: - XOR with 1 flips the bit
- 1 ^ 1 = 0
- 0 ^ 1 = 1

Example:

     1001
     0010
     ----
     1011

So bit at position 1 changes from 0 to 1.

Now if we toggle again:

     1011
     0010
     ----
     1001

So bit changes back from 1 to 0.

That means toggle always flips the current state.

Toggle/Flip Function:

int toggle_Bit(int x, int k) {
   return (x ^ (1 << k));
}

Multiply and Divide by 2 Using Bitwise Shift

Bit shifting can quickly multiply or divide numbers by 2.

Left Shift (<<) → Multiply by 2

Every left shift multiplies the number by 2.

Example : 5 = 0101 — 0101 << 1 = 1010 — (5*2=10)

Another Example : 3 << 2 = 12

Because : 3 * (2^2) = 12

So N multiply by 2^k equals to N << k.

Function :

int multiply_By_2(int x, int k) {
   return (x << k);
}

Right Shift (>>) → Divide by 2

Every right shift divides the number by 2 (integer / floor division).

Example : 10 = 1010 — 1010 >> 1 = 0101 — 10 / 2 = 5

Another Example : 20 >> 2 = 5

Because : 20 / (2^2) = 5

So N divide by 2^k equals to N >> k.

Function :

int divide_By_2(int x, int k) {
   return (x >> k);
}

Remove the Lowest Set Bit

Sometimes we want to remove only the last ON bit (1) from a number.

We use : x & (x - 1)

Let's take an example: x = 12 1100

Now subtract 1 : 1100 - 1 = 1011

Now apply AND :-

     1100
   & 1011
     ----
     1000

Notice :- The lowest set bit disappeared.

Because:
- x - 1 changes the lowest 1 into 0
- AND removes that bit

So this trick removes the last ON bit very efficiently.

Function:

int remove_Lowest_Set_Bit(int x) {
   return (x & (x - 1));
}

Get the Lowest Set Bit

Sometimes we only want the value of the last ON bit.

We use : x & (-x)

Let's take an example : x = 12 1100

Now apply:

     1100
   & 0100
     ----
     0100

Result : 0100 = 4

So the lowest set bit value is 4.

This trick keeps only the last ON bit and removes all others.

Function:

int lowest_Set_Bit(int x) {
   return (x & (-x));
}

Count Trailing Zeros

Trailing zeros means zeros at the end of the binary number.

Example : 101000 - (40)

Notice : There are 3 zeros at the end — So trailing zeros = 3.

Built-in Function:

For int : __builtin_ctz(x) and For long long : __builtin_ctzll(x)

Count Leading Zeros

Leading zeros means zeros before the first ON bit (1).

Example:

13 = 00000000000000000000000000001101

Here many zeros exist before the first 1.

Built-in Function:

For int : __builtin_clz(x) and For long long : __builtin_clzll(x)

Find the Highest Set Bit Position

The highest set bit means the leftmost ON bit (1) in binary.

Let's take an example : 1101 - (13)

Bits:       1 1 0 1
Position:   3 2 1 0

Notice:
- The leftmost 1 is at position 3
So highest set bit position = 3.

We can check bits from left to right and find the first ON bit.

Function:

int highest_Set_Bit_Position(int x) {
   for (int k = 31; k >= 0; k--) {
      if ((x >> k) & 1) {
         return k;
      }
   }
   return -1;
}

Built-in Function:

For int : 31 — __builtin_clz(x) and for long long : 63 __builtin_clzll(x)

Check Whether a Number is Power of 2

A power of 2 number always has only one set bit 1.

Example :

     1   = 0001
     2   = 0010
     4   = 0100
     8   = 1000
     16  = 10000

Notice: - Every power of 2 contains only one 1

Now subtract 1 from a power of 2.

Example:

1000 - 1 = 0111

Now apply :

     1000
   & 0111
     ----
     0000

Result becomes 0

So Formula is: x & (x - 1)

If result is 0, then the number is a power of 2.

Because:
- Power of 2 has only one set bit
- Subtracting 1 changes that bit and all lower bits

Function:

bool is_Power_Of_2(int x) {
   return (x > 0) && !(x & (x - 1));
}

Find Unique Element Using XOR

Sometimes every number appears twice except one number.
We can find that unique number using XOR (^).

Because XOR has a special property:

     a ^ a = 0
     a ^ 0 = a

That means same numbers cancel each other.

Example :

     2  3  5  3  2

Now apply XOR one by one:

     2 ^ 3 ^ 5 ^ 3 ^ 2

Same numbers disappear:

     (2 ^ 2) ^ (3 ^ 3) ^ 5
     = 0 ^ 0 ^ 5
     = 5

So the unique element is 5.

This trick is very useful in CP.

Function:

int unique_Element(vector<int> &a) {
   int xr = 0;
   for (int x : a) {
      xr ^= x;
   }
   return xr;
}

Generate All Subsets Using Bitmask

A set with n elements has total 2^n subsets.

We can generate all subsets using bitmasking.

Example :

Suppose:

     a = {1, 2, 3}

Total subsets:

     2^3 = 8

We use numbers from 0 to (1 << n) - 1 as masks.

Mask    Binary    Subset
--------------------------------
0       000       {}
1       001       {1}
2       010       {2}
3       011       {1, 2}
4       100       {3}
5       101       {1, 3}
6       110       {2, 3}
7       111       {1, 2, 3}

Notice:
- If a bit is ON (1) → take that element
- If a bit is OFF (0) → ignore that element

So every mask represents one subset.

Function:

void generate_Subsets(vector<int> &a) {
   int n = a.size();
   for (int mask = 0; mask < (1 << n); mask++) {
      for (int k = 0; k < n; k++) {
         if ((mask >> k) & 1) {
            cout << a[k] << ' ';
         }
      }
      cout << '\n';
   }
}