ReviseAlgo Logo

Bit Manipulation

Common Bit Tricks

Master essential bit manipulation recipes: get, set, clear, toggle i-th bit, power of two checks, and Brian Kernighan's counting.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What are Common Bit Tricks?

Common Bit Tricks are standardized bitwise recipes that solve math, boolean flags, or search tasks in O(1) time and space. They bypass division, modulo, and array allocations by performing raw logic directly on register indices.

Why study them?

These tricks are standard building blocks for system optimization and coding rounds. Knowing how to count set bits, isolate the lowest set bit, or check properties like parity (odd/even) with simple bit masks is highly valued.

2. Mental Model: Bit Masks as Stencils

Imagine you want to paint a pattern of stars on a wall:

  • You use a cardboard sheet with a hole cut out at position i (a stencil).
  • Placing the sheet over the wall and spraying paint only colors the wall through that specific hole.
  • A Bit Mask acts as this stencil. By creating a mask 1 << i (which has a single 1 at index i and 0s elsewhere), we can read or write to only that specific index, leaving all other bits unchanged.

    • 3. Core Bitwise Tricks

    Here are the essential bitwise recipes:

    1. Basic Bit Queries & Edits (i-th Bit)

  • Get i-th Bit: (x >> i) & 1 (isolates and reads index i).
  • Set i-th Bit: x | (1 << i) (forces bit i to 1).
  • Clear i-th Bit: x & ~(1 << i) (forces bit i to 0).
  • Toggle i-th Bit: x ^ (1 << i) (flips bit i).

    • 2. Arithmetic & Property Tricks

  • Check Even/Odd: (x & 1) == 0 is even; (x & 1) == 1 is odd.
  • Power of Two Check: x > 0 && (x & (x - 1)) == 0 (returns true if only one bit is set).
  • Clear Lowest Set Bit: x & (x - 1) (flips the rightmost 1 to 0).
  • Isolate Lowest Set Bit: x & -x (keeps only the rightmost 1 set, zeroing others).

    • 4. Visualizing Brian Kernighan's Clearing

    How x & (x - 1) clears the rightmost set bit for x = 12 (binary 1100):

    This property is highly efficient because it lets us count set bits in O(K) time (where K is the number of actual 1s), rather than scanning all 32 bits.

    5. Real-World Examples

  • Bitmapped Chessboards: Storing piece positions on a 8 × 8 grid inside a 64-bit integer, checking move overlaps in a single CPU instruction.
  • Embedded Flag Controls: Managing read, write, execute permissions (rwx) via bits 4 (read), 2 (write), and 1 (execute).

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test trick applications:
  • "Given an integer, count the number of set bits." -> Explain Brian Kernighan's algorithm. Show how x & (x - 1) clears the rightmost set bit, which runs in O(K) time, outperforming a linear 32-bit shift loop.
  • "How do you check if a number is a power of two without loops?" -> Explain that powers of two have exactly one bit set. Therefore, subtraction flips that bit and sets all trailing bits to 1 (e.g. 8 = 1000, 7 = 0111), so x & (x - 1) yields 0.

    • Common Mistakes

    Warning: 1. Neglecting negative checks for powers of two: Evaluating isPowerOfTwo(0) as true. Always check x > 0 first.
    > 2. Parentheses omission: Writing x & x - 1 == 0. Due to compiler precedence, subtraction - and equality == run before bitwise &, parsing this as x & ((x - 1) == 0). Always wrap operations: (x & (x - 1)) == 0.

    7. Summary

  • Get: (x >> i) & 1. Set: x | (1 << i).
  • Clear: x & ~(1 << i). Toggle: x ^ (1 << i).
  • Power of Two: x > 0 && (x & (x - 1)) == 0.
  • Set Bit Count: Loop x = x & (x - 1) to count sets.

    • 8. Quiz

    Question 1: What is the result of x & -x when x = 12 (binary 1100)? Answer: 4 (binary 0100). This operation isolates and returns the lowest set bit.
    Question 2: Why does x & 1 check for odd numbers? Answer: In binary representation, all columns representing indices ≥ 1 are powers of two (2, 4, 8, etc.), which are even. Only the 0-th column (value 2^0 = 1) represents an odd value, so a number is odd if and only if its 0-th bit is 1.
    Question 3: If x = 7 (0111) and we toggle bit 1 (toggleBit(x, 1)), what is the new value? Answer: 5 (binary 0101). Toggling flips the second bit from 1 to 0.
    Question 4: True or False: In Java, Integer.bitCount(n) uses Brian Kernighan's algorithm. Answer: False. It uses a parallel bit counting algorithm (divide-and-conquer masking), which runs in constant O(1) operations on all integers, bypassing loops.
    Question 5: What does x & ~(x - 1) yield? Answer: It isolates and returns the rightmost set bit, which is equivalent to x & -x.