Bit Manipulation
Bit Manipulation means working directly with the individual bits of a number using bitwise operators.
It is an important DSA topic because bit operations are extremely fast and are used in:
- Competitive programming
- System programming
- Cryptography
- Networking
- Operating systems
- Embedded/IoT systems
- Memory optimization
- Flags and permissions
- Bitmask DP
1. What is a Bit?
A computer ultimately represents data using binary.
A bit can have only two values:
0 or 1
For example, decimal 13 is:
13 = 1101₂
Because:
1 × 8 = 8 1 × 4 = 4 0 × 2 = 0 1 × 1 = 1 8 + 4 + 0 + 1 = 13
So:
Decimal Binary 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 10 1010 11 1011 12 1100 13 1101 14 1110 15 1111
2. Why Do We Need Bit Manipulation?
Normally, you might write:
int x = 13;
and work with the entire number.
Bit manipulation allows you to work with individual bits:
13 = 1101 ↑ ↑ ↑ ↑ 3 2 1 0
For example:
- Check whether bit
2is set. - Turn bit
1on. - Turn bit
3off. - Toggle a bit.
- Count the number of
1bits. - Check whether a number is a power of 2.
- Generate subsets using bitmasks.
3. Bit Positions
Bit positions start from 0 on the right.
For:
13 = 1101
we have:
Bit position: 3 2 1 0 ↓ ↓ ↓ ↓ 1 1 0 1
Therefore:
bit 0 = 1 bit 1 = 0 bit 2 = 1 bit 3 = 1
4. Bitwise Operators
C++ provides these important bitwise operators:
| Operator | Name | Meaning |
|---|---|---|
& | AND | Both bits must be 1 |
| ` | ` | OR |
^ | XOR | Bits must be different |
~ | NOT | Inverts bits |
<< | Left Shift | Shift bits left |
>> | Right Shift | Shift bits right |
These are the foundation of bit manipulation.
5. Bitwise AND &
AND follows:
0 & 0 = 0 0 & 1 = 0 1 & 0 = 0 1 & 1 = 1
So both bits must be 1.
Example:
5 = 0101 3 = 0011 ---- & 0001
Therefore:
cout << (5 & 3);
Output:
1
6. Bitwise OR |
OR follows:
0 | 0 = 0 0 | 1 = 1 1 | 0 = 1 1 | 1 = 1
Example:
5 = 0101 3 = 0011 ---- | 0111
0111 = 7
Therefore:
cout << (5 | 3);
Output:
7
7. Bitwise XOR ^
XOR means:
Result is
1when the two bits are different.
0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0
Example:
5 = 0101 3 = 0011 ---- ^ 0110
0110 = 6
cout << (5 ^ 3);
Output:
6
8. Important XOR Properties
XOR has several extremely useful properties.
Property 1
a ^ 0 = a
Example:
5 ^ 0 = 5
Property 2
a ^ a = 0
Example:
5 ^ 5 = 0
Property 3
XOR is reversible:
a ^ b ^ b = a
Because:
b ^ b = 0 a ^ 0 = a
These properties are heavily used in DSA problems.
9. Bitwise NOT ~
NOT flips every bit:
0 → 1 1 → 0
For example, conceptually:
5 = 00000101 ~5 = 11111010
But there is an important point:
C++ int is typically a signed fixed-width integer, so ~5 is interpreted using two's complement representation.
For a typical 32-bit signed int:
~5
produces:
-6
A useful identity is:
~x = -(x + 1)
for signed integers using two's complement.
10. Left Shift <<
Left shift moves bits toward the left.
Example:
5 = 0101
Shift left by 1:
0101 << 1 = 1010
1010 = 10
So:
cout << (5 << 1);
Output:
10
For nonnegative values where no significant bits are lost:
x << 1 ≈ x × 2
Similarly:
x << 2 ≈ x × 4
Example:
3 << 3
means:
3 × 2³ = 3 × 8 = 24
11. Right Shift >>
Right shift moves bits toward the right.
Example:
20 = 10100
Shift right by 1:
10100 >> 1 = 01010
01010 = 10
So:
cout << (20 >> 1);
Output:
10
For nonnegative integers:
x >> 1 ≈ x / 2
and:
x >> 2 ≈ x / 4
12. Important Operator Precedence Warning
Bitwise operators have lower precedence than comparison operators in C++.
So when writing expressions like:
if (x & 1 == 1)
don't rely on precedence.
Use parentheses:
if ((x & 1) == 1)
This is much safer and clearer.
13. Check Whether a Number is Odd or Even
This is one of the simplest and most useful bit tricks.
Look at the least significant bit.
Even numbers → last bit 0 Odd numbers → last bit 1
Examples:
2 = 0010 4 = 0100 6 = 0110 8 = 1000
All end in 0.
Odd:
1 = 0001 3 = 0011 5 = 0101 7 = 0111
All end in 1.
Therefore:
if (n & 1) cout << "Odd"; else cout << "Even";
14. Get the i-th Bit
Suppose:
n = 13 13 = 1101
We want bit position 2.
Create a mask:
1 << 2
which gives:
0100
Then:
1101 0100 ---- 0100
So bit 2 is set.
C++:
int bit = (n >> i) & 1;
For example:
int n = 13; int i = 2; cout << ((n >> i) & 1);
Output:
1
15. Another Way to Check a Bit
You can use:
if (n & (1 << i))
Example:
int n = 13; int i = 2; if (n & (1 << i)) cout << "Bit is set"; else cout << "Bit is not set";
16. Set a Bit
Set means change a bit to 1.
Suppose:
n = 9 9 = 1001
Set bit 1.
Create:
1 << 1 = 0010
OR:
1001 0010 ---- 1011
1011 = 11
C++:
n = n | (1 << i);
or:
n |= (1 << i);
Example:
int n = 9; n |= (1 << 1); cout << n;
Output:
11
17. Clear a Bit
Clear means change a bit to 0.
Suppose:
n = 13 1101
Clear bit 2.
Mask:
1 << 2 = 0100
Invert mask:
~0100
Then:
n &= ~(1 << i);
Example:
int n = 13; n &= ~(1 << 2); cout << n;
Output:
9
Because:
1101 ↓ clear bit 2 1001
18. Toggle a Bit
Toggle means:
0 → 1 1 → 0
XOR is perfect for this.
Use:
n ^= (1 << i);
Example:
n = 13 1101
Toggle bit 1:
0010
XOR:
1101 0010 ---- 1111
Result:
15
19. Bit Operations Summary
For bit position i:
Check
(n >> i) & 1
Set
n |= (1 << i);
Clear
n &= ~(1 << i);
Toggle
n ^= (1 << i);
This is one of the most important things to memorize.
20. Remove the Lowest Set Bit
This is a famous bit trick:
n = n & (n - 1);
or:
n &= (n - 1);
It removes the rightmost 1 bit.
Example:
n = 12 12 = 1100 11 = 1011
AND:
1100 1011 ---- 1000
So:
1100 → 1000
The lowest set bit was removed.
21. Count Set Bits
A set bit is a bit equal to 1.
Example:
13 = 1101
Number of set bits:
3
Method 1 — Check Every Bit
int countBits(int n) { int count = 0; while (n > 0) { if (n & 1) count++; n >>= 1; } return count; }
Complexity:
O(log n)
for the number of bits processed.
22. Better Method: Brian Kernighan's Algorithm
Use:
n &= (n - 1);
Every operation removes one set bit.
int countBits(int n) { int count = 0; while (n != 0) { n &= (n - 1); count++; } return count; }
If a number has only a few set bits, this can be much faster than checking every bit.
Complexity:
O(number of set bits)
23. C++ Built-in Functions
C++ provides useful bit-counting functions.
For unsigned int:
__builtin_popcount(x)
Example:
int x = 13; cout << __builtin_popcount(x);
Output:
3
For long long:
__builtin_popcountll(x);
Modern C++ also provides standard <bit> facilities such as:
std::popcount(x)
when using an appropriate C++ standard version.
24. Check if a Number is a Power of 2
Powers of two have exactly one set bit.
1 = 0001 2 = 0010 4 = 0100 8 = 1000 16 = 10000
Therefore:
n > 0 && (n & (n - 1)) == 0
Example:
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
Why?
For:
8 = 1000 7 = 0111
AND:
1000 0111 ---- 0000
But for:
10 = 1010 9 = 1001
AND:
1010 1001 ---- 1000
Not zero.
25. Find the Lowest Set Bit
Suppose:
n = 12 1100
The lowest set bit is:
0100
A famous expression is:
n & -n
Example:
12 = 1100 -12 = 0100 (in the relevant fixed-width two's complement representation)
Therefore:
1100 0100 ---- 0100
Result:
4
This is very useful in advanced bit algorithms, including Fenwick Trees.
26. XOR and Finding a Unique Number
Suppose every number appears twice except one:
[2, 3, 4, 2, 4]
Find the unique number.
Use XOR:
2 ^ 3 ^ 4 ^ 2 ^ 4
Because:
2 ^ 2 = 0 4 ^ 4 = 0 0 ^ 3 = 3
Answer:
3
C++:
int uniqueNumber(vector<int>& arr) { int result = 0; for (int x : arr) { result ^= x; } return result; }
Complexity:
Time = O(n) Space = O(1)
This is one of the most famous XOR interview problems.
27. XOR Swap
There is a classic XOR trick:
a ^= b; b ^= a; a ^= b;
It swaps two integers without a temporary variable.
However, in modern C++, a normal temporary variable or std::swap is usually clearer and preferable:
swap(a, b);
So understand XOR swap as a bit-manipulation technique, but don't use it just to look clever.
28. XOR From 1 to N
There is a useful pattern for:
1 ^ 2 ^ 3 ^ ... ^ n
The result depends on n % 4.
n % 4 | Result |
|---|---|
| 0 | n |
| 1 | 1 |
| 2 | n + 1 |
| 3 | 0 |
Example:
n = 7 7 % 4 = 3
Therefore:
1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 = 0
This can turn an O(n) calculation into O(1).
29. Bitmask
A bitmask is a number whose bits represent a collection of Boolean states.
For example, suppose:
0 = not selected 1 = selected
For 4 items:
1010
means:
item 3 → selected item 2 → not selected item 1 → selected item 0 → not selected
So the mask represents:
{item 1, item 3}
This is extremely important for subset problems.
30. Generate All Subsets Using Bitmask
Suppose:
arr = [10, 20, 30]
There are:
2³ = 8
possible subsets.
Why?
Every element has two choices:
Take Don't take
So:
2 × 2 × 2 = 8
Masks from:
000
to:
111
represent all subsets.
C++ Code
#include <iostream> #include <vector> using namespace std; int main() { vector<int> arr = {10, 20, 30}; int n = arr.size(); for (int mask = 0; mask < (1 << n); mask++) { cout << "{ "; for (int i = 0; i < n; i++) { if (mask & (1 << i)) { cout << arr[i] << " "; } } cout << "}\n"; } return 0; }
Possible output:
{ } { 10 } { 20 } { 10 20 } { 30 } { 10 30 } { 20 30 } { 10 20 30 }
This is the connection between bit manipulation and subset generation.
31. Why 1 << n Represents 2ⁿ
Suppose:
1 << 3
Binary:
0001
Shift left three times:
1000
which is:
8
Therefore:
1 << n = 2ⁿ
For example:
1 << 5 = 32
This is used constantly in bitmask problems.
32. Bitmask Representation
Suppose we have:
People: 0 = A 1 = B 2 = C 3 = D
Mask:
1011
means:
D → 1 → selected C → 0 → not selected B → 1 → selected A → 1 → selected
So selected:
A, B, D
This allows us to represent an entire set using a single integer.
33. Subset Enumeration Complexity
For n elements:
Number of subsets:
2ⁿ
If we inspect all n elements for each subset:
O(n × 2ⁿ)
This is useful when n is relatively small.
For example:
n = 20 2²⁰ ≈ 1 million
which can be practical depending on the problem.
But:
n = 50
gives:
2⁵⁰
which is enormous.
34. Bitwise AND for Common Properties
Bitwise operations are often useful for checking properties across numbers.
For example, to determine whether a number is odd:
n & 1
To clear its lowest set bit:
n & (n - 1)
To extract its lowest set bit:
n & -n
These small expressions appear frequently in DSA.
35. Signed vs Unsigned Integers
This is important.
C++ has:
int unsigned int long long unsigned long long
Bit operations are easiest to reason about with unsigned integers because their bit representation doesn't involve negative signed values.
For example:
unsigned int x = 5;
When working with shifts, be especially careful with signed negative numbers.
For right shift:
- Right shifting an unsigned integer is a logical shift.
- Right shifting a negative signed integer is implementation-defined in C++; modern implementations commonly perform an arithmetic shift, but don't rely on this blindly.
For DSA bit tricks, using nonnegative values or unsigned types where appropriate makes reasoning safer.
36. Common Bit Tricks
These are worth remembering:
Check odd
n & 1
Multiply by 2
n << 1
for values where the operation is valid.
Divide by 2
n >> 1
for nonnegative integers.
Check bit i
n & (1 << i)
Set bit i
n |= (1 << i)
Clear bit i
n &= ~(1 << i)
Toggle bit i
n ^= (1 << i)
Remove lowest set bit
n &= (n - 1)
Get lowest set bit
n & -n
Check power of 2
n > 0 && (n & (n - 1)) == 0
Count set bits
__builtin_popcount(n)
or modern standard C++:
std::popcount(n)
37. Bit Manipulation and DSA
Bit manipulation connects to many other topics you've already studied.
Arrays
Use bits to represent selected elements.
Strings
Character operations and encoding can involve bits.
Hashing
Bitwise operations can be used in hash functions and bitsets.
Graphs
Bitmasks can represent visited nodes or subsets for small graphs.
Dynamic Programming
Bitmask DP is a major advanced DP technique.
Example:
dp[mask][i]
can represent:
We have visited the nodes represented by
maskand currently stand at nodei.
Greedy
Bit tricks can help optimize certain greedy algorithms.
Trees
Fenwick Trees use:
i & -i
to isolate the lowest set bit.
38. Bitset
C++ provides:
bitset
for storing a fixed number of bits.
Example:
#include <bitset> #include <iostream> using namespace std; int main() { bitset<8> bits(13); cout << bits << endl; return 0; }
Output:
00001101
You can manipulate individual bits:
bits.set(2); bits.reset(1); bits.flip(0);
Useful operations:
bits.count(); bits.any(); bits.none(); bits.all();
39. Real-Life Applications
Bit manipulation isn't just a competitive-programming trick.
Permissions
For example:
Read = 001 Write = 010 Execute = 100
A user's permissions can be represented as:
111
meaning all three permissions are enabled.
Network flags
Different bits can represent different options.
00000101
could represent multiple enabled features.
Embedded Systems / IoT
Since you're also working with ESP32 and Arduino, bit manipulation is especially relevant.
Microcontrollers often control individual hardware registers and pins using bits.
Conceptually:
PORT |= (1 << pin);
can set a particular bit.
And:
PORT &= ~(1 << pin);
can clear it.
This allows multiple hardware states to be stored efficiently.
40. Common Interview Problems
Important problems involving bit manipulation include:
- Check odd/even
- Count set bits
- Check power of 2
- Find unique element
- Find two unique elements
- Missing number using XOR
- Reverse bits
- Count bits from
0ton - Single Number
- Subsets
- Maximum XOR
- XOR queries
- Bitmask DP
- Minimum XOR pair
- Sum without
+ - Divide integers using bit operations
- Binary representation
- Lowest set bit
- Highest set bit
41. Example: Missing Number Using XOR
Suppose:
[0, 1, 3, 4]
Numbers should be:
0, 1, 2, 3, 4
Missing:
2
Use:
int missingNumber(vector<int>& nums) { int n = nums.size(); int result = n; for (int i = 0; i < n; i++) { result ^= i; result ^= nums[i]; } return result; }
Why does it work?
Everything appearing twice cancels:
x ^ x = 0
Only the missing number remains.
Complexity:
Time = O(n) Space = O(1)
42. Example: Two Unique Numbers
Suppose:
[1, 2, 1, 3, 2, 5]
Unique numbers:
3 and 5
First XOR everything:
1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
Duplicates cancel:
3 ^ 5
We now know:
3 ^ 5
But we need to separate them.
The XOR result has at least one bit where 3 and 5 differ.
We can isolate a differing bit using:
int diff = xorAll & -xorAll;
Then divide numbers into two groups based on that bit.
This is a classic advanced XOR technique.
43. Important Warning About Overflow
Bit shifting can cause problems if you shift into or beyond the limits of the type.
For example:
1 << 31
with a signed 32-bit int is problematic.
For bit masks involving larger positions, use appropriate unsigned or wider types:
1LL << i
For example:
long long mask = 1LL << 40;
This is a common competitive-programming pattern.
44. How to Approach Bit Manipulation Problems
When you see a bit problem, ask:
Question 1
Can I represent the information using bits?
Question 2
Is XOR useful?
Look for:
pairs duplicates unique element missing element
Question 3
Do I need to manipulate one specific bit?
Use:
1 << i
Question 4
Do I need subsets?
Think:
mask
Question 5
Do I need to count selected items?
Think:
popcount
Question 6
Do I need the lowest set bit?
Think:
n & -n
Question 7
Do I need to remove the lowest set bit?
Think:
n & (n - 1)
45. Bit Manipulation Cheat Sheet
| Task | Expression |
|---|---|
| Check odd | n & 1 |
Get bit i | (n >> i) & 1 |
Check bit i | n & (1 << i) |
Set bit i | n |= (1 << i) |
Clear bit i | n &= ~(1 << i) |
Toggle bit i | n ^= (1 << i) |
Remove lowest 1 | n &= n - 1 |
Lowest 1 bit | n & -n |
| Power of 2 | n > 0 && (n & (n-1)) == 0 |
| Count set bits | __builtin_popcount(n) |
2^i | 1 << i |
| Multiply by 2 | n << 1 |
| Divide by 2* | n >> 1 |
| XOR cancellation | x ^ x = 0 |
| XOR identity | x ^ 0 = x |
*For nonnegative integers, under the usual conditions.
46. Big Picture
You can now connect the major DSA techniques you've studied:
DSA │ ┌────────────┼────────────┐ │ │ │ Data Algorithms Techniques Structures │ Arrays Linked List Stack Queue Tree Graph Heap Trie │ └──────────────┐ ↓ Problem Solving │ ┌───────────────┼────────────────┐ ↓ ↓ ↓ Greedy Divide & Conquer DP │ │ │ └───────────────┼────────────────┘ ↓ Bit Manipulation │ ↓ Bitmask / DP
Final Summary
Bit Manipulation = directly operating on the binary representation of numbers.
The six fundamental operators are:
& AND | OR ^ XOR ~ NOT << Left Shift >> Right Shift
The most important techniques to remember are:
// Check bit (n >> i) & 1 // Set bit n |= (1 << i); // Clear bit n &= ~(1 << i); // Toggle bit n ^= (1 << i); // Remove lowest set bit n &= (n - 1); // Get lowest set bit n & -n // Check power of 2 n > 0 && (n & (n - 1)) == 0 // Count set bits __builtin_popcount(n)
And the most important conceptual connection is:
Bits → Bitmasks → Subsets → Bitmask DP
That connection becomes especially important when you reach Advanced Data Structures and more advanced Problem Solving.