Bitwise Operations was one of the most confusing topics for me at first. But once I started understanding how bits actually work, many CP problems suddenly became much easier to think about and optimize. ↵
↵
This blog is the result of a full day of grinding, where I tried to organize everything I know about bitwise tricks into a clear and structured form — from the basics to useful CP patterns. I tried to keep everything as simple and beginner-friendly as possible so that anyone can understand the core idea behind each trick instead of memorizing formulas. If even one trick from this blog helps someone solve a problem faster or understand bits more clearly, then this effort feels truly meaningful for me. ↵
↵
And finally, I want to express my deepest gratitude to `Raha Ahmed` for being The Strongest support in my CP journey. Her constant encouragement, belief and presence have played a huge role in shaping my progress and I’m truly grateful for everything she has done. ↵
↵
--- ↵
↵
## The Basics for Beginners :↵
--- ↵
↵
<spoiler summary="Basics All - (click here)">↵
↵
## 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`.↵
↵
```text↵
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 :-↵
↵
<iframe width="360" height="215" src="https://www.youtube.com/embed/zDNaUi2cjv4" ↵
title="YouTube video player" frameborder="0"↵
allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture"↵
allowfullscreen>↵
</iframe>↵
↵
↵
---↵
↵
↵
--- ↵
↵
## 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 :↵
↵
```text↵
1010↵
& 1001↵
------↵
1000 ↵
```↵
↵
```cpp↵
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 :↵
↵
```text↵
1010↵
| 1001↵
------↵
1011↵
```↵
↵
```cpp↵
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 :↵
↵
```text↵
1010↵
^ 1001↵
------↵
0011↵
```↵
↵
```cpp↵
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 :↵
↵
```text↵
~1010 = 0101↵
```↵
↵
```cpp↵
~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 :↵
↵
```text↵
1010 << 1 = 10100↵
```↵
↵
```cpp↵
10 << 1 = 20↵
```↵
↵
Example 2 :↵
↵
```text↵
0011 << 2 = 1100↵
```↵
↵
```cpp↵
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 :↵
↵
```text↵
1010 >> 1 = 0101↵
```↵
↵
```cpp↵
10 >> 1 = 5↵
```↵
↵
Example 2 :↵
↵
```text↵
10100 >> 2 = 00101↵
```↵
↵
```cpp↵
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 ↵
↵
```cpp↵
1 << 5↵
```↵
↵
` 0001 -> 100000`↵
↵
```cpp↵
1 << 5 = 32↵
```↵
↵
---↵
↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 1 : Check Odd or Even Number ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## Check Odd or Even Number — (check the last bit)↵
↵
Lets Look at The Binary Numbers from 0 to 6 :-↵
↵
```text↵
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:↵
↵
```cpp↵
bool is_Even(int x) {↵
return !(x & 1); ↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 2 : Check The k-th bit ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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)`↵
↵
```text↵
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:↵
↵
```text↵
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:↵
↵
```cpp↵
bool is_Set(int x, int k) {↵
return (x & (1 << k));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 3 : iterate Through All Bits↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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:↵
↵
```text↵
Bit 0 = 1↵
Bit 1 = 0↵
Bit 2 = 1↵
Bit 3 = 1↵
```↵
↵
So we can visit every bit one by one.↵
↵
---↵
↵
#### Function:↵
↵
```cpp↵
void iterate_Bits(int x) {↵
for (int k = 0; k < 32; k++) {↵
cout << ((x >> k) & 1) << ' ';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 4 : Count Set bits / On bits ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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 :-↵
↵
```cpp↵
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)`↵
↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 5 : Set and Clear The k-th bit ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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`↵
↵
```text↵
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 :↵
↵
```text↵
1001↵
0010↵
----↵
1011↵
```↵
↵
So bit at position `1` becomes ON.↵
↵
---↵
↵
#### Set bit Function:↵
↵
```cpp↵
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:↵
↵
```text↵
1011↵
0111↵
----↵
0011↵
```↵
↵
So bit at position `3` becomes OFF.↵
↵
---↵
↵
#### Unset/Clear bit Function:↵
↵
```cpp↵
int clear_Bit(int x, int k) {↵
return (x & ~(1 << k));↵
}↵
```↵
↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 6 : Toggle The k-th bit ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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`↵
↵
```text↵
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:↵
↵
```text↵
1001↵
0010↵
----↵
1011↵
```↵
↵
So bit at position `1` changes from `0` to `1`.↵
↵
---↵
↵
Now if we toggle again:↵
↵
```text↵
1011↵
0010↵
----↵
1001↵
```↵
↵
So bit changes back from `1` to `0`.↵
↵
That means toggle always flips the current state.↵
↵
---↵
↵
#### Toggle/Flip Function:↵
↵
```cpp↵
int toggle_Bit(int x, int k) {↵
return (x ^ (1 << k));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 7 : Multiply and Divide by 2↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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 :↵
```cpp↵
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 :↵
↵
```cpp↵
int divide_By_2(int x, int k) {↵
return (x >> k);↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 8 : Remove The Lowest Set bit↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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 :-↵
↵
```text↵
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:↵
↵
```cpp↵
int remove_Lowest_Set_Bit(int x) {↵
return (x & (x - 1));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 9 : Get The Lowest Set bit↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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:↵
↵
```text↵
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:↵
↵
```cpp↵
int lowest_Set_Bit(int x) {↵
return (x & (-x));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 10 : Count Trailing and Leading Zeros↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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)`↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 11 : Find The Highest Set Bit Position↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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)`↵
↵
```text↵
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:↵
↵
```cpp↵
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)`↵
↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 12 : Check whether A Number is Power of 2↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## Check Whether a Number is Power of 2↵
↵
A power of 2 number always has only one set bit `1`.↵
↵
Example :↵
↵
```text↵
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 :↵
↵
```text↵
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:↵
↵
```cpp↵
bool is_Power_Of_2(int x) {↵
return (x > 0) && !(x & (x - 1));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 13 : Find The Unique Element using XOR↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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:↵
↵
```text↵
a ^ a = 0↵
a ^ 0 = a↵
```↵
↵
That means same numbers cancel each other.↵
↵
---↵
↵
### Example :↵
↵
```text↵
2 3 5 3 2↵
```↵
↵
Now apply XOR one by one:↵
↵
```text↵
2 ^ 3 ^ 5 ^ 3 ^ 2↵
```↵
↵
Same numbers disappear:↵
↵
```text↵
(2 ^ 2) ^ (3 ^ 3) ^ 5↵
= 0 ^ 0 ^ 5↵
= 5↵
```↵
↵
So the unique element is `5`.↵
↵
This trick is very useful in CP.↵
↵
---↵
↵
#### Function:↵
↵
```cpp↵
int unique_Element(vector<int> &a) {↵
int xr = 0;↵
for (int x : a) {↵
xr ^= x;↵
}↵
return xr;↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 14 : Generate All Subsets using Bitmask ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## Generate All Subsets Using Bitmask ↵
↵
A set with `n` elements has total `2^n` subsets.↵
↵
We can generate all subsets using bitmasking.↵
↵
---↵
↵
### Example :↵
↵
Suppose:↵
↵
```text↵
a = {1, 2, 3}↵
```↵
↵
Total subsets:↵
↵
```text↵
2^3 = 8↵
```↵
↵
We use numbers from `0` to `(1 << n) - 1` as masks.↵
↵
```text↵
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:↵
↵
```cpp↵
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';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
### * *Part 2 (Intermediate Level) coming very soon !... RS1630** : [**Part-2 — Click Here**](https://codeforces.me/blog/entry/153864)↵
↵
--- ↵
↵
↵
↵
↵
↵
This blog is the result of a full day of grinding, where I tried to organize everything I know about bitwise tricks into a clear and structured form — from the basics to useful CP patterns. I tried to keep everything as simple and beginner-friendly as possible so that anyone can understand the core idea behind each trick instead of memorizing formulas. If even one trick from this blog helps someone solve a problem faster or understand bits more clearly, then this effort feels truly meaningful for me. ↵
↵
And finally, I want to express my deepest gratitude to `Raha Ahmed` for being The Strongest support in my CP journey. Her constant encouragement, belief and presence have played a huge role in shaping my progress and I’m truly grateful for everything she has done. ↵
↵
--- ↵
↵
## The Basics for Beginners :↵
--- ↵
↵
<spoiler summary="Basics All - (click here)">↵
↵
## 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`.↵
↵
```text↵
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 :-↵
↵
<iframe width="360" height="215" src="https://www.youtube.com/embed/zDNaUi2cjv4" ↵
title="YouTube video player" frameborder="0"↵
allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture"↵
allowfullscreen>↵
</iframe>↵
↵
↵
---↵
↵
↵
--- ↵
↵
## 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 :↵
↵
```text↵
1010↵
& 1001↵
------↵
1000 ↵
```↵
↵
```cpp↵
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 :↵
↵
```text↵
1010↵
| 1001↵
------↵
1011↵
```↵
↵
```cpp↵
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 :↵
↵
```text↵
1010↵
^ 1001↵
------↵
0011↵
```↵
↵
```cpp↵
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 :↵
↵
```text↵
~1010 = 0101↵
```↵
↵
```cpp↵
~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 :↵
↵
```text↵
1010 << 1 = 10100↵
```↵
↵
```cpp↵
10 << 1 = 20↵
```↵
↵
Example 2 :↵
↵
```text↵
0011 << 2 = 1100↵
```↵
↵
```cpp↵
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 :↵
↵
```text↵
1010 >> 1 = 0101↵
```↵
↵
```cpp↵
10 >> 1 = 5↵
```↵
↵
Example 2 :↵
↵
```text↵
10100 >> 2 = 00101↵
```↵
↵
```cpp↵
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 ↵
↵
```cpp↵
1 << 5↵
```↵
↵
` 0001 -> 100000`↵
↵
```cpp↵
1 << 5 = 32↵
```↵
↵
---↵
↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 1 : Check Odd or Even Number ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## Check Odd or Even Number — (check the last bit)↵
↵
Lets Look at The Binary Numbers from 0 to 6 :-↵
↵
```text↵
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:↵
↵
```cpp↵
bool is_Even(int x) {↵
return !(x & 1); ↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 2 : Check The k-th bit ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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)`↵
↵
```text↵
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:↵
↵
```text↵
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:↵
↵
```cpp↵
bool is_Set(int x, int k) {↵
return (x & (1 << k));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 3 : iterate Through All Bits↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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:↵
↵
```text↵
Bit 0 = 1↵
Bit 1 = 0↵
Bit 2 = 1↵
Bit 3 = 1↵
```↵
↵
So we can visit every bit one by one.↵
↵
---↵
↵
#### Function:↵
↵
```cpp↵
void iterate_Bits(int x) {↵
for (int k = 0; k < 32; k++) {↵
cout << ((x >> k) & 1) << ' ';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 4 : Count Set bits / On bits ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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 :-↵
↵
```cpp↵
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)`↵
↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 5 : Set and Clear The k-th bit ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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`↵
↵
```text↵
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 :↵
↵
```text↵
1001↵
0010↵
----↵
1011↵
```↵
↵
So bit at position `1` becomes ON.↵
↵
---↵
↵
#### Set bit Function:↵
↵
```cpp↵
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:↵
↵
```text↵
1011↵
0111↵
----↵
0011↵
```↵
↵
So bit at position `3` becomes OFF.↵
↵
---↵
↵
#### Unset/Clear bit Function:↵
↵
```cpp↵
int clear_Bit(int x, int k) {↵
return (x & ~(1 << k));↵
}↵
```↵
↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 6 : Toggle The k-th bit ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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`↵
↵
```text↵
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:↵
↵
```text↵
1001↵
0010↵
----↵
1011↵
```↵
↵
So bit at position `1` changes from `0` to `1`.↵
↵
---↵
↵
Now if we toggle again:↵
↵
```text↵
1011↵
0010↵
----↵
1001↵
```↵
↵
So bit changes back from `1` to `0`.↵
↵
That means toggle always flips the current state.↵
↵
---↵
↵
#### Toggle/Flip Function:↵
↵
```cpp↵
int toggle_Bit(int x, int k) {↵
return (x ^ (1 << k));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 7 : Multiply and Divide by 2↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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 :↵
```cpp↵
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 :↵
↵
```cpp↵
int divide_By_2(int x, int k) {↵
return (x >> k);↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 8 : Remove The Lowest Set bit↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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 :-↵
↵
```text↵
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:↵
↵
```cpp↵
int remove_Lowest_Set_Bit(int x) {↵
return (x & (x - 1));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 9 : Get The Lowest Set bit↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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:↵
↵
```text↵
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:↵
↵
```cpp↵
int lowest_Set_Bit(int x) {↵
return (x & (-x));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 10 : Count Trailing and Leading Zeros↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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)`↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 11 : Find The Highest Set Bit Position↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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)`↵
↵
```text↵
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:↵
↵
```cpp↵
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)`↵
↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 12 : Check whether A Number is Power of 2↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## Check Whether a Number is Power of 2↵
↵
A power of 2 number always has only one set bit `1`.↵
↵
Example :↵
↵
```text↵
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 :↵
↵
```text↵
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:↵
↵
```cpp↵
bool is_Power_Of_2(int x) {↵
return (x > 0) && !(x & (x - 1));↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 13 : Find The Unique Element using XOR↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## 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:↵
↵
```text↵
a ^ a = 0↵
a ^ 0 = a↵
```↵
↵
That means same numbers cancel each other.↵
↵
---↵
↵
### Example :↵
↵
```text↵
2 3 5 3 2↵
```↵
↵
Now apply XOR one by one:↵
↵
```text↵
2 ^ 3 ^ 5 ^ 3 ^ 2↵
```↵
↵
Same numbers disappear:↵
↵
```text↵
(2 ^ 2) ^ (3 ^ 3) ^ 5↵
= 0 ^ 0 ^ 5↵
= 5↵
```↵
↵
So the unique element is `5`.↵
↵
This trick is very useful in CP.↵
↵
---↵
↵
#### Function:↵
↵
```cpp↵
int unique_Element(vector<int> &a) {↵
int xr = 0;↵
for (int x : a) {↵
xr ^= x;↵
}↵
return xr;↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
↵
### Trick 14 : Generate All Subsets using Bitmask ↵
--- ↵
↵
<spoiler summary="Explanation - (click here)">↵
## Generate All Subsets Using Bitmask ↵
↵
A set with `n` elements has total `2^n` subsets.↵
↵
We can generate all subsets using bitmasking.↵
↵
---↵
↵
### Example :↵
↵
Suppose:↵
↵
```text↵
a = {1, 2, 3}↵
```↵
↵
Total subsets:↵
↵
```text↵
2^3 = 8↵
```↵
↵
We use numbers from `0` to `(1 << n) - 1` as masks.↵
↵
```text↵
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:↵
↵
```cpp↵
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';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
--- ↵
↵
### *
↵
--- ↵
↵
↵
↵
↵
