Задача: 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 {
    private $cache = [];

    function reverseByte($byte) {
        if (isset($this->cache[$byte])) {
            return $this->cache[$byte];
        }
        $value = ($byte * 0x0202020202 & 0x010884422010) % 1023;
        $this->cache[$byte] = $value;
        return $value;
    }

    function reverseBits($n) {
        $ret = 0;
        $power = 24;
        while ($n != 0) {
            $ret += $this->reverseByte($n & 0xff) << $power;
            $n = $n >> 8;
            $power -= 8;
        }
        return $ret;
    }
}

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