BitsAlgorithmaka bit manipulation basics, get bit, update bit

Set, Clear, Toggle & Test a Bit

The four single-bit primitives: set with OR, clear with AND-NOT, toggle with XOR, test with AND on a shifted 1.

▶ VisualizePattern: Bit ManipulationPractice (3)
Progress

Overview

All single-bit manipulation is built from one mask, 1 << i, and one operator. Set bit i: x | (1 << i). Clear bit i: x & ~(1 << i). Toggle bit i: x ^ (1 << i). Test bit i: (x >> i) & 1 or (x & (1 << i)) != 0.

Two related primitives appear constantly: clear the lowest set bit with x & (x - 1) and isolate the lowest set bit with x & -x. Ranges follow the same shape: x & ((1 << k) - 1) keeps the low k bits; x | ((1 << k) - 1) sets them; x >> k << k clears them.

These operations power Bit Masks, Count Set Bits (Popcount), Fenwick Tree indexing (i & -i), and every "bit trick" that follows.

set bitclear bittoggle bittest bitO(1)

Intuition

A mental model before the formal terms.

A mask 1 << i is a stencil with a single hole at position i. OR paints through the hole (that bit becomes 1, everything else untouched). AND with the *inverted* stencil erases through the hole. XOR flips whatever is under the hole. AND with the stencil looks through the hole to see what is there.

How it works

  1. Build the mask m = 1 << i — a single 1 at position i, zeros elsewhere.
  2. Set: x | m. Every bit of x survives (b | 0 = b) except position i, forced to 1 (b | 1 = 1).
  3. Clear: x & ~m. ~m is all ones except a 0 at i; b & 1 = b keeps others, b & 0 = 0 clears i.
  4. Toggle: x ^ m. b ^ 0 = b, b ^ 1 = not b.
  5. Test: (x >> i) & 1 shifts the bit of interest to position 0 and masks everything else away.
  6. Lowest set bit: x - 1 flips the trailing zeros to ones and the lowest 1 to 0, so x & (x - 1) drops it; -x is ~x + 1, which agrees with x only at the lowest set bit, so x & -x isolates it.

Why it works

The identities b | 0 = b, b & 1 = b, b ^ 0 = b are what make each operator a no-op outside the mask, and b | 1 = 1, b & 0 = 0, b ^ 1 = ¬b are what make it act inside the mask. Because bit positions are independent there is no interaction between them.

For x & (x - 1): subtracting 1 borrows from the lowest set bit, turning it into 0 and every lower 0 into 1. Higher bits are unchanged, so ANDing keeps them and zeroes the lowest 1 and everything below (which was already 0).

Recognition

How to tell a problem wants this.

  • The problem mentions the "i-th bit", "flip bit", "binary representation", or asks to update a bit in place.
  • You are implementing a compact visited set, a permission system, or a flags field.
  • The phrase "rightmost set bit" or "lowest set bit" appears — it is x & -x.
“parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

n
0
7
0
6
1
5
0
4
1
3
1
2
0
1
0
0
= 44
1/7n = 44 (00101100). We want to manipulate bit k=1, which currently is 0.
Bit kBit set to 1Bit cleared to 0
PseudocodeLearn Set, Clear, Toggle & Test a Bit →
1mask = 1 << k
2set    = n | mask
3clear  = n & ~mask
4toggle = n ^ mask
5test   = (n >> k) & 1
Variables
n44
k1
Complexity
best O(1)
avg O(1)
worst O(1)
space O(1)
Speed

Pseudocode

1mask = 1 << i
2set(x, i)    = x | mask
3clear(x, i)  = x & ~mask
4toggle(x, i) = x ^ mask
5test(x, i)   = (x >> i) & 1
6lowest_set(x)     = x & -x
7drop_lowest(x)    = x & (x - 1)
8low_k_bits(x, k)  = x & ((1 << k) - 1)

Implementations

11 · Set, clear, toggle
2def set_bit(x: int, i: int) -> int:
3    return x | (1 << i)
4 
5 
6def clear_bit(x: int, i: int) -> int:
7    return x & ~(1 << i)
8 
9 
10def toggle_bit(x: int, i: int) -> int:
11    return x ^ (1 << i)
12 
13 
142 · Test and branch-free update
15def test_bit(x: int, i: int) -> bool:
16    return (x >> i) & 1 == 1
17 
18 
19def update_bit(x: int, i: int, value: bool) -> int:
20    return (x & ~(1 << i)) | (int(value) << i)
21 
22 
233 · Lowest-set-bit tricks
24def lowest_set_bit(x: int) -> int:
25    return x & -x
26 
27 
28def drop_lowest_set_bit(x: int) -> int:
29    return x & (x - 1)
30 
31 
32def low_k_bits(x: int, k: int) -> int:
33    return x & ((1 << k) - 1)      # any k works: ints are unbounded
34 
35 
364 · Demo
37if __name__ == "__main__":
38    x = 0b1010  # 10
39    assert set_bit(x, 0) == 0b1011
40    assert clear_bit(x, 1) == 0b1000
41    assert toggle_bit(x, 3) == 0b0010
42    assert test_bit(x, 1) and not test_bit(x, 0)
43    assert update_bit(x, 0, True) == 0b1011
44    assert lowest_set_bit(12) == 4        # 1100 -> 0100
45    assert drop_lowest_set_bit(12) == 8   # 1100 -> 1000
46    assert low_k_bits(0xFF, 4) == 0xF
Walkthrough
  1. Python ints are unbounded, so 1 << i works for any i, and ~(1 << i) has infinitely many leading ones — harmless for &.
  2. update_bit uses int(value) to turn the bool into 0/1 before shifting (a bool would shift too, since bool subclasses int).
  3. x & -x works for negative x too because Python negation is exact two's complement of infinite width.
  4. low_k_bits needs no guard; (1 << 100) - 1 is a legal 100-bit mask.
Complexity (this implementation)
time O(1) · space O(1)

O(number of digits) for huge ints; constant for values below 2^60.

Language notes
  • No bitset in the stdlib; ints as masks are the idiom. int.bit_length() gives the position of the highest set bit + 1.
  • Chained comparisons: (x >> i) & 1 == 1 binds as (x >> i) & (1 == 1) — here it happens to work because True == 1, but parenthesize for clarity.
  • Negative shift counts raise ValueError.
Common mistakes in this language
  • Printing ~x and expecting a bit pattern — it is a negative number; mask with (1 << w) - 1 first.
  • Relying on x & 1 == 0 for parity: it evaluates to x & False, which is 0, always falsy.
  • Emulating a fixed-width register and forgetting to mask after <<.
Language differences that matter here
  • Bit index range: C++ uint32_t needs 1u << i with i < 32 (UB otherwise); JS/TS 1 << i wraps i mod 32 and bit 31 produces a negative number; Python accepts any non-negative i.
  • Lowest set bit x & -x: Python and JS work directly on signed values; in C++ prefer unsigned types (x & (0u - x)) to avoid signed-negation UB on INT_MIN.
  • All-ones mask of k bits: C++/JS must guard k >= 32 (1 << 32 is UB in C++ and equals 1 in JS); Python (1 << k) - 1 always works.
  • Precedence trap x & 1 == 0 exists in all four languages; parenthesize (x & 1) == 0.

Complexity

Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(1)
Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
Avoid it when
  • When a plain boolean array is clearer and the universe is not tiny — bit-packing is an optimization, not a default.
  • When bit index may reach or exceed the word width; 1 << 40 is 256 in JavaScript and undefined in C++ with 32-bit int.

Alternatives

Bit MasksArray

Common mistakes

  • Clearing with x & (1 << i) instead of x & ~(1 << i) — the former isolates the bit.
  • Treating the result of x & (1 << i) as 0/1; compare with != 0 or shift first.
  • Zero-based vs one-based bit indexing; bit 0 is the least significant.
  • In Java, 1 << 31 on int is negative, and x >> 31 sign-extends; use 1L/>>> for a clean test.

Interview patterns

  • Set/clear a bit at a given position in a stream of updates (design questions with packed state).
  • Insert m into n at bits i..j: clear the range with a mask, then OR in m << i.
  • Position of the rightmost set bit: log2(x & -x), or count trailing zeros.
  • Alternating bits check: y = x ^ (x >> 1) has all ones iff x alternates; test with (y & (y + 1)) == 0.

Example problems

Single NumbereasyCounting BitseasyBit Counting Trickseasy