Arithmetic Right Shift Gives Bogus Result

Arithmetic right shift gives bogus result?

In C++ as in C, shifts are limited to the size (in bits) of the value shifted. For instance, if unsigned int is 32 bits, then a shift of more than 31 is undefined.

In practice, a common result is that the 5 least-significant bits of the shift amount are used and the higher order bits are ignored; this is due to the compiler producing a machine instruction which does exactly that (eg SHR on x86).

In this case, the shift value is 100000 (decimal) which happens to be 11000011010100000 in binary - the lower 5 bits are zero. So, you're effectively getting a shift by 0. You shouldn't rely on this however; technically, what you're seeing is undefined behaviour.

References:

For C, N1570 section 6.5.7:

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.

For C++, N3690 section 5.8 "[expr.shift]":

The behavior is undefined if the right operand is negative, or greater
than or equal to the length in bits of the promoted left operand.

N1570 is a draft, nearly identical to the released ISO C11 standard; this clause has been pretty much the same since the 1989 ANSI C standard.

N3690 is a recent draft of the C++ standard; I'm not sure whether it's the best one to use, but again, this clause hasn't changed.

Right bit-shift giving wrong result, can someone explain

The thing is you are not considering negative numbers representation correctly. With right shifting, the type of shift (arithmetic or logical) depends on the type of the value being shifted. If you cast your value to an unsigned value, you might get what you are expecting:

int16_t b = ((unsigned int)a) >> 5;

You are using -109 (16 bits) in your example. 109 in bits is:

00000000 01101101

If you take's 109 2's complement you get:

11111111 10010011

Then, you are right shifting by 5 the number 11111111 10010011:

__int16_t a = -109;
__int16_t b = a >> 5; // arithmetic shifting
__int16_t c = ((__uint16_t)a) >> 5; // logical shifting
printf("%d %d %d\n", a,b,c);

Will yield:

-109 -4 2044

Signed right shift = strange result?

Since x is a signed quantity, the result of (x & (0xFF << 24)) is 0xFF000000 which is also signed and thus a negative number since the top (sign) bit is set. The >> operator on int (a signed value) performs sign extension (Edit: though this behaviour is undefined and implementation-specific) and propagates the sign bit value of 1 as the value is shifted to the right.

You should rewrite the function as follows to work exclusively on unsigned values:

unsigned reverse(unsigned x)
{
    unsigned int reversed = 0;

    reversed = (x & (0xFF << 24)) >> 24;
    reversed |= (x & (0xFF << 16)) >> 8;
    reversed |= (x & (0xFF << 8)) << 8;
    reversed |= (x & 0xFF) << 24;

    return reversed;
}

Question on arithmetic right shift operator

As far as I can tell, this is practice problem 2.16 from the global edition of Computer Science: A Programmer's Perspective (3rd edition), which according to the original authors is full of errors.

Direct quote from the errata page:

Note on the Global Edition: Unfortunately, the publisher arranged for the generation of a different set of practice and homework
problems in the global edition. The person doing this didn't do a very
good job, and so these problems and their solutions have many errors.
We have not created an errata for this edition.

The advice around the web seems to be to pick up the North American edition if you're interested in doing the practice and homework problems.

Your answer is indeed the correct one:

0x44 >> 3 == 0x08

Java Method returns wrong value after left and right arithmetic bit-shifting

Use logical-and instead of left/right shift, to avoid issues with the fact that short is signed:

short i = 1557;

short i_masked = (short)(i & 0x001F);

or, perhaps more clearly

short i_masked = (short) (i & 0b0000000000011111);

To understand what is happening in your code I suggest you print out the value after right-shifting but before applying abs().

Arithmetic right shift examples in my textbook shift in ones when the MSB was zero

No shift will ever fill with 1 when the input's MSB was 0. Note that the reverse isn't true (logical right shift always fills with zero).

If the book doesn't have some extra context, then it's simply an error. That's not a rotate or anything else. Not even 1's complement or sign/magnitude could explain it (because the number is positive in all 3 of those representations).

Arithmetic right shifts in 2's complement shift in copies of the sign bit. (so for example sar eax, 31 broadcasts the sign bit to all bits of the 32-bit register.

The sign of an arithmetic shift result will always be the same as the sign of the input.

---

Logical right shifts always shift in zeros.

---

Left shifts are the same for logical and arithmetic: they shift in zeros. (x86 has a sal mnemonic, but it's just an alternate name for the same opcode as shl. Later x86 extensions don't bother mentioning an arithmetic left shift, e.g. there's a SIMD pslld (packed-integer shift left logical) but no pslad.)

In sign/magnitude, arithmetic left shifts would I guess leave the sign bit untouched. I'm not sure if 1's complement arithmetic left shifts would need any special treatment.

But 2's complement arithmetic left shift is identical to logical. (And identical to add same,same to left shift by 1 aka multiply by 2.)

Weird behavior of right shift in C (sometimes arithmetic, sometimes logical)

Quoting from https://en.cppreference.com/w/c/language/integer_constant, for an hexadecimal integer constant without any suffix

The type of the integer constant is the first type in which the value can fit, from the list of types which depends on which numeric base and which integer-suffix was used.

int
unsigned int
long int
unsigned long int
long long int(since C99)
unsigned long long int(since C99)

Also, later

There are no negative integer constants. Expressions such as -1 apply the unary minus operator to the value represented by the constant, which may involve implicit type conversions.

So, if an int has 32 bit in your machine, 0x80000000 has the type unsigned int as it can't fit an int and can't be negative.

The statement

int x = 0x80000000;

Converts the unsigned int to an int in an implementation defined way, but the statement

int x = 0x80000000 >> 3;

Performs a right shift to the unsigned int before converting it to an int, so the results you see are different.

EDIT

Also, as M.M noted, the format specifier %x requires an unsigned integer argument and passing an int instead causes undefined behavior.

Undefined behavior of right-shift in C++

One of the goals of C++ is to allow for fast, efficient code, "close to the hardware". And on most hardware, an integer right shift or left shift can be implemented by a single opcode. The trouble is, different CPUs have different behavior in this case where the shift magnitude is more than the number of bits.

So if C++ mandated a particular behavior for shift operations, when producing code for a CPU whose opcode behavior doesn't match all the Standard requirements, compilers would need to insert checks and logic to make sure the result is as defined by the Standard in all cases. This would need to happen to almost all uses of the built-in shift operators, unless an optimizer can prove the corner case won't actually happen. The added checks and logic would potentially slow down the program.

Why is this C arithmetic shift implementation not working?

From C99 6.5.7 Bitwise shift operators paragraph 4: (emphasis mine)

4. The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 x 2^E2 , reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 x 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

You are trying to use -1<<(sizeof(x_arith)*8) for which your E1 is -1:

• This is not "a signed type and nonnegative value" (-1 is signed and negative).
• The "and E1 x 2^E2 is representable" clause only applies if "signed type and nonnegative value" is true. (See Is left and right shifting negative integers defined behavior? for more discussion.)

Therefore, your statement falls into the dreaded "undefined behavior" category, which means all bets are off. But all is not lost.

First of all, you can cheat. The CPU's assembly language usually has an arithmetic shift right instruction, so you can just use that. For example, with the x86 instruction sar (shift arithmetic right):

    int arith(int x, unsigned k) {
      asm volatile ("sar %1,%0" :"+r"(x) :"c"((unsigned char)k));
      return x;
    }

Notice that I have changed your function signature a bit. Semantically, the number of bits k being shifted right should never be negative. (If you want to shift left, use that.) In fact, the paragraph (#3) before the one quoted above states (referring to both << and >>):

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.

So k should never be negative under any circumstances, and I have made it unsigned. I changed x to a signed int so that it can be tested and examined with negative numbers (more on this below). The return type was changed to match.

Of course this assembly solution only works on an x86 machine. Something universal might be better. This answer to Shift operator in C has a nice summary of the mathematics of bit shifting. For a nonnegative x, arithmetic shift right by k bits has the same result as integer division by 2^k. The difference is where x is negative, integer division is rounded towards zero and arithmetic shift right is rounded to negative infinity. This leads to

    int arith(int x, unsigned k) {
      if ( x >= 0 ) {
        // Same as integer division for nonnegative x
        return x/(1<<k);
      } else {
        // If negative, divide but round to -infinity
        return x/(1<<k) - ( x % (1<<k) == 0 ? 0 : 1 );
      }
    }

The ternary operator is to decide if there is any remainder in the division. If there is, a 1 is subtracted to "round down." The 1<<k of course is a simple way to calculate 2^k. Notice that this version requires x to be a signed type, otherwise x >= 0 would always evaluate to true.

Is right-shifting an unsigned integer by its total number of bits UB ?

According to the C++ Standard (5.8 Shift operators)

1. ...The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted
   left operand

The same is written in the C Standard (6.5.7 Bitwise shift operators)

3 The integer promotions are performed on each of the operands. The
type of the result is that of the promoted left operand. 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.

---

Related Topics