Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ✅ 2. Useful Bitwise Tricks (Common in CP & DP)
- 📌 A. Set / Check / Clear a specific bit
- cpp
- Copy
- Edit
- int x = 5; // 0101 in binary
- // Set 2nd bit (0-indexed)
- x |= (1 << 2); // x becomes 0101 | 0100 = 1101 (13)
- // Check if 3rd bit is set
- bool isSet = x & (1 << 3); // true if bit 3 is set
- // Clear 0th bit
- x &= ~(1 << 0); // 1101 & ~(0001) = 1100 (12)
- 📌 B. Count number of set bits (popcount)
- cpp
- Copy
- Edit
- int x = 29; // Binary: 11101
- int count = __builtin_popcount(x); // count = 4 (set bits)
- 🚀 Useful for DP on subsets (e.g., TSP, bitmask problems)
- 📌 C. Iterate all subsets of a bitmask
- cpp
- Copy
- Edit
- int mask = 0b1011; // Subsets of 4-element set {0,1,3}
- for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
- // sub is a subset of mask
- }
- 📌 D. Toggle a bit
- cpp
- Copy
- Edit
- int x = 6; // 0110
- x ^= (1 << 1); // Toggle 1st bit: 0110 → 0100 (4)
- 📌 E. Check if a number is a power of 2
- cpp
- Copy
- Edit
- bool isPow2 = (x > 0) && ((x & (x - 1)) == 0);
- 📌 F. Lowest set bit
- cpp
- Copy
- Edit
- int x = 12; // 1100
- int lowBit = x & -x; // Gets 3rd bit (value 4)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
