counter

Here’s a common situation:

• You have a list of items
• You’re currently at a particular item in that list

For example:

• You have a shopping list, and you’re currently looking for a particular product;
• You’re reading a book (composed of a list of pages), and you’re currently reading a particular page;
• You’re following a tutorial composed of a list of lessons, and you’re currently reading a particular lesson.

So how can we represent this concept?

A common and easy approach is to use an index. This just means storing a number that tells us where we are in the list — like telling someone “I’m on page 17” when they ask you where you are in a book.

common functions

What are some common things we want to do with an index?

• Check if we’re at the right page (e.g. “are you on page 17?”)
• Compare it with other indices (e.g. “are you before/after page 54?”)
• Increment it (i.e. “turn to the next page”)
• Decrement it (i.e. “turn to the previous page”)
• Minimise it (i.e. “go to the first page”)
• Maximise it (i.e. “go to the last page”)

We’ll look at all of these in turn, but let’s start with incrementing and decrementing.

rules of incrementing

• Check the digits from lowest to highest
• If you find a 1, change it to a 0
• If you find a 0, change it to a 1 — and then stop!

rules of decrementing

• Check the digits from lowest to highest
• If you find a 0, change it to a 1
• If you find a 1, change it to a 0 — and then stop!

symmetry

The laws of incrementing and decrementing look suspiciously similar.

Imagine we keep an index A that we’re going to increment and decrement. Let’s say A has 4 digits, so it varies between 0000 and 1111.

Let’s also keep an index B. B is linked to A, and is its complement — which means that wherever A has a 0, B has a 1, and vice versa. So when A is 0110, B is 1001.

When we compare A and B digit by digit, exactly one of them must be 1 and exactly one of them is 0. Therefore, the pairwise sum of digits is 1 in every position, which means the total sum is always 1111.

Therefore: because the sum of A and B is a constant value (1111), then whenever we change A, we have to change B by an equal and opposite amount. To take a specific example: whenever we increment A, we have to decrement B.

So instead of talking about “incrementing A”, let’s call it “incrementing A / decrementing B”. For short, we’ll call it “crementing AB”.

In each column, A and B together always have exactly one 1 and exactly one 0. So whenever we change A to a different value, each column always starts with one 1 and one 0; and each column ends up with one 1 and one 0.

… this means that all valid transformations of A can be performed just by swapping 1s and 0s within columns.

Let’s visualise this using presence encoding, representing 1 as and 0 as :

Whenever we want to change the value of A (the left-hand column), we just move some number of marbles left or right. All valid moves can be represented like this.

This is very convenient! As we’ve seen before, presence encoding can run into the problem of “where do I get a marble from?” But with this setup, we always have exactly the right number of and ; we just have to swap their positions.

combining operations

Whenever we increment A, B automatically decrements. So we can now combine our increment and decrement rules into a single rule:

• Check the digit pairs from lowest to highest
• If you find a 10, swap the digits.
• If you find a 01, swap the digits — and then stop!

continue