Search code examples
cshift

Bitwise shift *by* a negative number to reverse the bits in a number

Is it valid to perform a bitwise shift by a negative amount? For example, if I have the following code:

#include <stdint.h>
uint32_t reverse_bits (uint32_t n)
{
    uint32_t result = 0;    
    for (int i = 0; i < 32; i++) 
    {
        uint32_t bit = n & (1 << i);
        bit <<= 31 - i * 2;
        result |= bit;
    }
    return result;
}

Is this something I could expect to work on all architectures (specifically, that the result of expression x << shift_amt where shift_amount < 0 is true, is equivalent to x >> -shift_amt)?

Note: This is not a question about the behavior of performing a bitwise shift on a negative number (ie -1 << 1).

Here is the full test program:

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
uint32_t reverse_bits (uint32_t n)
{
    uint32_t result = 0;
    for (int i = 0; i < 32; i++)
    {
        uint32_t bit = n & (1 << i);
        bit <<= 31 - i * 2;
        result |= bit;
    }
    return result;
}
void print_bits (uint32_t n)
{
    for (int i = 0; i < 32; i++)
        putchar(n & (1 << i) ? '1' : '0');
    putchar('\n');
}
int main ()
{
    for (int i = 0; i < 5; i++)
    {
        uint32_t x = rand();
        x |= rand() << 16;
        print_bits(x);
        print_bits(reverse_bits(x));
        putchar('\n');
    }
}
Solution

  • The C Standard declares that shifting by a negative number is explicitly undefined behavior in § 6.5.7 paragraph 3:

    If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

    Emphasis mine.