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');
}
}
(See undefined behavior 51.) Do not shift an expression by a negative number of bits or by a number greater than or equal to the precision of the promoted left operand. The precision of an integer type is the number of bits it uses to represent values, excluding any sign and padding bits.
When representing integers using a fixed number of bits, negative numbers are typically represented using two's complement. If using n bit numbers, the two's complement of a number x with 0 ≤ x < 2 n 0 \leq x < 2^n 0≤x<2n is ( − x ) mod 2 n = 2 n − x (-x) \mathbin{\text{mod}} 2^n = 2^n - x (−x)mod2n=2n−x.
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.
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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With