###
**EDIT:** I made a small mistake, hereâs the updated version:

Okay, this algorithm works in three basic steps, and first I will only list them and after that explain how they work exactly:

- make
**several** copies of the original number (fan out)
- select
**specific** bits
- contract the number

Letâs look at those steps a little bit closer (we will go even closer later on).

**First step** is done by just multiplying them with a âsparseâ number in a way they donât overlap. So when looking at the bits, there are copies of them.

**Second step** is also easy. We use the AND operation to only select some of them. The number we use is called **magic number** for now.

**Third step**: thatâs pure magic! Letâs say we are doing exactly what we want, but for now we donât know how (wait for it).

## The **wrong** concept

**Intuitively**, we would think the algorithm works as follows (letâs say we want to reverse **n** bits)

- Make
**n** copies of the bit pattern
- In the left most copy select the right most bit, to have it at the left most after contracting.
- Second to left copy, second bit, and so on
- Contract them as we have it in mind.

In case of `n = 4`

, this concept (which is wrong) would go like this:

Our binary number is `x = 0i4321`

. I use `0i`

to tell you that I just write the indices of the bit positions, so we know how they end up.

Letâs make copies:

`x * 0b0001 0001 0001 0001 = 0i4321 4321 4321 4321`

Mask:

`0i4321 4321 4321 4321 AND`

`0b0001 0010 0100 1000`

which gives us

`0i0001 0020 0300 4000`

*magic contraction we wish it exists* will make `0i1234`

Makes sense? Yes it does! **But**: we have a problem with the last step: thereâs no operation which does that *magic contraction we wish it exists`. But obviously, there is a solution to that.

Now comes the actual explanation, whatâs going on!

## The **right** concept

The **key** to understanding that algorithm is the **last step**. The **modulo** operation. Everyone knows what MOD does, so I wonât explain that. **However**, the algorithm uses a special number for the modulo: **1023** Why is it special? Itâs `base - 1`

. So they use a base of 1024. Letâs go to our beloved 10-base system, to explain whatâs going on:

`base - 1 = 10 - 1 = 9`

What happens with a number when we do the MOD 10 operation:

Example from the thread I have linked: `34 % 9 = 7`

, the individual digits are added together (you can try this with different numbers, as well (there might be some exceptions due to some kind of overflow!))

Letâs switch to another base: 16 and look what we can do with that in binary representation:

16-base or hex uses 4 bits: `0b0000`

. And the very cool thing by applying `% 15`

is the following.

Take any binary number and do the `% 15`

operation, what you will get is that every group of 4-bits will be added together (contracted!).

**Example**:

`0b0100 0000 0000 0010 0000 0001 % 0i1111`

which is `4194817 % 15 = 7 = 0b0111`

Thatâs the same as: `0b0100 + 0b0000 + 0b0000 + 0b0010 + 0b0000 + 0b0001`

!!! **Amazing!**

**Important:** This only works, if not all 4 bits will be set. Obviously, `0b1111`

mod `0b1111`

wonât result in `0b1111`

And thatâs the **third step** of the algorithm!

We still have to conquer step 1 and 2:

- find the right fan out multiplier
- find the magic number

Letâs say we want to reverse a 3-bit number, and we use `% 15`

for our **third step**, to keep it simple. Letâs build the magic number!

We have two conditions for our magic number. The **first** is: when contracted, it should result in `0b0111`

as we want to use three bits. So we need some *elements* to build the number.

Letâs say we have the following elements: `0b0001`

, `0b0010`

, and `0b0100`

. Shuffle them together as crazy, optionally add some `0b0000`

in between, and I `promise`

you, the `% 15`

will make `0b0111`

out of it!

So **second** condition is, that we select the right bits of our number `0i0321`

. We can achieve that, by combining our elements.

Letâs look at that and go with our **intuitive** concept: make three copies of `0i4321`

by multiplying it with `0b0100 1001`

:

`0i0003 2132 1321`

and find a combination of our *elements* to select the right positions of our number.

`0i0003 2132 1321 AND`

`0b0001 0100 0010 =`

`0i0003 0100 0020`

## Apply `% 15`

we will get: `0i0123`

.

Woohoo! We just reversed a 3-bit number!

To write the steps in decimal:

### Take a 3-bit number x, multiply it with 73 (**fan out**), AND it with 322 (**select bits**), and modulo with 15 (**contract**). That reverses your 3-bit number.

Try yourself: http://www.wolframalpha.com/input/?i=BitAnd[(011+base+2)+*+73,++322]+mod+15+to+binary

Thatâs whatâs going on there.

In general: If you want to revert a n-bit number, your *magic elements* have to be at least (n+1) bits long, if itâs the same (like the **important** note above), the contraction wonât work. Your elementâs can have more than one active bit. With that you can reduce the numbers of copies you have to generate (fan-out step).

The algorithm for 8 bits uses *magic elements* of length 10 (bits)! So the modulo number is `2^10 - 1 = 1023`

. And some of them have two active bits. Thatâs why they only have to make 5 copies instead of 8. For 3-bits I used 3 copies. There might be also a solution which uses less copies for 3 bits. Itâs some Sherlock-work to find them, itâs fun! I canât guarantee, that for every n thereâs a set of (n+1)-bit magic elements to solve the problem. However, I am quite positive there is.

Hope that helped!