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

Question

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

Yes, I'll edit the sample code to imply explicitly a 32 bits (or wider) unsigned integer type — rsethc, Feb 13 '19 at 21:28
Curious - what does the warnings on your compiler say? `warning: left shift count is negative [-Wshift-count-negative]` (When I feed a negative number in directly using <<= -1.) — Michael Dorgan, Feb 13 '19 at 21:29
Admittedly I have not tested this yet, perhaps I should do that right now. — rsethc, Feb 13 '19 at 21:30
Possible duplicate of [Left shifting with a negative shift count](https://stackoverflow.com/questions/4945703/left-shifting-with-a-negative-shift-count) — vgru, Feb 13 '19 at 21:33
@MichaelDorgan GCC (mingw-w64 6.3.0) does not emit any warnings for this code. — rsethc, Feb 13 '19 at 21:36
Also from actually bothering to test it I see that it definitely does not work as intended, so I suppose there I have my answer about X64 too. — rsethc, Feb 13 '19 at 21:37
I would be very curious to know whether this happens to work on ARM though, if anyone feels like running the example code (I will update it to be the full test program) — rsethc, Feb 13 '19 at 21:38
Godbolt is great but I am unaware of its ability to actually run the code, and the assembly output does not tell me much on its own. — rsethc, Feb 13 '19 at 21:43
@rsethc: it's UB, what's the point in doing this? If it turns out to be working today, gcc could easily change the way it compiles this in future versions, if by assuming that the count is always positive it will get more optimization possibilities. Just use `if (shift < 0) x >>= -shift;` and let gcc decide if it can utilize some architecture-specific tricks to avoid checking. [Btw there are probably better algorithms for bit reversing out there](http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious). — vgru, Feb 13 '19 at 21:50

Govind Parmar · Accepted Answer · 2019-02-13T21:27:00.700

10

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.

edited Feb 13 '19 at 21:27

answered Feb 13 '19 at 21:21

Govind Parmar

20,656
7
53
85

I suppose that's as clear as it can get from the C Standard, though since it is "undefined" I am wondering if, given a specific target architecture (i.e. that you know you're specifically going to be using X86-64) whether the actual shift instructions the compiler will generate are, in terms of the actual machine's specification, going to behave as intended. (i.e. while C leaves this behavior undefined, does X64 or ARM have a more concrete definition of the behavior?) – rsethc Feb 13 '19 at 21:27
If it's undefined (UB), you cannot depend on anything, even if it appears to work. Next version of the compiler can, at will, change it and not you have a really hard to find bug in your code. – Michael Dorgan Feb 13 '19 at 21:31
Easy enough to check for a negative number and shift the other direction positive if needed I think. – Michael Dorgan Feb 13 '19 at 21:32
...and it is explicitely forbidden to shift by more than the bitwidth of the operand. – wildplasser Feb 13 '19 at 21:32
The reason I was hoping negative operand would cause a backward shift was so that I didn't have to have a branch in order to do a left-shift versus right-shift based on the sign of the operand (and also negation). dbush's solution meets this goal since it is still able to avoid branching inside the loop. – rsethc Feb 13 '19 at 21:57
1

@rsethc: No, shift instructions in hardware generally do not respect a signed operand. If, in assembly language, you pass a negative value to a shift instruction, a typical behavior is to use only the low five bits for a 32-bit operand. Hence only shifts of 0 to 31 bits are possible; negative shifts are not. – Eric Postpischil Feb 14 '19 at 02:08

dbush · Answer 2 · 2019-02-13T21:52:21.973

4

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

edited Feb 13 '19 at 21:52

answered Feb 13 '19 at 21:46

dbush

205,898
23
218
273

@wildplasser Good idea. Edited. – dbush Feb 13 '19 at 21:52
It's true that first shifting the value all the way to the ones place does solve the problem in a more robust way. However as for using sizeof, it's clever but generally I would want to just ignore extra bytes in the length of the type, since the logic is all based around 32-bit widths. – rsethc Feb 13 '19 at 21:53
@rsethc There are excellent examples of bitrev at bithacks@stanford.edu. – wildplasser Feb 13 '19 at 21:56
@rsethc You can easily replace `unsigned long` with `uint32_t` in the above code and replace `sizeof(unsigned long) * CHAR_BIT` with `32` and get the same behavior for the type you want. – dbush Feb 13 '19 at 21:57
Something else I do not quite get is why `1ul` is any better than `1`: since it's positive, `1ul` and `1` are equivalent aside from potentially having different widths (if `sizeof(long) != sizeof(int)`) though the width of `(int)1` should certainly be enough to account for any valid shift amount. – rsethc Feb 13 '19 at 22:01
Oh, integer promotion of the value being shifted? – rsethc Feb 13 '19 at 22:34
Even if the value being shifted gets promoted to a signed type, I imagine that should not matter even if the value represents a negative number when treated as signed, since this is not an arithmetic shift operation. – rsethc Feb 13 '19 at 22:36
1

@rsethc If the type of a value is signed, shifting a bit into the sign bit is undefined behavior, specifically `1<<31` if `int` is 32 bits or less. By using the `UL` suffix, it forces the value to be an `unsigned long` so that we *don't* shift into the sign bit. – dbush Feb 13 '19 at 22:40

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

2 Answers2

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