I have a function implemented which reverses the bits in a number. The number of bits in the number to be reversed can vary. However, of course it must be shifted to the left at the end to align with the nibble if it is not divisible by 4. This is what I have :
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;
}
Yes this works. However, is there a cleaner way to do this at the end instead of checking if (counter % 4 != 0) ? Like a one line solution to shift based on the number % 4 without checking if it’s 0 first?
4
Reverse in groups of 4 bits?
Something like:
#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);
}
}
2
Replace
if (counter % 4 != 0)
{
reverse_num <<= (4 - counter % 4);
}
with
reverse_num <<= ((-counter) % 4);
or
reverse_num <<= ((-counter) & 3);
Each pair of parentheses can be omitted if desired.
In addition, it is possible to decrement counter instead of incrementing it, then (-counter) can be replaced with counter at the end.
Be careful if counter has an unsigned type that is narrower than int (e.g. if counter has type unsigned short and USHRT_MAX <= INT_MAX). In that case, (-counter) will be zero or negative, and therefore (-counter) % 4 will be zero or negative, and the shift operation with a negative shift amount will result in undefined behavior. That does not apply in OP’s case because counter has type unsigned int. Replacing 4 with 4U would avoid the problem since the negative (-counter) value would be converted to unsigned int before the modulo operation, producing a zero or positive shift value. Similarly & 3 could be replaced with & 3U to avoid problems if int does not use a two’s complement representation of negative values, although it seems unlikely that such implementations ever existed since C23 mandates a two’s complement representation of signed integer types.
4