Задача: 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) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    private Dictionary<uint, uint> cache = new Dictionary<uint, uint>();

    public uint ReverseByte(uint byteValue) {
        if (cache.TryGetValue(byteValue, out uint cachedValue)) {
            return cachedValue;
        }
        uint value = (byteValue * 0x0202020202 & 0x010884422010) % 1023;
        cache[byteValue] = value;
        return value;
    }

    public uint ReverseBits(uint n) {
        uint ret = 0, power = 24;
        while (n != 0) {
            ret += ReverseByte(n & 0xff) << (int)power;
            n = n >> 8;
            power -= 8;
        }
        return ret;
    }
}

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