Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

c

shift

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');
    }
}
like image 512
rsethc Avatar asked Feb 13 '19 21:02

rsethc


People also ask

Can you bit shift by a negative number?

(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.

How does bitwise operator work with negative numbers?

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.


2 Answers

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.

like image 194
Govind Parmar Avatar answered Nov 15 '22 03:11

Govind Parmar


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;
}
like image 27
dbush Avatar answered Nov 15 '22 02:11

dbush