8

Many people frequently point out in discussions of the right-shift operator that the C standard explicitly states that the effect of right-shifting a negative number is implementation defined. I can understand the historical basis for that statement, given that C compilers have been used to generate code for a variety of platforms which do not use two's-complement arithmetic. All new-product development that I'm aware of, however, has centered around processors which have no inherent support for any kind of integer arithmetic other than two's-complement.

If code wishes to perform a floored signed integer division by a power of two, and it is only going to be run for current or future architectures, is there any realistic danger that any future compiler is going to interpret the right-shift operator as doing anything else? If there is a realistic possibility, is there any good way to provide for it without adversely affecting readability, performance, or both? Are there any other dependencies which would justify making an outright assumption of the operator's behavior (e.g. code will be useless on implementations that don't support function X, and implementations are unlikely to support X if they don't use sign-extended right shifts)?

Note: I ask under the C99 and C11 tags because I would expect that newer language features would be among the things which, if supported, would suggest that a platform is probably going to use a right-shift which is arithmetically equivalent to floored division, and would be interested in knowing of any C99 or C11 compilers which implement right-shift any other way.

supercat
  • 77,689
  • 9
  • 166
  • 211
  • And my favorite "idiot test": if even Microsoft does it as expected, then likely it won't go wrong with other compilers. I don't know if MSVC implements this as you expect, though. –  Nov 20 '13 at 17:50
  • 1
    I work almost solely with an MCU that doesn't even have a shift right, so its "implementation" is to break if it's unable to split it into available instructions. It's less about compiler, and more about hardware platform. There are a few MCUs out there that have weird shift right behavior. – Sam Cristall Nov 20 '13 at 17:51
  • 1
    @SamCristall: What MCU doesn't have any kind of right-shift? I've worked on some where arithmetic right shift sometimes costs one or two more instructions than would a logical right shift [depending upon operand size and the shift amount] but the compiler still generates code for arithmetic right shift. On that particular MCU, unsigned comparisons are faster than signed comparisons, so time-critical code avoids using signed numbers unnecessarily; if one is right-shifting a signed number, there's often a reason. – supercat Nov 20 '13 at 18:00
  • @supercat DSPs in particular, see my answer for more on that. The MCU I'm referring to *can* put out an equivalent, but in some cases its so horrendous that its better just to error and tell the programmer. This is in a small embedded system (<32kB RAM) – Sam Cristall Nov 20 '13 at 18:08
  • 7
    It is a mistake to think “Well, processors all shift this way now, so future C implementations will shift the same way” because compilers are increasingly treating the language abstractly. Writing operators like `>>` and `+` do not specify processor instructions to use; they specify operations in an abstract machine. When the compiler translates the abstract machine language into actual code, it may implement only the features specified for the abstract machine. In particular, when optimization is applied, unspecified behavior of the abstract machine may be transformed into **anything**. – Eric Postpischil Nov 20 '13 at 18:15
  • In practice, compiler writers consider what code people actually write, and they may design the compiler to go beyond the language specification. So, if they consider right-shift of negative numbers to be important behavior, they may design the compiler to treat it as a specified operation. But compiler writers are also pushed for efficiency in generated code, which causes them to want to be able to transform input source code into any legal output code that satisfies the specification. So, in the absence of a specification, you cannot rely on compiler writers preserving the behavior of `>>`. – Eric Postpischil Nov 20 '13 at 18:19
  • @EricPostpischil: How would you suggest that code should perform a division by a power of two, if code will rely upon the `(n+d)/d == (n/d)+1`, which holds for both natural numbers and real numbers, also holding with the values one is using? I know of no nice formulation for power-of-two division except using signed shift, and no non-ugly formulation for non-power-of-two division [the best approach I can figure for the latter is add (UINT_MAX/d)*d, do the division as unsigned, and then subtract (UINT_MAX/d); I'd rather avoid such constructs when possible, and for powers of 2 it could be. – supercat Nov 20 '13 at 18:38
  • The Transputer's right shift instruction was microcoded as a loop equivalent to `do { value >>= 1; } while (--count);`. The predecrement meant that if you tried to shift by 0, it ended up iterating 2^32 times... with interrupts off. It'd take days. – David Given Nov 20 '13 at 20:13
  • @DavidGiven: I remember reading about that; I'm pretty sure that a 32-bit machine I'm pretty certain right-shifts between 0 and 31 *inclusive* are supposed to work, though having -1 loop 2^32-1 times would be legitimate. In any case, the question was about cases where a negative value is right-shifted a positive amount. – supercat Nov 20 '13 at 20:58
  • @supercat Yes, I really just brought it up for interest (the Transputer wasn't really designed for C anyway; I assume that the compiler would have to generate an explicit check for >>0). There's usually a reason for all the weird undefined behaviour in C, even if it is pretty archaic. – David Given Nov 20 '13 at 21:28
  • If your goal is to do portable floored signed integer division then [see here](http://stackoverflow.com/questions/4102423/efficiently-implementing-floored-euclidean-integer-division). – M.M Feb 06 '15 at 01:41

2 Answers2

3

This is just one of many reasons why this is so, but consider the signal processing case:

1111 0001 >> 1
0000 1111 >> 1

In the form of shift right arithmetic (SRA) you refer to you would get the following:

1111 0001 >> 1 = 1111 1000
OR
-15 >> 1 = -8

0000 1111 >> 1 = 0000 0111
OR
15 >> 1 = 7

So what's the problem? Consider a digital signal with an amplitude of 15 "units". Dividing this signal by 2 should yield equivalent behavior regardless of sign. However, with a SRA as above, the positive signal of 15 would result in a signal with 7 amplitude, while a negative signal of 15 would result in a signal with 8 amplitude. This unevenness results in a DC bias in the output. For this reason, some DSP processors choose to implement a "round to 0" shift right arithmetic, or other methods altogether. Because the C99 standard is worded as it is, these processors can still be compliant.

On these processors, -1 >> 1 == 0

Related Wiki

Sam Cristall
  • 4,328
  • 17
  • 29
  • Both natural numbers and real numbers define only one form of division, and it upholds the axiom that for any values n and d, (n+d)/d == (n/d)+1. Real-number division also upholds the axiom that (-n)/d == -(n/d). Integer division can be defined so as to uphold one axiom or the other, but not both. If one has a signal which happens to swing from -7 to +7 (a swing of 14), floored division by two will make it swing from -4 to +3 (i.e. reduce it by exactly half), while truncated division will reduce its swing to six. – supercat Nov 20 '13 at 18:26
  • If one wishes to avoid a DC bias, biasing the input of what would otherwise be a floored division by either d/2 or d/4 will eliminate much of it; applying such bias it correctly when using truncated division is usually not much easier than adjusting the operand to be positive. I can't think of any DSP support I've ever seen for a shift that behaves like a truncated division. – supercat Nov 20 '13 at 18:52
  • With regard to the Wiki, the idea that `x>>1` doesn't divide negative numbers by two depends upon what such division is supposed to mean. If one views the extension of the natural numbers to integers as attaching a mirrored copy of the whole numbers to the left of zero, then the meaning of division by things on opposite sides of zero is rather vague. If one views the extension as "for every integer X (*including zero*), X-1 is an integer", then the natural-number axiom should clearly apply. – supercat Nov 20 '13 at 19:05
1

Theoretically, nowadays there are subtleties in compiler implementations that could abuse the so-called "undefined behavior", beyond what the backend cpu would do to the actual integers on registers (or "files" or memory locations or whatever):

  1. Cross compilers are usual stuff: the compiler may abuse implementation dependent specs when executing simple calculations itself. Consider the case where the target architecture implements this one way and the hosting the other. In your particular example, compile-time constants could end up as 1, even if whatever assembly output in the target architecture would otherwise gives 0 (I can't think of no such architecture). And then again, vice-versa. There would be no requirement (other than user-base complaining) for a compiler implementer to otherwise care.

  2. Consider CLANG and other compilers that generate intermediate abstract code. There's nothing preventing the type mechanics to optimize some operations up to the last bit at intermediate time on some code paths (i.e. when it can reduce code to constants, loop folding comes to mind), while leaving the assembly backend to resolve this at runtime in other paths. In other words, you could see mixed behavior. In this kind of abstract, there's no obligation from the implementer to obey any standards other than whatever the C language expects. Think the case where all integer math is done by arbitrary precision arithmetics libraries instead of direct mapping to the host cpu integers. The implementation may decide for whatever reason that this is undefined and would return 0. It can do so for any of the signed arithmetic undefined behavior, and there's lots of then in the ISO C standard, specially the wrapping and such.

  3. Consider the (theoretical) case where instead of emitting the full instruction to do the low-level op, the compiler hijacks a sub-operation. An example of this is the ARM with barrel shifter: an explicit instruction (i.e. add or whatever) could have a range and semantics, but the sub-operation could operate with slightly different limits. The compiler could exploit this up to limits where behavior could differ, for instance one case can set result flags and the other not. I can't think of a concrete case where it matters, but it's a possibility that some weird instruction can only deal with subsets of "otherwise normal behavior" and the compiler may assume it's a nice optimization since undefined behavior is supposed to really means undefined :-)

Apart from weird architectures where you would actually have weird behavior at runtime, these are some of the reasons I can think of why you can't assume anything beyond the undefined behavior.

Having said all that, however, we must also consider:

  1. You asked for a C99 compiler. Most weird architectures (i.e. embedded targets) don't have a C99 compiler.
  2. Most "large scale" compiler implementers deals with very large user code bases and generally speaking face support nightmares by over-optimizing minor subtleties. So they don't. Or they do it the way other players are doing.
  3. In the particular case of signed integer "undefined behavior", normally the complementary unsigned operation is a defined operation, i.e. I've seen code casting signed to unsigned only to do the op and then casting the result back.

I think the best straight answer I could give is "you might assume all this is irrelevant, but perhaps you shouldn't".

Alexandre Pereira Nunes
  • 1,068
  • 13
  • 22
  • I would expect that a decent cross-compiler should evaluate compile-time constants using the same rules of arithmetic as the code it generates for the target system, regardless of what the host system would otherwise use. I think my main point is that the rationale for C leaving vagueness about things like right-shift is to avoid making people pay for what they don't need, but if C99 implementations mostly run on hardware where arithmetic right shift costs the same as logical right-shift, and on those few implementations where it doesn't compiler vendors generate the code... – supercat Feb 05 '15 at 22:12
  • ...to sign-extend `int` values which are shifted right, does the vagueness offer any benefit to anyone that would offset the cost of forcing programmers to write constructs like `(int)((n ^ 0x80000000u) >> 4)-0x8000000`? – supercat Feb 05 '15 at 22:16
  • I honestly don't know what's the rationale the C committee uses for demoting signed integer like that. And then Sun came and made java with *only* signed integers. They're trying to make us mad. – Alexandre Pereira Nunes Feb 05 '15 at 23:46
  • The unsigned integer semantics of C are truly horrible because the language can't decide whether they're numbers or members of a wrapping abstract algebraic ring of numbers congruent mod 2^n. The behavior of `uint32+int32->uint32` makes sense if they're members of an abstract algebraic ring, but type promotion only makes sense if they're numbers. I don't mind Java's decision not to support C's horrible unsigned mess, though it should have included unsigned 16-bit and 8-bit quantities since there's no ambiguity about how they should behave. – supercat Feb 06 '15 at 00:12
  • @supercat explain what you mean by "type promotion only makes sense if they're numbers" . Nothing promotes to unsigned int (except on DSPs) – M.M Feb 06 '15 at 01:37
  • @MattMcNabb: Suppose two 16-bit hardware registers reports the number of "moved left" and "moved right" pulses received on some input, mod 65536, and one can guarantee that no more than 65535 pulses will be received between polling events. The reported count values should be considered members of a wrapping algebraic ring. If on the previous polling cycle one register read 65534 and on the current one it reads 3, that means it received 5 counts, not -65531. On the other hand, if one computes in `uint16_t` variables the number of clicks something moved right and left... – supercat Feb 06 '15 at 16:23
  • ...and then wants to update a 32-bit current position, then if there were 3 right moves and 5 left moves, the position should be adjusted by -2, not 65534; the number of left/right pulses received on the most recent cycle should be viewed as a cardinal number. The statement `someLong += someUInt16 - anotherUInt16` will behave as though the subtrahends are members of an algebraic ring on machines where `int` is 16 bits, and as though they are cardinal numbers on machines where `int` is longer. Does that example clarify things? – supercat Feb 06 '15 at 16:33
  • @MattMcNabb: If I were designing a language, operations between a ring member and a number would yield a member of the same ring, and implicit conversion from a number to a ring would add that number to the ring's zero. Operations between members of different rings, or implicit conversions from ring members to numbers, would be forbidden. Thus, the aforementioned `some32bitThing += someRing16 - anotherRing16` would refuse to compile unless the right-hand side was rewritten to be unambiguous: either `(int16)(someRing16-anotherRing16)` or `(cardinal16)someRing16-(cardinal16)anotherRing16`. – supercat Feb 06 '15 at 16:38
  • @supercat that's nice but not really relevant to C . You'd end up with some mess like Java where normal code has to have casts all over the place because there is no implicit conversion. – M.M Feb 06 '15 at 21:33
  • @MattMcNabb: If types were implemented as I'd like to see them, one would mostly end up needing casts at places *where different C compilers presently do different things*. If compatibility with existing code weren't required, I'd rather have `someUInt32 += firstUInt16-secondUInt16;` refuse compilation than have it perform different computations on different machines. Further, there are many cases where overflow checking would be desirable and worth the runtime cost if there were a way to distinguish overflows that should be flagged from computations which should simply wrap. – supercat Feb 06 '15 at 22:22
  • @supercat maybe you can move to C++ where you can indeed write code that does what you want – M.M Feb 06 '15 at 22:59
  • @MattMcNabb: Unless a language allows compile-time constants of user-defined types (I don't think C++ does), I don't see any good substitute for a having a robust numerical type system built into the compiler. At present, there are at least three major dialects of C: "C with 16-bit `int`" (still popular in the embedded world), "C with 32 bit `int`" (currently the most popular), and "C with 64 bit `int`". I'd like to see a language which would make it easy to write code that would work correctly on all three platforms while using the optimal variable size on each. – supercat Feb 06 '15 at 23:14