Рубрики

Напишите эффективную программу на C для обращения битов числа

Получив целое число без знака, переверните все его биты и верните число с обратными битами.

Input : n = 1
Output : 2147483648  
On a machine with size of unsigned
bit as 32. Reverse of 0....001 is
100....0.

Input : n = 2147483648
Output : 1                          

Метод 1 — Простой
Перебрать все биты целого числа. Если бит в i-й позиции установлен в i / p нет. затем установите бит в (NO_OF_BITS — 1) — i в o / p. Где NO_OF_BITS — количество битов, присутствующих в данном числе.

/ * Функция для инвертирования битов num * /

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;

}

  
/ * Функция драйвера для проверки вышеуказанной функции * /

int main()

{

    unsigned int x = 2; 

    printf("%u", reverseBits(x));

    getchar();

}

Вышеприведенную программу можно оптимизировать, исключив использование переменной temp. Смотрите ниже измененный код.

unsigned int reverseBits(unsigned int num)

{

    unsigned int  NO_OF_BITS = sizeof(num) * 8;

    unsigned int reverse_num = 0;

    int i;

    for (i = 0; i < NO_OF_BITS; i++)

    {

        if((num & (1 << i)))

           reverse_num |= 1 << ((NO_OF_BITS - 1) - i);  

   }

    return reverse_num;

}

Сложность времени: O (n)
Космическая сложность: O (1)

Метод 2 — Стандартный
Идея состоит в том, чтобы сохранять заданные биты num в reverse_num до тех пор, пока num не станет равным нулю. После того как num станет равным нулю, сдвиньте оставшиеся биты reverse_num.

Пусть num хранится с использованием 8 битов, а num — 00000110. После цикла вы получите reverse_num как 00000011. Теперь вам нужно сдвинуть left_verse_num еще 5 раз, и вы получите точное обратное значение 01100000.

unsigned int reverseBits(unsigned int num)

{

    unsigned int count = sizeof(num) * 8 - 1;

    unsigned int reverse_num = num;

      

    num >>= 1; 

    while(num)

    {

       reverse_num <<= 1;       

       reverse_num |= num & 1;

       num >>= 1;

       count--;

    }

    reverse_num <<= count;

    return reverse_num;

}

  

int main()

{

    unsigned int x = 1;

    printf("%u", reverseBits(x));

    getchar();

}

Сложность времени: O (log n)
Космическая сложность: O (1)

Метод 3 — Таблица поиска:
Мы можем инвертировать биты числа в O (1), если мы знаем размер числа. Мы можем реализовать это, используя справочную таблицу. Пожалуйста, обратитесь к обратным битам, используя таблицу поиска в O (1) времени для деталей.

Источник :
https://graphics.stanford.edu/~seander/bithacks.html

Рекомендуемые посты:

Напишите эффективную программу на C для обращения битов числа

0.00 (0%) 0 votes