Bit Manipulation

    DSA · Intermediate

    Definition

    Bit manipulation uses operators like AND, OR, XOR and shifts to work directly on binary representations.

    Gives elegant O(1) tricks and is common in interviews.

    Diagram

    5 = 1013 = 0115 ^ 3 = 110 = 6

    Flowchart

    Write number in binaryPick operator (& | ^ << >>)Apply maskRead result

    Example: Find the single number

    nums = [4, 1, 2, 1, 2]
ans = 0
for n in nums:
    ans ^= n
print(ans)

    Output: 4

    Complexity

    O(1) per operation

    Key points

    • x & (x−1) clears lowest set bit
    • x ^ x = 0
    • x << k multiplies by 2^k

    Interview questions

    Check power of two?

    x > 0 and x & (x − 1) == 0.

    Count set bits?

    Repeat x &= x − 1 and count iterations.

    More DSA topics

    ArraysLinked ListStackQueue