aloalgoBit Manipulation Summary
A quick reference for bitwise operations and problems to practice. Bit manipulation is the art of using binary representations and bitwise operators to solve problems with exceptional efficiency. At the hardware level, every number is stored as a sequence of bits, and bitwise operations work directly on these bits in constant time.While bit manipulation problems are less common than array or string problems in interviews, they do appear regularly and can often provide elegant O(1) space solutions to problems that would otherwise require extra data structures. Understanding how bits work also deepens your understanding of how computers represent and process data at the most fundamental level.Bitwise Operators
There are six core bitwise operators. Each operates on individual bits of integer values. Understanding what each operator does and when to use it is the foundation for all bit manipulation techniques.| Operator | Name | Use Case |
|---|---|---|
| & | AND | Check/clear bits, test if even |
| | | OR | Set bits |
| ^ | XOR | Toggle bits, find unique element |
| ~ | NOT | Flip all bits |
| << | Left Shift | Multiply by 2, create masks |
| >> | Right Shift | Divide by 2, extract bits |
Common Tricks
Most bit manipulation interview questions revolve around a handful of well-known tricks. These tricks combine the basic operators in clever ways to achieve results that would otherwise require loops or conditional logic.- n & (n-1): Clear lowest set bit, check power of 2. If n & (n-1) equals 0, then n has exactly one set bit and is a power of 2.
- n & (-n): Isolate lowest set bit. This gives you a number with only the rightmost set bit of n turned on.
- n & 1: Check if odd (1) or even (0). The least significant bit determines parity.
- a ^ a = 0: XOR same numbers cancel out. This is the basis for the "Single Number" problem where every element appears twice except one.
- a ^ 0 = a: XOR with 0 returns the number unchanged, which serves as the identity element for XOR.
- 1 << n: Create bit mask with 1 at position n. Useful for setting, clearing, or toggling specific bits.
When to Use Bit Manipulation
Bit manipulation is particularly useful in the following scenarios:- Finding unique elements: When all elements appear in pairs except one, XOR all elements together to find the unique one in O(n) time and O(1) space.
- Subset generation: Each bit position represents whether an element is included or excluded. Iterating from 0 to 2^n - 1 generates all possible subsets.
- Efficient multiplication and division: Left shift multiplies by 2, right shift divides by 2. These are faster than arithmetic operations in low-level code.
- Flag and state management: Use individual bits as boolean flags to track multiple states in a single integer, saving memory and enabling fast comparisons.
Chapters
- Bitwise Operators - The six operators and their uses
- Common Bit Tricks - XOR tricks, counting bits, and more
Practice Problems
Easy
Medium
Hard
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.