190. Reverse Bits

leetcode easy

#bit-manipulation#csharp#dynamic-programming#easy#hash-table#leetcode#string

Task

Переверните биты заданного 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:

C# solution

matched/original

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

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private unordered_map<uint, uint> cache = new unordered_map<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;
    }
}

Java solution

matched/original

class Solution {
    private int reverseByte(int byteVal, Map<Integer, Integer> cache) {
        if (cache.containsKey(byteVal)) {
            return cache.get(byteVal);
        }
        int value = (int)(((byteVal * 0x0202020202L) & 0x010884422010L) % 1023);
        cache.put(byteVal, value);
        return value;
    }
    public int reverseBits(int n) {
        int ret = 0;
        int power = 24;
        Map<Integer, Integer> cache = new HashMap<>();
        while (n != 0) {
            ret += reverseByte(n & 0xff, cache) << power;
            n >>>= 8; // Use unsigned shift
            power -= 8;
        }
        return ret;
    }
}

JavaScript solution

matched/original

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

Python solution

matched/original

import functools
class Solution:
    def reverseBits(self, n: int) -> int:
        ret, power = 0, 24
        while n:
            ret += self.reverseByte(n & 0xFF) << power
            n = n >> 8
            power -= 8
        return ret
    @functools.lru_cache(maxsize=256)
    def reverseByte(self, byte):
        return (byte * 0x0202020202 & 0x010884422010) % 1023

Go solution

matched/original

func reverseByte(b uint32, cache map[uint32]uint64) uint64 {
    value, ok := cache[b]
    if ok {
        return value
    }
    value = (uint64(b) * 0x0202020202 & 0x010884422010) % 1023
    cache[b] = value
    return value
}

func reverseBits(num uint32) uint32 {
    ret := uint64(0)
    power := uint64(24)
    var cache = map[uint32]uint64{}

    for num != 0 {
        ret += reverseByte(num & 0xff, cache) << power
        num = num >> 8
        power -= 8
    }
    return uint32(ret)
}

Explanation

Algorithm

1️⃣

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

2️⃣

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

3️⃣

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

😎