CODEWITHSUNDEEP
cshift
rsethc
rsethc

Reputation: 2684

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');
    }
}

Upvotes: 6

Views: 2439

Answers (2)

dbush
dbush

Reputation: 224437

As already mentioned, shifting by a negative value invokes undefined behavior as per section 6.5.7p3 of the C standard.

Rather than attempting to guess when you can get away with a negative shift, change your code so you don't need to.

After masking out the bit you want, shift it back to position 0, then shift it to the desired location. Also, make sure you change the constant 1 to 1ul so that you don't end up shifting a signed value into the sign bit or exceed the width of an int. Note also the use of sizeof to avoid hardcoding magic numbers such as 32.

unsigned long reverse_bits (unsigned long n)
{
    unsigned long result = 0;
    for (int i = 0; i < sizeof(unsigned long) * CHAR_BIT; i++)
    {
        unsigned long bit = ((n & (1ul << i)) >> i);
        unsigned long shift = (sizeof(unsigned long) * CHAR_BIT) - i - 1;
        result |= bit << shift;
    }
    return result;
}

Upvotes: 4

Govind Parmar
Govind Parmar

Reputation: 21562

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.

Upvotes: 10

Related Questions