Bitwise Operations & Identities
Bitwise Operations manipulate individual bits of integers directly in O(1) CPU cycles using AND, OR, XOR, NOT, and shifts—powering low-level optimizations, masks, and power-of-two checks.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Bitwise Operations & Identities
Bitwise Operations act directly on the binary representation of integers in single CPU cycles ($O(1)$). Mastering a handful of identities unlocks fast set operations, Fenwick Trees (i & -i), power-of-two checks ((n & (n - 1)) == 0), and compact DP state representations.
Essential Cheat Sheet
| Expression | Meaning |
| :--- | :--- |
| (x >> i) & 1 | Test whether bit i is set |
| x \| (1 << i) | Set bit i to 1 |
| x & ~(1 << i) | Clear bit i to 0 |
| x ^ (1 << i) | Toggle (flip) bit i |
| x & (x - 1) | Clear the lowest set bit (also tests power of 2: x > 0 && (x & (x - 1)) == 0) |
| x & -x | Isolate the lowest set bit (Fenwick Tree jump!) |
---
Practice Problems
Easy
1. Power-of-Two, Isolate LSB & Clear LSB Toolkit
Implement fundamental $O(1)$ bitwise utility operations on 32-bit unsigned integers.
Approach: Use x & (x - 1) and x & -x in unsigned/two's-complement arithmetic. Time: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <cstdint>
#include <iostream>
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
int lowestSetBit(int n) { return n & -n; }
int clearLowestSetBit(int n) { return n & (n - 1); }
int main() {
std::cout << std::boolalpha << isPowerOfTwo(16) << " " << isPowerOfTwo(18) << " | "
<< lowestSetBit(12) << " " << clearLowestSetBit(12) << "\n"; // true false | 4 8
return 0;
}
</details>
---