Есть ли способ изменить порядок бит в UInt64? - PullRequest
Новая
       78

Есть ли способ изменить порядок бит в UInt64?

1 голос
/ 09 марта 2020

Я строю шахматный движок в Swift на основе учебника, написанного на Java. В этом учебнике 64-разрядное целое число long со знаком Java имеет метод stati c, называемый reverse(long i), который "возвращает значение, полученное путем изменения порядка битов в двоичном представлении двоичного дополнения указанной длинной ценность." По сути, он меняет порядок двоичных битов, так что, для простоты, 01000000 станет 00000010.

Мне любопытно, есть ли способ сделать sh таким же вещь со Свифтом UInt64. Я понимаю, что Java long (подписано, дополнение 2s) и UInt64 (без знака) Свифта отличаются, но я думаю, что это не составит труда сделать с UInt64.

Я пытался UInt64.byteSwapped, но это, похоже, не дает мне ожидаемого поведения.

1 Ответ

1 голос
/ 09 марта 2020

Нет, стандартные библиотеки Swift не предоставляют метод для обратного порядка битов в целых числах, см., Например, обсуждение Обращение битов на форуме Swift.

Можно использовать методы C из Bit Twiddling Hacks , либо импортировав код 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);
}

на основе l oop, потому что он не ограничен определенным целочисленным размером. Его можно перевести на 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 для обратного порядка байтов вначале, а затем обратного порядка битов в каждом байте с помощью (предварительно вычисленной) таблицы поиска: 

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