DEV Community

Brian McGraw
Brian McGraw

Posted on

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)))
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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 

Top comments (0)