有没有办法反转 UInt64 中的位顺序？

Question

我正在 Swift 中根据 Java 中编写的教程构建国际象棋引擎。在本教程中，Java 的带符号 64 位整数 long 有一个名为 reverse(long i) 的静态方法 "Returns the value obtained by reversing the order of the bits in the two's complement binary representation of the specified long value." 它基本上颠倒了二进制位的顺序，因此，使用 8 -为了简单起见，01000000 将变为 00000010.

我很好奇是否有办法用 Swift 的 UInt64 完成同样的事情。我知道 Java 的 long （有符号，2s 补码）和 Swift 的 UInt64 （无符号）是不同的，但我想这并不难使用 UInt64.

执行此操作

我尝试了 UInt64.byteSwapped，但这似乎并没有让我得到我期望的行为。

Answer 1

不，Swift 标准库不提供反转整数中位顺序的方法，例如参见讨论 Bit reversal在 Swift 论坛中。

可以使用 Bit Twiddling Hacks 中的 C 方法，方法是将 C 代码导入 Swift，或者将其转换为 Swift。

例如，我采用了基于循环的变体

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);
}

因为那不限于某个整数大小。它可以翻译成 Swift 作为 FixedWidthInteger 的扩展，因此它适用于所有大小的整数：

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
    }
}

示例：

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

另一种选择是先使用 byteSwapped 反转字节顺序，然后通过（预先计算的）查找反转每个字节中的位顺序 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 = [=13=].bindMemory(to: UInt8.self)
            for i in 0..<bytes.count {
                bytes[i] = bitReverseTable256[Int(bytes[i])]
            }
        }
        return value
    }
}

有没有办法反转 UInt64 中的位顺序？

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

binary

uint64

bitboard

swift