Are the shift operators (<<, >>) arithmetic or logical in C?

Question

When shifting left, there is no difference between arithmetic and logical shift. When shifting right, the type of shift depends on the type of the value being shifted.

(As background for those readers unfamiliar with the difference, a "logical" right shift by 1 bit shifts all the bits to the right and fills in the leftmost bit with a 0. An "arithmetic" shift leaves the original value in the leftmost bit. The difference becomes important when dealing with negative numbers.)

When shifting an unsigned value, the >> operator in C is a logical shift. When shifting a signed value, the >> operator is an arithmetic shift.

For example, assuming a 32 bit machine:

signed int x1 = 5;
assert((x1 >> 1) == 2);
signed int x2 = -5;
assert((x2 >> 1) == -3);
unsigned int x3 = (unsigned int)-5;
assert((x3 >> 1) == 0x7FFFFFFD);

According to K&R 2nd edition the results are implementation-dependent for right shifts of signed values.

Wikipedia says that C/C++ 'usually' implements an arithmetic shift on signed values.

Basically you need to either test your compiler or not rely on it. My VS2008 help for the current MS C++ compiler says that their compiler does an arithmetic shift.

TL;DR

Consider i and n to be the left and right operands respectively of a shift operator; the type of i, after integer promotion, be T. Assuming n to be in [0, sizeof(i) * CHAR_BIT) — undefined otherwise — we've these cases:

| Direction  |   Type   | Value (i) | Result                   |
| ---------- | -------- | --------- | ------------------------ |
| Right (>>) | unsigned |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    ≥ 0    | −∞ ← (i ÷ 2ⁿ)            |
| Right      | signed   |    < 0    | Implementation-defined†  |
| Left  (<<) | unsigned |    ≥ 0    | (i * 2ⁿ) % (T_MAX + 1)   |
| Left       | signed   |    ≥ 0    | (i * 2ⁿ) ‡               |
| Left       | signed   |    < 0    | Undefined                |

^{† most compilers implement this as arithmetic shift
‡ undefined if value overflows the result type T; promoted type of i}

---

Shifting

First is the difference between logical and arithmetic shifts from a mathematical viewpoint, without worrying about data type size. Logical shifts always fills discarded bits with zeros while arithmetic shift fills it with zeros only for left shift, but for right shift it copies the MSB thereby preserving the sign of the operand (assuming a two's complement encoding for negative values).

In other words, logical shift looks at the shifted operand as just a stream of bits and move them, without bothering about the sign of the resulting value. Arithmetic shift looks at it as a (signed) number and preserves the sign as shifts are made.

A left arithmetic shift of a number X by n is equivalent to multiplying X by 2ⁿ and is thus equivalent to logical left shift; a logical shift would also give the same result since MSB anyway falls off the end and there's nothing to preserve.

A right arithmetic shift of a number X by n is equivalent to integer division of X by 2ⁿ ONLY if X is non-negative! Integer division is nothing but mathematical division and round towards 0 (trunc).

For negative numbers, represented by two's complement encoding, shifting right by n bits has the effect of mathematically dividing it by 2ⁿ and rounding towards −∞ (floor); thus right shifting is different for non-negative and negative values.

for X ≥ 0, X >> n = X / 2ⁿ = trunc(X ÷ 2ⁿ)

for X < 0, X >> n = floor(X ÷ 2ⁿ)

where ÷ is mathematical division, / is integer division. Let's look at an example:

37)₁₀ = 100101)₂

37 ÷ 2 = 18.5

37 / 2 = 18 (rounding 18.5 towards 0) = 10010)₂ [result of arithmetic right shift]

-37)₁₀ = 11011011)₂ (considering a two's complement, 8-bit representation)

-37 ÷ 2 = -18.5

-37 / 2 = -18 (rounding 18.5 towards 0) = 11101110)₂ [NOT the result of arithmetic right shift]

-37 >> 1 = -19 (rounding 18.5 towards −∞) = 11101101)₂ [result of arithmetic right shift]

As Guy Steele pointed out, this discrepancy has led to bugs in more than one compiler. Here non-negative (math) can be mapped to unsigned and signed non-negative values (C); both are treated the same and right-shifting them is done by integer division.

So logical and arithmetic are equivalent in left-shifting and for non-negative values in right shifting; it's in right shifting of negative values that they differ.

Operand and Result Types

Standard C99 §6.5.7:

Each of the operands shall have integer types.

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 behaviour is undefined.

short E1 = 1, E2 = 3;
int R = E1 << E2;

In the above snippet, both operands become int (due to integer promotion); if E2 was negative or E2 ≥ sizeof(int) * CHAR_BIT then the operation is undefined. This is because shifting more than the available bits is surely going to overflow. Had R been declared as short, the int result of the shift operation would be implicitly converted to short; a narrowing conversion, which may lead to implementation-defined behaviour if the value is not representable in the destination type.

Left Shift

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×2^E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and non-negative value, and E1×2^E2 is representable in the result type, then that is the resulting value; otherwise, the behaviour is undefined.

As left shifts are the same for both, the vacated bits are simply filled with zeros. It then states that for both unsigned and signed types it's an arithmetic shift. I'm interpreting it as arithmetic shift since logical shifts don't bother about the value represented by the bits, it just looks at it as a stream of bits; but the standard talks not in terms of bits, but by defining it in terms of the value obtained by the product of E1 with 2^E2.

The caveat here is that for signed types the value should be non-negative and the resulting value should be representable in the result type. Otherwise the operation is undefined. The result type would be the type of the E1 after applying integral promotion and not the destination (the variable which is going to hold the result) type. The resulting value is implicitly converted to the destination type; if it is not representable in that type, then the conversion is implementation-defined (C99 §6.3.1.3/3).

If E1 is a signed type with a negative value then the behaviour of left shifting is undefined. This is an easy route to undefined behaviour which may easily get overlooked.

Right Shift

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Right shift for unsigned and signed non-negative values are pretty straight forward; the vacant bits are filled with zeros. For signed negative values the result of right shifting is implementation-defined. That said, most implementations like GCC and Visual C++ implement right-shifting as arithmetic shifting by preserving the sign bit.

Conclusion

Unlike Java, which has a special operator >>> for logical shifting apart from the usual >> and <<, C and C++ have only arithmetic shifting with some areas left undefined and implementation-defined. The reason I deem them as arithmetic is due to the standard wording the operation mathematically rather than treating the shifted operand as a stream of bits; this is perhaps the reason why it leaves those areas un/implementation-defined instead of just defining all cases as logical shifts.

In terms of the type of shift you get, the important thing is the type of the value that you're shifting. A classic source of bugs is when you shift a literal to, say, mask off bits. For example, if you wanted to drop the left-most bit of an unsigned integer, then you might try this as your mask:

~0 >> 1

Unfortunately, this will get you into trouble because the mask will have all of its bits set because the value being shifted (~0) is signed, thus an arithmetic shift is performed. Instead, you'd want to force a logical shift by explicitly declaring the value as unsigned, i.e. by doing something like this:

~0U >> 1;

Here are functions to guarantee logical right shift and arithmetic right shift of an int in C:

int logicalRightShift(int x, int n) {
    return (unsigned)x >> n;
}
int arithmeticRightShift(int x, int n) {
    if (x < 0 && n > 0)
        return x >> n | ~(~0U >> n);
    else
        return x >> n;
}

When you do - left shift by 1 you multiply by 2 - right shift by 1 you divide by 2

 x = 5
 x >> 1
 x = 2 ( x=5/2)

 x = 5
 x << 1
 x = 10 (x=5*2)