⚡ Bit Manipulation — CP Handbook
A clean, structured, competitive‑programming–ready handbook containing: - Full concepts (NO
problem‑solving steps) - Correct & simplified C++ code (int only) - Important properties & identities - Extra
formulas requested - Revision sheet
📑 Table of Contents
1. What is Bit Manipulation?
2. Decimal ⇄ Binary Conversion
3. Bitwise AND (&)
4. Bitwise OR (|)
5. Bitwise XOR (^)
6. Bitwise NOT (~)
7. Left Shift (<<)
8. Right Shift (>>)
9. Useful Properties & Identities
10. Extra Requested Formulas
11. Built‑in Functions
12. CP Template
13. One‑Page Revision Sheet
1. What is Bit Manipulation?
Bit manipulation means performing operations directly on bits (0/1). Computers internally store and
operate on numbers in binary.
Useful in: - Competitive programming - Optimization - Low‑level computations
2. Decimal → Binary Conversion
Code
string decToBinary(int n) {
string s = "";
if(n == 0) return "0";
while(n > 0) {
s += char('0' + (n % 2));
1
n /= 2;
}
reverse([Link](), [Link]());
return s;
}
3. Binary → Decimal Conversion
Code
int binaryToDec(string s) {
int val = 0, p = 1;
for(int i = [Link]()-1; i >= 0; i--) {
if(s[i] == '1') val += p;
p *= 2;
}
return val;
}
4. Bitwise AND (&)
Rule
•1&1→1
• Else → 0
Code
int bitAnd(int a, int b) {
return a & b;
}
5. Bitwise OR (|)
Rule
• If any bit is 1 → result = 1
2
Code
int bitOr(int a, int b) {
return a | b;
}
6. Bitwise XOR (^)
Rule
• Bits differ → 1
• Bits same → 0
Code
int bitXor(int a, int b) {
return a ^ b;
}
7. Bitwise NOT (~)
Rule
Flips all bits.
Code
int bitNot(int a) {
return ~a;
}
8. Left Shift (<<)
Meaning
a << k = multiply by 2ᵏ
3
Code
int LShift(int a, int k) {
return a << k;
}
9. Right Shift (>>)
Meaning
a >> k = divide by 2ᵏ (floor)
Code
int RShift(int a, int k) {
return a >> k;
}
10. Useful Properties & Identities
AND Properties
•a&a=a
• a & b ≤ min(a, b)
OR Properties
•a|a=a
• a | b ≥ max(a, b)
XOR Properties
•a^a=0
•a^0=a
•a^b^a=b
• XOR is reversible!
4
Power of Two Check
bool isPowerOfTwo(int n) {
if(n <= 0) return false;
return (n & (n - 1)) == 0;
}
11. Extra Requested Formulas
These are extremely important in CP.
✔ Formula 1 — OR + AND identity
a + b = (a | b) + (a & b)
✔ Formula 2 — XOR + AND identity
a + b = (a ^ b) + 2 * (a & b)
These come from binary addition rules.
12. Built‑in Functions
Count set bits
int countBits(int x) {
return __builtin_popcount(x);
}
13. CP Template
#include <bits/stdc++.h>
using namespace std;
int countBits(int x) { return __builtin_popcount(x); }
5
int bitAnd(int a, int b) { return a & b; }
int bitOr(int a, int b) { return a | b; }
int bitXor(int a, int b) { return a ^ b; }
int bitNot(int a) { return ~a; }
int LShift(int a, int k) { return a << k; }
int RShift(int a, int k) { return a >> k; }
14. One‑Page Revision Sheet
Operators
• & AND → both 1
• | OR → any 1
• ^ XOR → bits differ
• ~ NOT → flip bits
• << multiply by 2
• divide by 2
Key Checks
• Power of two → n & (n-1) == 0
• Count bits → __builtin_popcount(x)
Identities
• a+b = (a|b) + (a&b)
• a+b = (a^b) + 2(a&b)
End of Handbook