Июльское испытание Leetcode: 12 июля

Сегодняшняя задача — снова забава с битами, надеюсь, вам понравится и эта, как и предыдущая.

Вопрос: Обратные биты заданного 32-битного целого числа без знака.

Пример 1:

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

Пример 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Примечание.

Обратите внимание, что в некоторых языках, таких как Java, нет целочисленного типа без знака. В этом случае и ввод, и вывод будут заданы как целочисленный тип со знаком и не должны влиять на вашу реализацию, поскольку внутреннее двоичное представление целого числа одинаково независимо от того, подписано оно или беззнаково.

В Java компилятор представляет целые числа со знаком, используя дополнительную нотацию числа 2. Таким образом, в Примере 2 выше входные данные представляют собой целое число со знаком -3, а выходные данные представляют собой целое число со знаком -1073741825.

Дополнительные сведения:

Если эта функция вызывается много раз, как бы вы оптимизировали ее?

Это простая, но интересная проблема, так как есть пограничные случаи, которые можно упустить из виду, если не уделить должного внимания, кроме того, что это простая проблема.

Сначала вам следует прочитать о том, что число является подписанным или неподписанным, так как важно знать эту концепцию и когда они могут быть полезны.

Простой подход: итерируйте число от LSB до MSB и переключайте биты до тех пор, пока не получите их. Но здесь мы имеем дело с числами без знака, и с числами без знака все становится немного сложнее, и числа также задаются как двоичное представление числа.

iterate over the bits of the given number. If bit at "ith" position is set in the input number then set the bit at (NO_OF_BITS – 1) – i in the output number. 
Here NO_OF_BITS is number of bits of our given number.
unsigned int reverseBits(unsigned int num){
    unsigned int  NO_OF_BITS = sizeof(num) * 8;
    unsigned int reverse_num = 0, i, temp;
    for (i = 0; i < NO_OF_BITS; i++){
        temp = (num & (1 << i));
        if(temp)
            reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
    }
    return reverse_num;
}

Эффективный подход: без использования дополнительной памяти, то есть без использования переменной «tmp».

uint32_t reverseBits(uint32_t n) {
        int pos = 31; // maintains shift
        // store reversed bits of n. Initially all bits are set to 0
        uint32_t reverse = 0;
        // do till all bits are processed
        while (pos >= 0 && n){
        // if current bit is 1, then set corresponding bit in result
            if (n & 1)
                reverse = reverse | (1 << pos);
            n >>= 1; // drop current bit (divide by 2)
            pos--;  // decrement shift by 1
        }
    return reverse;
}

Другой подход: справочная таблица:
это можно сделать за O(1), если мы знаем размер числа. Мы можем реализовать это с помощью таблицы поиска. Дополнительные сведения см. в разделе Обратные биты с использованием таблицы поиска за время O(1).

Вы можете протестировать свой подход здесь: https://leetcode.com/problems/reverse-bits/

Чтобы узнать больше таких пояснительных статей и понимания концепций, следите за обновлениями.

Удачного кодирования!!!