Задача: 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 {
    constructor() {
        this.cache = {};
    }

    reverseByte(byte) {
        if (this.cache[byte] !== undefined) {
            return this.cache[byte];
        }
        let value = (byte * 0x0202020202 & 0x010884422010) % 1023;
        this.cache[byte] = value;
        return value;
    }

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

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