Обратные биты целого числа
Я пришел через вопрос интервью. Обратные биты 32-битного целого числа без знака. Я написал этот код, и он совершенно нормальный:
uint32_t reverseBits(uint32_t n) {
for(int i = 0, j = 31; i < j; i++, j--) {
bool iSet = (bool)(n & (1 << i));
bool jSet = (bool)(n & (1 << j));
n &= ~(1 << j);
n &= ~(1 << i);
if (iSet) n |= (1 << j);
if (jSet) n |= (1 << i);
}
return n;
}
После этого возник следующий вопрос - Если эта функция вызывается много раз, как бы вы ее оптимизировали? Я не могу понять, как решение должно быть оптимизировано в этом сценарии.
Рабочий код, который, по вашему мнению, можно улучшить? Похоже, это работа для Coooooooode Обзор!. Я связался со страницей как задать вопрос, потому что ее стоит прочитать, чтобы убедиться, что все публикуемые вами сообщения соответствуют их требованиям.
Ответы 1
Вы можете оптимизировать цикл, используя таблицу обратного просмотра. Для получения более подробной информации вы можете перейти по URL-адресу это, из которого я взял код ниже.
// Generate a lookup table for 32bit operating system
// using macro
#define R2(n) n, n + 2*64, n + 1*64, n + 3*64
#define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
// Lookup table that store the reverse of each table
unsigned int lookuptable[256] = { R6(0), R6(2), R6(1), R6(3) };
/* Function to reverse bits of num */
int reverseBits(unsigned int num)
{
int reverse_num = 0;
// Reverse and then rearrange
// first chunk of 8 bits from right
reverse_num = lookuptable[ num & 0xff ]<<24 |
// second chunk of 8 bits from right
lookuptable[ (num >> 8) & 0xff ]<<16 |
lookuptable[ (num >> 16 )& 0xff ]<< 8 |
lookuptable[ (num >>24 ) & 0xff ] ;
return reverse_num;
}
Вы, вероятно, должны упомянуть источник этого.
Привет @ m69 Я добавил исходник.
Сами GeeksforGeeks, кажется, скопировали его из опубликованной ссылки @zch, не упоминая об этом :-) graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
@ m69 Спасибо за упоминание настоящего источника, я обновил URL-адрес источника.
@ m69 Этот сайт компьютерных фанатов цитирует источник, но только на предыдущий пост по той же теме.
спасибо за Ваш ответ. Я не мог понять создание таблицы поиска по макро-части, даже от geeksforgeeks
Таблица поиска @Kaidul хранит в обратном порядке каждое число, которое находится в диапазоне (0-255)
но как макросы это представляют?
Обязательная ссылка на Bit Twiddling Хаки.