gamesblog

Bitwise

AND, OR, XOR, NOT, shifts, x AND (x − 1) and two's complement, worked bit by bit at a width that keeps growing.

  • Computing
  • Timed
  • Endless levels

How it plays

Two patterns and an operation, or one pattern and a shift, and you give the result at the width shown. Then x AND (x − 1), negative numbers in two's complement, and patterns read back as signed values. It starts at four bits and grows two at a time without end.

The wrong options are the mistakes people make: OR taken for XOR, NOT confused with negation, a shift the wrong way or one place too far, bits rotated round instead of dropped, an arithmetic shift where a logical one was asked, the +1 forgotten in two's complement.

The working names the rule — which columns survive, which bits fall off — and checks the result in decimal.

Keys

Space starts and skips ahead · 1–9 pick · Enter submits · Esc stops. On a phone, tap.

What it trains

This makes bit manipulation and two's complement quicker and surer to work by hand. It trains that, not reasoning in general.

Learn

How to get better at bitwise: the method, the techniques, what each new level asks of you, and the traps the wrong answers are made of.

Your approach to each question

  1. Read the operation word or symbol first — AND, OR, XOR, NOT, <<, >> — and the width in the question. The width is part of the answer: every result is exactly that many bits.
  2. Work in columns, not in decimal. Line the patterns up, and decide each column on its own from the rule. Past 8 bits the patterns come in groups of four; take one group at a time.
  3. For a shift, count the places first, then move the whole pattern: say which bits fall off and what fills the gap before you write anything.
  4. With options shown, compare them before you work it all out. They usually differ in a few columns — the ones where both bits are 1, or the ends of a shift. Decide those columns and you are done.

Techniques and tricks

  • One line for each operator

    AND: 1 only where both are 1. OR: 1 where either is 1. XOR: 1 where the two differ. Say the line for the operator before you start, every time.

    e.g. 1100 AND 1010 = 1000; 1100 OR 1010 = 1110; 1100 XOR 1010 = 0110

  • Settle the both-1 columns first

    Where both bits are 0, every operator gives 0. Where both are 1, AND and OR give 1 but XOR gives 0. Where they differ, OR and XOR give 1 but AND gives 0. So mark the both-1 columns first; they are where OR and XOR part ways.

  • NOT is all-ones minus x

    Flipping every bit is the same as subtracting from the all-ones pattern of that width, 2ⁿ − 1. Check a NOT by adding: x + NOT x is always all ones, never more.

    e.g. NOT 1011 in 4 bits = 0100; 15 − 11 = 4

  • Shifts drop off the end

    x << k moves everything k places left: the top k bits fall off and k zeros come in on the right. A logical x >> k drops the lowest k bits and fills the top with zeros. Nothing wraps round.

    e.g. 10110011 << 2 = 11001100; 10110011 >> 2 = 00101100

  • x AND (x − 1) clears the lowest 1

    Subtracting 1 turns the rightmost 1 into 0 and every 0 to its right into 1. ANDing with x keeps the rest of x and wipes that one bit. So find the rightmost 1, make it 0, and copy everything else.

    e.g. 10110100 → 10110000

  • Negate: copy to the first 1, flip the rest

    Two’s complement of −m is “flip every bit of m and add 1”. A faster way by eye: copy m from the right up to and including its first 1, then flip every bit to the left of that.

    e.g. −6 in 8 bits: 6 = 00000110 → 11111010; 256 − 6 = 250 = 11111010

  • The top bit is worth minus

    To read a signed pattern, give the top bit the value −2ⁿ⁻¹ and every other bit its usual value, then add. Or read it unsigned and subtract 2ⁿ. If the top bit is 0, the number means the same signed as unsigned.

    e.g. 11111010 in 8 bits: −128 + 122 = −6; or 250 − 256 = −6

As the levels climb

  • The operations unlock in this order: AND, OR, XOR; then NOT; then shifts; then x AND (x − 1); then two’s complement, both writing a negative number and reading a pattern back as signed. Each new kind joins the mix at the same rate as the old ones.
  • The width starts at 4 bits and grows by two bits at a time without end. Past 8 bits, work one group of four at a time and keep your place by the groups, not by counting single bits.
  • The clock is 6 seconds plus 0.9 for every bit, and closes in three steps to 55% of that. When it tightens, stop working every column: find the columns where the options differ and decide only those.
  • At wide two’s complement, the decimal gets large. Use the copy-to-the-first-1 rule rather than flip-then-add, which makes you carry the +1 along a long run of 1s.

Traps to avoid

  • OR taken for XOR, or the other way: they differ only where both bits are 1. OR gives 1 there; XOR gives 0.
  • NOT confused with negation: NOT just flips. Flip and add 1 is two’s complement negation, a different question. An option one more than your NOT is this mistake.
  • The shift the wrong way, one place too far, or rotated: bits shifted off the end are gone, not carried round to the other side. Count the zeros that came in — there must be exactly k of them.
  • An arithmetic shift where a logical one was asked: when the top bit is 1, an arithmetic >> copies 1s in at the top. This game asks for a logical shift, which always brings in zeros.
  • The +1 forgotten, or the sign bit just set: for −m, flipping alone gives one too little, and putting a 1 on top of m’s bits is sign-and-magnitude, not two’s complement. Check by adding the pattern to m: you must get 2ⁿ, all zeros once kept to the width.

How to practise

  • Use “Operations” to drill one kind at a time — “Two’s complement” on its own until negating is quick, or “x AND (x − 1)” until you see the lowest 1 at a glance.
  • Switch “Answer by” to “Typing it” to write every bit yourself. With options you can decide a few columns; typing makes you do the whole width.
  • Raise “Options shown” to 8 so that more of the near-misses — wrong direction, one place too far, rotated — are on screen together, and you have to know which is which.
  • Read the decimal check in the working after a miss. Seeing that a left shift doubled the number, or that a negative pattern minus 2ⁿ gives the value, is what makes the rules stick.

Levels

Each question has a clock that comes from the work it asks for. There is no last level: at least one dial turns without end. Your level is judged on your last ten answers, every ten: 90% moves you up, below 80% moves you down, which holds most people near four in five right.

All of it is in the settings beside Start — how many answers a judgement looks at and how often it recalibrates, the thresholds, the time, which questions, how many options, and whether you see each verdict at once or review them together at the judgement. You can also jump to any level.

More computing

All games →