Is there a way to reverse the bit order in UInt64?

Question

I am building a chess engine in Swift based off a tutorial written in Java. In the tutorial, Java's signed 64 bit integer long has a static method called reverse(long i) that "Returns the value obtained by reversing the order of the bits in the two's complement binary representation of the specified long value." It basically reverses the order of the binary bits so that, using 8-bit for simplicity's sake, 01000000 would become 00000010.

I am curious if there is a way to accomplish the same thing with Swift's UInt64. I understand that Java's long (signed, 2s complement) and Swift's UInt64 (unsigned) are different, but I imagine it wouldn't be hard to do this with UInt64.

I tried UInt64.byteSwapped, but this doesn't seem to be getting me the behavior I expect.

Answer 1

No, the Swift standard libraries do not provide a method to reverse the order of bits in an integer, see for example the discussion Bit reversal in the Swift forum.

One can use the C methods from Bit Twiddling Hacks, either by importing C code to Swift, or by translating it to Swift.

As an example, I have taken the loop-based variant

unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2 
unsigned int mask = ~0;         
while ((s >>= 1) > 0) 
{
  mask ^= (mask << s);
  v = ((v >> s) & mask) | ((v << s) & ~mask);
}

because that is not restricted to a certain integer size. It can be translated to Swift as an extension to FixedWidthInteger so that it works with integers of all sizes:

extension FixedWidthInteger {
    var bitSwapped: Self {
        var v = self
        var s = Self(v.bitWidth)
        precondition(s.nonzeroBitCount == 1, "Bit width must be a power of two")
        var mask = ~Self(0)
        repeat  {
            s = s >> 1
            mask ^= mask << s
            v = ((v >> s) & mask) | ((v << s) & ~mask)
        } while s > 1
        return v
    }
}

Examples:

print(String(UInt64(1).bitSwapped, radix: 16))
// 8000000000000000
print(String(UInt64(0x8070605004030201).bitSwapped, radix: 16))
// 8040c0200a060e01
print(String(UInt16(0x1234).bitSwapped, radix: 16))
// 2c48

Another option would be to use byteSwapped to reverse the order of bytes first, and then reverse the order of the bits in each byte with a (precomputed) lookup table:

fileprivate let bitReverseTable256: [UInt8] = [
    0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240,
    8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248,
    4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244,
    12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60, 188, 124, 252,
    2, 130, 66, 194, 34, 162, 98, 226, 18, 146, 82, 210, 50, 178, 114, 242,
    10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218, 58, 186, 122, 250,
    6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214, 54, 182, 118, 246,
    14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94, 222, 62, 190, 126, 254,
    1, 129, 65, 193, 33, 161, 97, 225, 17, 145, 81, 209, 49, 177, 113, 241,
    9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89, 217, 57, 185, 121, 249,
    5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85, 213, 53, 181, 117, 245,
    13, 141, 77, 205, 45, 173, 109, 237, 29, 157, 93, 221, 61, 189, 125, 253,
    3, 131, 67, 195, 35, 163, 99, 227, 19, 147, 83, 211, 51, 179, 115, 243,
    11, 139, 75, 203, 43, 171, 107, 235, 27, 155, 91, 219, 59, 187, 123, 251,
    7, 135, 71, 199, 39, 167, 103, 231, 23, 151, 87, 215, 55, 183, 119, 247,
    15, 143, 79, 207, 47, 175, 111, 239, 31, 159, 95, 223, 63, 191, 127, 255]

extension FixedWidthInteger {
    var bitSwapped: Self {
        var value = self.byteSwapped
        withUnsafeMutableBytes(of: &value) {
            let bytes = $0.bindMemory(to: UInt8.self)
            for i in 0..<bytes.count {
                bytes[i] = bitReverseTable256[Int(bytes[i])]
            }
        }
        return value
    }
}