Reverse bits of 64-bit unsigned integer

7 September 2015

I have tested few algorithms for reversing bits of unsigned integer. The fastest one would be using a lookup table for smaller segments of long 64-bit number. It's of O(1) complexity too.

For the sake of testing we used two more algorithms, the classic one using reminder after division by 2, and the other one, which would be more brute alike algorithm because it's based on string manipulation, which ought to be the slowest.

Look at the benchmarks:

BenchmarkDivReverse-4       100000000            17.8 ns/op
BenchmarkBruteReverse-4      3000000           554 ns/op
BenchmarkLookupReverse-4    300000000             5.55 ns/op

Function LookupReverse uses lookup table:

func lookupreverse(n uint64) uint64 {
    var ret uint64

    for n > 0 {
        bits := n & 0xff
        n >>= 8

        ret <<= 8
        ret |= uint64(lTable[bits])
    }

    for ret&1 == 0 {
        ret >>= 1
    }

    return ret
}

The lookup table consists of 8-bit numbers. Maybe the above function better suits bigger numbers than 64-bit ones. It doesn't rely exactly on the fact that we have just eight 8-bit segments inside a 64-bit number, which could be coded without a loop. But, the loop goes through as much iterations it needs until there is no another 8-bit segment remaining in a number. For 64-bit number it is no more than fixed eight iterations, which is still of O(1) complexity.

Other two algorithms were useful in test functions. First, we have initialized test table using one algorithm and later we compared those results with other algorithms. It's hard that all algorithms give different results. Reliability of tests is based on having same results with different algorithms.

var reverseTests []reverseTest

func init() {
    for i := 0; i < 8196; i++ {
        number := uint64(rand.Int63())
        reverseTests = append(reverseTests, reverseTest{number, divreverse(number)})
    }
}

func TestBruteReverse(t *testing.T) {
    for _, tt := range reverseTests {
        actual := brutereverse(tt.n)
        if actual != tt.expected {
            t.Errorf("BruteReverese(%x) expected: %x actual: %x ", tt.n, tt.expected, actual)
        }
    }
}

func TestLookupReverse(t *testing.T) {
    for _, tt := range reverseTests {
        actual := lookupreverse(tt.n)
        if actual != tt.expected {
            t.Errorf("LookupReverese(%x) expected: %x actual: %x ", tt.n, tt.expected, actual)
        }
    }
}

Find code samples here github.com/CodingBerg/golang-interview.

By one coder