Ugenz Academy/Tutorial

Bitmanipulation

21 min read4,077 words

Reading progress

Keep learning

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 2 is set.
  • Turn bit 1 on.
  • Turn bit 3 off.
  • Toggle a bit.
  • Count the number of 1 bits.
  • 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:

OperatorNameMeaning
&ANDBoth bits must be 1
``OR
^XORBits must be different
~NOTInverts bits
<<Left ShiftShift bits left
>>Right ShiftShift 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 1 when 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 % 4Result
0n
11
2n + 1
30

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 mask and currently stand at node i.

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:

  1. Check odd/even
  2. Count set bits
  3. Check power of 2
  4. Find unique element
  5. Find two unique elements
  6. Missing number using XOR
  7. Reverse bits
  8. Count bits from 0 to n
  9. Single Number
  10. Subsets
  11. Maximum XOR
  12. XOR queries
  13. Bitmask DP
  14. Minimum XOR pair
  15. Sum without +
  16. Divide integers using bit operations
  17. Binary representation
  18. Lowest set bit
  19. 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

TaskExpression
Check oddn & 1
Get bit i(n >> i) & 1
Check bit in & (1 << i)
Set bit in |= (1 << i)
Clear bit in &= ~(1 << i)
Toggle bit in ^= (1 << i)
Remove lowest 1n &= n - 1
Lowest 1 bitn & -n
Power of 2n > 0 && (n & (n-1)) == 0
Count set bits__builtin_popcount(n)
2^i1 << i
Multiply by 2n << 1
Divide by 2*n >> 1
XOR cancellationx ^ x = 0
XOR identityx ^ 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.

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy