Algorithms · 11 min

Bit tricks and bitmasks

Store “which cities have I visited?” as one number, and the shortest round trip through 20 stops drops from years of work to under a second.

A delivery driver starts in Tokyo. Today she drops parcels in Osaka, Kyoto, Nagoya and Fukuoka, then drives home. Which order gives the shortest drive?

Here is the challenge: write a program that finds the truly shortest loop, not a good guess, for a driver with 20 stops. It must answer on a laptop before she has finished her coffee.

By the end of this page you will have solved it, and the key will be one ordinary integer used as a set.

Why trying every order runs out of time

With 4 stops after Tokyo, the first stop can be any of 4 cities, the next any of the 3 left, then 2, then 1. That is 4 × 3 × 2 × 1 = 24 orders. A computer checks 24 in no time.

This count is called a factorial, written 4! (“4 factorial”). Each extra stop multiplies it by the new number of stops.

So listing orders is hopeless. The way out comes from noticing that most of those orders repeat work.

The clue: half a route forgets its own order

Freeze the driver mid-route. She has visited Tokyo, Osaka and Nagoya, and she is now standing in Kyoto. There are two ways she could have got here:

What is left of her trip is the same in both cases: visit Fukuoka, then go home. The rest of the route doesn’t care which order she used so far. It only cares about two things: which cities are done, and where she is now.

So the 640 km version can never be part of the best loop. Throw it away and keep only 440.

That gives a new plan. Instead of listing orders, keep a table. Each slot is one pair (cities visited so far, city she is in now), and holds the shortest distance to reach that situation. Many orders land on the same slot, and only the best survives.

One practical question is left: the table needs a key for “Tokyo, Osaka, Nagoya and Kyoto, visited”. A string key like "Kyoto,Nagoya,Osaka,Tokyo" works, but every lookup must sort the names, build the string and hash it. With 20 cities that runs hundreds of millions of times. Bits turn the set into a plain number, and a number can index an array directly.

A set of cities written as one number

Give each city a position: Tokyo 0, Osaka 1, Kyoto 2, Nagoya 3, Fukuoka 4. Now write a row of 5 digits, each 0 or 1. A 1 in position i means “city i is visited”. Positions count from the right.

Read 01101 as a binary number: 8 + 4 + 1 = 13. So the number 13 means “Tokyo, Kyoto and Nagoya are visited, nobody else”. Every set of these 5 cities is a different number from 0 (00000, nothing) to 31 (11111, everything).

Because the set is a number, it can be an array index. best[13][2] is “visited {Tokyo, Kyoto, Nagoya}, standing in Kyoto”. No hashing, no string building.

Five operators, shown in binary

Five operators do all the work: <<, &, |, ~ and ^. Each works on every bit position at once. Our running set is 01101 (13).

<< shifts bits left. 1 << 3 takes 00001 and moves the 1 three places: 01000, which is 8. That is “just Nagoya”. In general, 1 << i is the set holding only city i.

& (AND) gives 1 only where both numbers have a 1. Use it to test a city. Has she been to Osaka?

  01101   visited (13)
& 00010   1 << 1, just Osaka
= 00000   0: Osaka not visited

| (OR) gives 1 where either number has a 1. Use it to add a city. She drives to Osaka:

  01101   visited (13)
| 00010   1 << 1, just Osaka
= 01111   15: Tokyo, Osaka, Kyoto, Nagoya

~ (NOT) flips every bit of one number. Combined with &, it removes a city. To take Nagoya out of 01111, flip “just Nagoya” and AND:

~ 01000   1 << 3, just Nagoya
= 10111   everyone except Nagoya

  01111   visited (15)
& 10111
= 00111   7: Tokyo, Osaka, Kyoto

^ (XOR) gives 1 where the two bits differ. You will see it in the demo. So visited ^ (1 << i) flips city i: on if it was off, off if it was on.

Filling the table one slot at a time

Now combine the clue and the bits. The table is best[visited][here]. It starts with one known slot: best[1][0] = 0. Set 1 is 00001, city 0 is Tokyo: “only Tokyo done, standing in Tokyo, 0 km”.

From every filled slot, try driving to each city not yet visited:

1. Skip city k if visited & (1 << k) is not 0. She has been there.
2. The new set is visited | (1 << k), and she now stands in k.
3. The new distance is best[visited][here] plus the leg from here to k.
4. If that beats what the new slot holds, write it in. Otherwise drop it, like the 640 km route.

A slot can only be filled from sets with one city fewer. The demo fills rows by size: every 2-city set, then every 3-city set, and so on. That way each slot is final before anything reads it.

When the table is full, look at the row 11111. For each possible last city, add the drive home to Tokyo. The smallest total is the answer.

One warning before you open the demo: box 1 shows the operators on a ramen order instead of cities, with 8 bits for 8 toppings. Same trick, different set.

The table ended with 33 filled slots and 52 “extend by one city” checks. Every set that includes Tokyo is a row, and a slot only exists if she could be standing in that city.

Is this actually faster?

Count the work for n cities. There are 2^n possible sets (each city is in or out: 2 × 2 × … × 2). For each set there are n cities she could be standing in, and from each she tries up to n next cities. That is about 2^n × n × n steps, written 2^n × n² for short.

For 5 cities: 2^5 × 5 × 5 = 32 × 25 = 800 as an upper bound. The demo actually needed 52, because most slots are impossible.

This method is called Held–Karp, after the two researchers who published it in 1962. Filling a table with answers to smaller problems and reusing them is called dynamic programming. When the table is indexed by a set stored as bits, it is bitmask dynamic programming.

The whole solver

Here it is in pseudocode. It walks sets in plain number order, 1, 2, 3 … 31, not by size like the demo. That still works: removing a city turns a bit off, so every smaller set is a smaller number and is already done. Look for 1 << k to make “just city k”, & to test it, | to add it.

n = number of cities                  # Tokyo is city 0
best[visited][here] = infinity for every slot
best[1][0] = 0                        # 00001: only Tokyo, standing in Tokyo

for visited from 1 to (1 << n) - 1:
    for here in 0 .. n-1:
        if best[visited][here] is infinity: skip
        for k in 0 .. n-1:
            if visited & (1 << k): skip          # already been
            bigger = visited | (1 << k)
            best[bigger][k] = min(best[bigger][k],
                                  best[visited][here] + dist[here][k])

everyone = (1 << n) - 1
answer = min(best[everyone][last] + dist[last][0] for last in 1 .. n-1)

Where the trick runs out

The table is fast, but it is still 2^n rows. Memory is the first wall. Each slot holds a distance in km, and even a 20-city loop is well under a million km, so a 32-bit number (4 bytes, up to about 2 billion) is plenty:

• 20 cities: 2^20 × 20 ≈ 21 million slots × 4 bytes ≈ 84 MB. Fine.
• 25 cities: 2^25 × 25 ≈ 839 million slots × 4 bytes ≈ 3.4 GB. Painful.
• 30 cities: 2^30 × 30 ≈ 32 billion slots × 4 bytes ≈ 129 GB. Not on a laptop.

So the answer to the challenge is yes, for 20 stops, and “around 20 to 25” is where exact answers stop being practical. Real route planners for 100 stops, like Google’s OR-Tools routing solver, settle for very good routes found by smart guessing and improving, instead of the provably best one.

The same trick away from the van

Any time you have a small, fixed list of yes/no facts, one number can hold them all, and the same operators answer questions about all of them in one step.

• Unix file permissions: each bit is one right (read = 4, write = 2, execute = 1). Mode 6 is 110, read and write; 7 is 111, all three.
• App permission checks: (user_perms & NEEDED) == NEEDED means “has every permission in NEEDED”. Checking != 0 instead would only mean “has at least one of them”.
• Redis SETBIT and BITOP: one bit per user ID means “active today”. AND two days together and you get the users active on both.
• Chess engines: each bit is one of the 64 squares, so one 64-bit number says where all the white pawns are.