Reversing Bits in Golang

Reversing bits is used in graphics programming, in converting from big endian to little endian, and in complex mathematics, e.g., Fast Fourier Transformations.

I find that working through the source code of your favorite language as a valuable exercise in becoming a more proficient software engineer.

How does Go reverse bits?

We will look at the implementation in Go 1.16. However, this is stable code that is very unlikely to change in future versions.

Let's look at the source code:

// Reverse returns the value of x with its bits in reversed order.
func Reverse(x uint) uint {
    if UintSize == 32 {
        return uint(Reverse32(uint32(x)))
    }
    return uint(Reverse64(uint64(x)))
}

I will focus on reversing the bits of a 64 bit integer, but conceptually reversing a 32 bit integer is very similar, with an additional operation for the 64 bit reversal.

As you can see, the code checks to see if x is a 32 bit unsigned integer, and if not calls Reverse64.

// Reverse64 returns the value of x with its bits in reversed order.
func Reverse64(x uint64) uint64 {
    const m = 1<<64 - 1.            
    x = x>>1&(m0&m) | x&(m0&m)<<1   
    x = x>>2&(m1&m) | x&(m1&m)<<2   
    x = x>>4&(m2&m) | x&(m2&m)<<4   
    return ReverseBytes64(x)
}

There are a handful of bitwise operators (&, >>, <<, |) in these functions that you might not see everyday. If you are not familiar with them, Your Basic Go has a good explanation of how they work.

Before we get into the code itself, I want to explain conceptually at a high level what the code is doing. Through clever bit manipulation the functions are first swapping each set of adjacent bits, then swapping adjacent sets of two bits, then sets of four bits, and so on all the way up to swapping the final two groups of 32 bits.

Consider the 16 bit integer:

^{00 00 01 01 10 10 11 11}

First we swap each adjacent bit, noting that the first and last two groups of bits are unchanged:

^{00 00 10 10 01 01 11 11}

Then we swap each group of adjacent set of 2 bits, though due to the current structure of the integer, nothing will visually change.

^{0000 1010 0101 1111}

Then we swap each adjacent set of 4 bits:

^{1010 0000 1111 0101}

Finally we swap each adjacent set of 8 bits:

^{1111 0101 1010 0000}

and the final result above is the reversal of the original integer.

^{1111 0101 1010 0000 = reverse(0000 0101 1010 1111)}

Back to the code:

// Reverse64 returns the value of x with its bits in reversed order.
func Reverse64(x uint64) uint64 {
    const m = 1<<64 - 1             // (#1)
    x = x>>1&(m0&m) | x&(m0&m)<<1   // (#2)
    x = x>>2&(m1&m) | x&(m1&m)<<2   // (#3)
    x = x>>4&(m2&m) | x&(m2&m)<<4   // (#4)
    return ReverseBytes64(x)
}

Let's start with the constants referenced:

m0-m2 are defined at the top of the code file using hexadecimal notation, below I represent them using binary.

^{m0 = 0101010101010101010101010101010101010101010101010101010101010101}

^{m1 = 0011001100110011001100110011001100110011001100110011001100110011}

^{m2 = 0000111100001111000011110000111100001111000011110000111100001111}

Let's step through the function, using the following uin64 as our example:

^{1001101000001111100110100000111110011010000011111001101000001111}

(#1) m = 1<<64 - 1

This takes the integer 1, left shifts it 64 positions, then subtracts one. The resulting value is:

^{m = 1111111111111111111111111111111111111111111111111111111111111111}

(#2) x = x>>1&(m0&m) | x&(m0&m)<<1

We will break this into

(#2a) x>>1&(m0&m)

and

(#2b) x&(m0&m)<<1

It is helpful here to reference Go's operator precedence, which is similar to the order of operations concept in math. From reading the operator precedence guide, we can see that the bitwise AND operator and the shift operators have equal precedence, and will be evaluated from left to right.

(#2a) x>>1&(m0&m)

We will start by shifting our initial integer that we are reversing one bit to the right.

Our initial uint:

^{1001101000001111100110100000111110011010000011111001101000001111}

x >> 1 ==

^{0100110100000111110011010000011111001101000001111100110100000111}

m0 & m ==

^{m0 = 0101010101010101010101010101010101010101010101010101010101010101
m = 1111111111111111111111111111111111111111111111111111111111111111
m0 & m == m0.1}

(#2a) x>>1&(m0)

^{x>>1 = 0100110100000111110011010000011111001101000001111100110100000111}

^&

^{m0 = 0101010101010101010101010101010101010101010101010101010101010101}

Conceptually, if you think of the adjacent bits exercise we looked at above, what we have done with x>>1 is shift every left-adjacent bit (e.g., the 0 in 01) to the right side of the same adjacent set of two bits.

By combining that with & m0, where m0 has a value of 1 in right bit of every single set of two adjacent bits (e.g., the 1 in 01), we are saving those values. Because the left-adjacent bits of m0 are all 0, we are ignoring those for now and only saving the right adjacent bits.

Now lets look at (#2b)

x&(m0&m)<<1

Here, we are saving all of the right-side sets of two bits and then shifting them to the left by one.

Recall that m0&m is equal to a long series of 01:

^{m0&m = 0101010101010101010101010101010101010101010101010101010101010101}

By combining x&m0 we are saving every right-side adjacent bit, (e.g., the 1 in 01) then shifting them to the left.

Back to (#2)

(#2) x = x>>1&(m0&m) | x&(m0&m)<<1

(#2) x = Every Left Adjacent Bit (now on the right side) | Every Right Adjacent Bit (now on the left side)

Taking a bitwise OR of the two individual calculations, we are combining them into one value.

After line #2 our initial value of

^{1001101000001111100110100000111110011010000011111001101000001111}

becomes

^{0110010100001111011001010000111101100101000011110110010100001111}

If you take the time to go through every single pair of adjacent bits you will see that they have been swapped.

Moving on to (#3)

(#3) x = x>>2&(m1&m) | x&(m1&m)<<2

(#3) is very similar to (#2), except now we are swapping sets of two bits rather than sets of individual bits.

For example:

^{00 11 becomes 11 00.}

Let's review our constants:

^{m1&m = 0011001100110011001100110011001100110011001100110011001100110011}

Here, you can see that the for each set of 4 bits, we always see the 0011 pattern. Because of this, when we do x>>2&(m1&m), we are shifting all bits two to the right and saving the right side of the 4 bit groups, while setting the left sides equal to zero.

The left side does the opposite. It saves the 2 bits on the right side of each 4 bit group then shifts them to the left.

By combining these two separate operations with the bitwise OR operator, we have successfully swapped each set of 4 bits.

Our initial x:
^{0110010100001111011001010000111101100101000011110110010100001111}

now becomes

^{1001010100001111100101010000111110010101000011111001010100001111}

Let's go back to the code:

// Reverse64 returns the value of x with its bits in reversed order.
func Reverse64(x uint64) uint64 {
    const m = 1<<64 - 1             // (#1)
    x = x>>1&(m0&m) | x&(m0&m)<<1   // (#2)
    x = x>>2&(m1&m) | x&(m1&m)<<2   // (#3)
    x = x>>4&(m2&m) | x&(m2&m)<<4   // (#4)
    return ReverseBytes64(x)
}

I went through steps #1-#3. We start by swapping individual sets of bits, then we swapped adjacent sets of two bits. Hopefully you see the pattern. Step #4 would swap adjacent sets of 4 bits,

^{1111 0000 becomes 0000 1111}

Now each byte within the 64 bit integer is reversed, but the sets of bytes themselves are not reversed. The function then calls ReverseBytes64:

func ReverseBytes64(x uint64) uint64 {
    const m = 1<<64 - 1
    x = x>>8&(m3&m) | x&(m3&m)<<8 (#1)
    x = x>>16&(m4&m) | x&(m4&m)<<16 (#2)
    return x>>32 | x<<32  (#3)
}

The same pattern applies here. The incoming integer has each set of bytes reversed. (#1) swaps each byte with the adjacent set of bytes. (#2) swaps each set of 2 bytes with an adjacent set of 2 bytes. Finally, step #3 swaps each set of 4 bytes with the adjacent set of 4 bytes. A 64 bit integer has two sets of 4 bytes, so at the end we are swapping the first half of the bytes with the second half.

The result of this function call Reverse64Bytes is returned to Reverse64 which is returned to Reverse, which was what we started with above.

Conclusion

This is my first attempt at walking through source code and writing down what I have found. I am not satisfied with the visual layout of the bits here, despite writing it I find it difficult to follow the long strings of 1s and 0s. This might be better done as a video or some sort of animated description in the future, but for now this will have to do.

Please let me know if you see any errors or have any suggestions to improve this explanation. I'd love to hear from you.

x = x>>1&(m0) | x&(m0)<<1

---

1. As an aside, if anyone knows why the code is structured this way, I'd love an explanation! Why not just write (#2a) as ↩