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';
   }
}