DSA Bit Manipulation
What is Bit Manipulation?
Bit Manipulation refers to directly working with the individual bits of binary numbers. Instead of handling numbers as a whole, it treats them as a sequence of 0s and 1s, allowing highly efficient operations at the bit level.
This approach is very useful in low-level programming, performance-critical applications, and solving problems where direct control over bits speeds up computation.
Why Use Bit Manipulation?
- Works at the smallest unit of data, the bit.
- Enables faster arithmetic and logical operations.
- Saves memory by packing data tightly.
- Simplifies certain algorithms involving sets, flags, and masks.
Bits and Binary
A number in a computer is stored as a series of bits (binary digits), each either 0 or 1. For example:
- Decimal 5 in binary is 0101 (4 bits).
- Decimal 10 in binary is 1010.
Bit manipulation changes or queries these bits directly.
Common Bitwise Operators
| Operator | Symbol | What It Does | Example |
|---|---|---|---|
| AND | & | Sets each bit to 1 if both bits are 1 | 5 & 3 = 1 (0101 & 0011) |
| OR | ` | ` | Sets each bit to 1 if one bit is 1 |
| XOR | ^ | Sets each bit to 1 if bits differ | 5 ^ 3 = 6 (0101 ^ 0011) |
| NOT | ~ | Inverts all bits | ~5 = -6 (depends on system) |
| Left Shift | << | Shifts bits left, adding zeros on right | 5 << 1 = 10 (0101 << 1) |
| Right Shift | >> | Shifts bits right, dropping bits on right | 5 >> 1 = 2 (0101 >> 1) |
Practical Uses
- Checking if a number is even or odd: Check the least significant bit using num & 1.
- Setting a bit: Use OR with a mask like num | (1 << position).
- Clearing a bit: Use AND with the inverse mask: num & ~(1 << position).
- Toggling a bit: Use XOR: num ^ (1 << position).
- Counting bits set to 1: Efficiently find how many bits are ‘on’.
- Swapping values without temporary variable: Using XOR trick.
- Fast multiplication or division by powers of two: Using left or right shifts.
Example: Check if a Number is a Power of Two
A number is a power of two if it has exactly one bit set to 1.
Code Idea: num & (num - 1) == 0 means the number is a power of two.
Simple Example: Turning On the 3rd Bit
Suppose you want to set the 3rd bit (counting from 0) of number 5 (binary 0101).
- Create mask: 1 << 3 → 1000 (decimal 8)
- Apply OR: 5 | 8 = 13 (0101 | 1000 = 1101)
So, the number becomes 13.
Real-Life Analogy
Think of bits as light switches (ON=1, OFF=0). Bit manipulation lets you flip switches, check if they're ON, or turn off specific switches without disturbing others.
Efficiency
Bitwise operations are typically one CPU instruction, making them extremely fast compared to arithmetic or looping logic.
Summary of Benefits
- Minimizes time by working directly with bits.
- Simplifies complex logic involving sets and flags.
- Ideal for embedded systems, cryptography, graphics, and compression algorithms.
Prefer Learning by Watching?
Watch these YouTube tutorials to understand DATA STRUCTURES ALGORITHMS Tutorial visually:
What You'll Learn:
- 📌 Algorithms: Bit Manipulation
- 📌 Introduction To Bit Manipulation In DSA | FREE DSA Course in JAVA | Lecture 14