Why is this C arithmetic shift implementation not working?

Question

I'm trying to write a C function that will always find the arithmetic right shift of an unsigned integer argument, using bitwise operators. I managed to write a function that would always find the logical right shift of a signed integer using bitwise operators, but the same idea doesn't seem to be working for finding the arithmetic shift.

Here's my function right now:

unsigned arith(unsigned x, int k) {
    unsigned x_arith = (int) x >> k;

    x_arith = x_arith | ((-1<<(sizeof(x_arith)*8)-k)) & ~(-1<<(sizeof(x_arith)*8));
    return x_arith;
}

Explanation:

(-1 << (sizeof(x_arith)*8-k))

Create an all-1's binary then shift those ones so that the first 1 aligns with the leftmost 1 in x_arth.

& ~(-1 << (sizeof(x_arith)*8))

Create an all-1's binary and shift it so the first one aligns after the leftmost bit in x_arth, then flip it, then keep only those bits in common with the binary above.

This whole process supposedly creates a mask that has 1's where x_arith needs to have ones. Finally, I | (or) the original x_arith with this mask to get the 1's that I need to make the shift arithmetic and return the result.

However, the result is still a logical shift. I tried changing many things in the above code and got really frustrated with the weird numbers I got. What am I doing wrong?

UPDATE: The function posted above does actually find the arithmetic shift. The problem was that I was testing it with 4 and k=1, expecting the result to be 6, which turns out to be not how arithmetic shifting works. Here's a nicer-looking version of the function for future reference:

unsigned arith_shift(unsigned x, int k) {

    unsigned x_arith = (int) x >> k;

    int bits = sizeof(int) * 8;

    unsigned mask = k? ((~0 << (bits-k)) & ~(~0 << bits)): 0;

    return x_arith | mask;

}

Note that you can use both -1 and ~0 for an all-1's binary number. However, this function may behave differently on different machines since the behavior of left-shifting -1 is undefined (see e0k's answer).

Answer 1

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.

Answer 2

You just need to create a mask with k leftmost 1's (if the number was negative), which is the sign expansion done by an arithmetic shift:

unsigned mask = x > 0x8000 ? (0xFFFF << (16-k)): 0;

Then apply the mask to the logical shift result

unsigned x_arith = mask | (x >> k);

Note: I am assuming 16 bit unsigned, otherwise you need to adjust using sizeof(), since this is homework I leave that bit to you