Free Math and bits lessonsMath and bits · Stage 3 · Bit tricks · Step 2

Set, clear, flip

Change single bits of a number with masks. About 9 minutes.

A mask points at one bit

A mask is a number with only the bit you care about switched on, like a stencil with a single hole. Shifting 1 left by k places gives a 1 followed by k zeros, so exactly bit k is on.

Combine the number with the stencil: OR switches that bit on, AND with the flipped stencil switches it off, and XOR flips it. Every other bit is left alone.

OR with the mask: sets the bit.

AND with the flipped mask: clears it.

XOR with the mask: toggles it.

In code

mask = 1 << k
n | mask      # set bit k
n & ~mask     # clear bit k
n ^ mask      # toggle bit k

n = 0, ops = [set 3, toggle 0, clear 3]

bit 3bit 2bit 1bit 0

mask

n: 8

set 3: mask = 1 << 3 = 1000. n | mask turns bit 3 on. n = 8.

Move 1 of 3

Bits as switches

Real programs pack many on/off flags into one number this way: file permissions, which items are chosen, which cells are visited. A single 32-bit number holds 32 switches in just four bytes.

You will use exactly this idea in the next step to stand for subsets.

Setting twice: is the same as setting once.

In code

for op in ops:
    word, k = op.split()
    mask = 1 << int(k)
    if word == "set":
        n |= mask
    elif word == "clear":
        n &= ~mask
    else:
        n ^= mask
return n

Quick check

n = 5 (101). What is n after toggling bit 1?

Show the answer

7. Bit 1 was 0; ^ 2 turns it on: 111 = 7.

Your problem

Apply bit operations

Start with n and apply each operation in order. Each is "set k", "clear k" or "toggle k", acting on bit k (bit 0 is the lowest). Return the final number.

Example

n = 0, ops = ["set 3", "toggle 0", "clear 3"] → 1

0 ≤ n ≤ 2^30 · 0 ≤ ops ≤ 1,000 · 0 ≤ k ≤ 29

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.