Задача: 190. Reverse Bits
Сложность: easy

Переверните биты заданного 32-битного беззнакового целого числа.

Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

👨‍💻 Алгоритм:

1⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа.

2⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции.

3⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений.

😎 Решение:

class Solution {
    var cache = [UInt32: UInt32]()

    func reverseByte(_ byte: UInt32) -> UInt32 {
        if let cachedValue = cache[byte] {
            return cachedValue
        }
        let value = ((byte * 0x0202020202) & 0x010884422010) % 1023
        cache[byte] = value
        return value
    }

    func reverseBits(_ n: UInt32) -> UInt32 {
        var ret: UInt32 = 0
        var power: UInt32 = 24
        var n = n
        while n != 0 {
            ret += reverseByte(n & 0xff) << power
            n = n >> 8
            power -= 8
        }
        return ret
    }
}

Ставь 👍 и забирай 📚 Базу знаний