Bitwise operations are one of the most powerful tricks in programming — especially in competitive programming — because they are fast (O(1)) and help us manipulate numbers efficiently.

Basics

All numbers are stored in binary form (0s and 1s) in memory.

Each bit has a value:

• 0 → OFF
• 1 → ON

The last bit in a signed integer represents the sign:

• 0 → Positive
• 1 → Negative (in two’s complement form → invert bits + add 1)

Common Bitwise Operators

&   AND        → bit is 1 if both bits are 1  
|   OR         → bit is 1 if any bit is 1  
^   XOR        → bit is 1 if bits are different  
~   NOT        → inverts all bits  
<<  Left Shift → multiply by 2^x  
>>  Right Shift→ divide by 2^x

Binary Representation

#include <bitset>
#include <iostream>
using namespace std;

int main() {
    int a = 5;
    cout << bitset<32>(a) << endl;     // Binary representation of a
    cout << bitset<32>(~a) << endl;    // Binary of NOT a
}

bitset<32> means we represent the number using 32 bits.

Turning Bits On / Off / Flip

Turn ON bit x Make sure bit x = 1 (keep others unchanged):

a = a | (1 << x);

Explanation: (1 << x) shifts 1 to the left by x positions, so it creates a number with only one bit ON at position x. Then, using the OR | operation turns that bit ON without changing the others.

Turn OFF bit x Make sure bit x = 0:

a = a & ~(1 << x);

Explanation: (1 << x) marks the bit you want to turn off. ~ inverts all bits (so that the bit you want to clear becomes 0, and all others are 1). Then & keeps all bits the same, except that bit x becomes 0.

Flip bit x If it’s 1 → 0, if it’s 0 → 1:

a = a ^ (1 << x);

Explanation: ^ (XOR) changes a bit only if the bits differ. So this toggles the target bit: 1 → 0, 0 → 1.

Check if bit x is ON

Two ways:

if (a & (1 << x)) cout << "ON";
else cout << "OFF";

or

if ((a >> x) & 1) cout << "ON";

Identity Elements

Identity for AND (&) → all bits = 1
Identity for OR (|)  → all bits = 0
Identity for XOR (^) → all bits = 0

Important XOR Properties

a ^ a = 0
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)

Even / Odd Check

if (x & 1) cout << "Odd";
else cout << "Even";

Example: Can a string form a palindrome?

Idea: In a palindrome, every letter appears an even number of times — except possibly one. We use XOR to track whether each character appears an odd or even number of times.

string s;
cin >> s;
int ans = 0;

for (char c : s) {
    ans ^= 1 << (c - 'a');
}

// if at most one bit is ON → palindrome possible
if (ans == 0 || (ans & (ans - 1)) == 0)
    cout << "YES";
else
    cout << "NO";

Explanation of (ans & (ans - 1)) == 0: Example:

ans = 1000  
ans - 1 = 0111  
ans & (ans - 1) = 0000

This trick checks whether ans has only one bit ON (i.e., it’s a power of 2). If a number has just one set bit, subtracting 1 flips all bits after that position — so ans & (ans - 1) becomes 0. That’s why this condition means “at most one odd-count letter” → palindrome possible.

Built-in Bit Functions (GCC)

__builtin_popcount(x)    → Count 1s in integer
__builtin_popcountll(x)  → Count 1s in long long
__builtin_clz(x)         → Count leading zeros
__builtin_ctz(x)         → Count trailing zeros
__lg(x)                  → Position of the highest bit (≈ floor(log2(x)))

Explanation:

• __builtin_clz(x) → Counts how many zeros come before the first 1 from the left.
• __builtin_ctz(x) → Counts how many zeros come after the last 1 from the right. These are useful to find the position of the first or last set bit quickly.

Example

int x = 8;
cout << __builtin_popcount(x) << endl; // 1
cout << __lg(x) << endl;               // 3
cout << (1 << __lg(x)) << endl;        // 8

Summary

Turn ON bit: a = a | (1 << x)

Turn OFF bit: a = a & ~(1 << x)

Flip bit: a = a ^ (1 << x)

Check bit: (a >> x) & 1

Even / Odd: x & 1

Multiply by 2ˣ: a << x

Divide by 2ˣ: a >> x

All bitwise operations work in O(1). Mastering them can make your code shorter, faster, and smarter.