AntInLoop

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>

---

Related Algorithms