Сдвиг числа на основе его остатка, разделенного на 4 - C
У меня реализована функция, которая меняет местами биты в числе. Количество битов в инвертируемом числе может варьироваться. Однако, конечно, его необходимо сдвинуть влево в конце, чтобы выровнять с полубайтом, если он не делится на 4. Вот что у меня есть:
uint64_t revBits(uint64_t num)
{
unsigned int counter = 0;
uint64_t reverse_num = 0;
while (num)
{
reverse_num <<= 1;
reverse_num |= num & 1;
num >>= 1;
counter++;
}
if (counter % 4 != 0)
{
reverse_num <<= (4 - counter % 4);
}
return reverse_num;
}
Да, это работает. Однако есть ли более чистый способ сделать это в конце вместо проверки (counter % 4 != 0)? Как однострочное решение для сдвига на основе числа % 4 без предварительной проверки, равно ли оно 0?
@pmg Я не уверен, что понимаю тебя
Я дал полный ответ из этого комментария :)
Почему функция, реверсирующая биты, должна соответствовать размеру полубайта?
Ответы 2
Реверс группами по 4 бита?
Что-то вроде:
#include <inttypes.h>
#include <stdio.h>
uint64_t revBits(uint64_t num) {
unsigned int counter = 0;
uint64_t reverse_num = 0;
while (num) {
reverse_num <<= 1;
reverse_num |= num & 1;
num >>= 1;
counter++;
}
if (counter % 4 != 0) {
reverse_num <<= (4 - counter % 4);
}
return reverse_num;
}
uint64_t revBits4(uint64_t num) {
static const unsigned char reverse_table[] = {
0b0000, 0b1000, 0b0100, 0b1100, 0b0010, 0b1010, 0b0110, 0b1110,
0b0001, 0b1001, 0b0101, 0b1101, 0b0011, 0b1011, 0b0111, 0b1111};
uint64_t reverse_num = 0;
while (num) {
reverse_num <<= 4;
reverse_num |= reverse_table[num & 0b1111];
num >>= 4;
}
return reverse_num;
}
int main(void) {
for (uint64_t k = 0; k < 2000000000; k++) {
uint64_t v1, v2;
v1 = revBits(k);
v2 = revBits4(k);
if (v1 != v2) printf("Oops ... revBits4() failed for %" PRIu64 "\n", k);
}
}
Спасибо. На самом деле это отличное решение.
Заменять
if (counter % 4 != 0)
{
reverse_num <<= (4 - counter % 4);
}
с
reverse_num <<= ((-counter) % 4);
или
reverse_num <<= ((-counter) & 3);
При желании каждую пару скобок можно опустить.
Кроме того, можно уменьшить counter вместо увеличения, тогда (-counter) можно заменить на counter в конце.
Будьте осторожны, если counter имеет беззнаковый тип, уже, чем int (например, если counter имеет типы unsigned short и USHRT_MAX <= INT_MAX). В этом случае (-counter) будет нулевым или отрицательным, и, следовательно, (-counter) % 4 будет нулевым или отрицательным, а операция сдвига с отрицательной величиной сдвига приведет к неопределенному поведению. Это неприменимо в случае ОП, потому что counter имеет тип unsigned int. Замена 4 на 4U позволит избежать проблемы, поскольку отрицательное значение (-counter) будет преобразовано в unsigned int перед операцией по модулю, создавая нулевое или положительное значение сдвига. Точно так же & 3 можно заменить на & 3U, чтобы избежать проблем, если int не использует представление отрицательных значений с двоичным дополнением, хотя кажется маловероятным, что такие реализации когда-либо существовали, поскольку C23 требует представления с двоичным дополнением целочисленных типов со знаком.
@interjay Только для беззнаковых типов, уже int. В этом случае 4 можно заменить на 4U.
Вы правы, я пропустил unsigned.
@IanAbbott Спасибо. До сих пор я никогда не рассматривал возможность использования модуля отрицательного числа. Это хорошо.
Реверс группами по 4 бита?
unsigned reverse_table[] = {0b0000, 0b1000, 0b0100, ..., 0b1111};