4

Apparently, the behaviour of the right shift operation:

a >> b

is undefined in C and C++ when b >= sizeof(a)*CHAR_BIT (whereas in the normal case, the "new bits" introduced from the left due to the right shift are equal to zero).

Why is this undefined behaviour better than setting the result to zero when b >= sizeof(a)*CHAR_BIT?

8
  • 4
    Because there are platform specfic details like I explain here such as the size of the shift register which may make it difficult to standardize one behavior because it may be inconvenient to implement on some platforms. Mar 19, 2015 at 2:33
  • what about negative values? does right shift -1 bit same as left shift 1 bit? if you are sure your ISA can do it efficiently, you are better off just use intrinsics to force compilier to use that instruction to implement bit shift operators. Mar 19, 2015 at 2:40
  • 3
    @sje397: C++ 2011 Section 5.8 Shift Operators Paragraph 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.
    – Bill Lynch
    Mar 19, 2015 at 2:51
  • 2
    @user3528438: Shifting by a negative value is also undefined.
    – Bill Lynch
    Mar 19, 2015 at 2:52
  • 1
    @user3528438: There is a difference between implementation defined behavior and undefined behavior. And this is undefined behavior. I quoted the relevant line in an earlier comment. In C 2011 you can also find basically the exact same line as well.
    – Bill Lynch
    Mar 19, 2015 at 3:13

2 Answers 2

6

We can get an idea of why languages choose undefined behavior from Why Language Designers Tolerate Undefined Behavior and it says:

This answer came from two general design principles behind C:

  1. The language should impose no unnecessary overhead on the implementation.
  2. It should be as easy as possible to implement C on a wide variety of hardware.

in this specific case what happens when we use a shift count larger than the bit width will depend on the architecture for example as I explain in my answer here:

on some platforms the shift count will be masked to 5 bits for example on an x86 architecture we can see the Intel® 64 and IA-32 Architectures Software Developer’s Manual section SAL/SAR/SHL/SHR—Shift in the IA-32 Architecture Compatibility section says:

The 8086 does not mask the shift count. However, all other IA-32 processors (starting with the Intel 286 processor) do mask the shift count to 5 bits, resulting in a maximum count of 31. [...]

So implementing shift for an arbitrary count may be burdensome on some platforms and therefore it is better to leave it undefined behavior.

Why not unspecified behavior

If we look at the Rationale for International Standard—Programming Languages—C it says:

Unspecified behavior gives the implementor some latitude in translating programs. This latitude does not extend as far as failing to translate the program, however, because all possible behaviors are “correct” in the sense that they don’t cause undefined behavior in any implementation.

So there must have been a case or still exists a case where the behavior is not correct and would have bad issues.

2
  • 1
    This is a good answer, but I'd appreciate details on why choose undefined behavior rather than unspecified behavior (i.e. the result will have some value, but no velociraptors are involved) .
    – sbabbi
    Mar 19, 2015 at 8:43
  • @sbabbi: Making it undefined behavior means that a compiler can optimize int shift(int v, int n) { if (n >= 32) v=0; return v<<n;} by eliminating the first if(n>=32) v=0;, regardless of what the processor will do with the request, since if n is 32 or larger the C standard says the compiler can do whatever it wants.
    – supercat
    Apr 17, 2015 at 23:45
3

Example to why is this undefined behavior better than setting the result to zero.

Typically a CPU has a single instruction that does the shift. If that instruction was required to compare against an upper bound, that would take more circuitry and slow the shifting. Instead, many CPUs' simply use the Least Significant Bits of the shift to determine how much to shift.

// Example - not specified behavior  (assume 32-bit int)
y = 1 << 34;
// same as 
y = 1 << 2;

The first PCs used an 8/16 bit processor that used the least 8 bits to determine the shift, so it indeed would shift in zeros once the shift count was more than the `int width, yet less than 256. The problem with this was that each shift took 1 clock tick. So in a worst-case, the simple shift command could take 255 clock ticks to perform. Of course, after 16 ticks, nothing but 0 were shifted. This long worst case instruction was not interruptible! Thus making that processor's worst case Interrupt latency far worst than the competition. Intel did not make this mistake again.

7
  • I thought that even on the 80386 which added a barrel shifter for most shift/rotate instructions, the rotate-through-carry instructions behaved iteratively and did not mask the lower bits the way the barrel-shifter-based instructions do.
    – supercat
    Jun 1, 2015 at 5:55
  • @supercat See css.csail.mit.edu/6.858/2014/readings/i386.pdf "3.4.4.1 Shift Instructions" --> "Only the low order 5 bits of CL are used." For Rotate Through Carry, the shift is only 1 bit. Should code mask the lower bits of the shift or not isn't a function of the 386's instructions. It is a function of the compiler. A compiler could not mask, as you suggest or it could mask as I suggest. The C spec allows either. A good compiler will limit the shift count somehow, else a simple x = some_large_value(); y >> x; would take an excessive about of time. Jun 1, 2015 at 14:43
  • I must be misremembering something in that regard, though maybe there was incompatibility in the way different machines handled RRC and RLC on 8- and 16-bit operands. I do remember I never liked Intel's ignoring of the upper bits of shift amounts. On machines that allow it, computing the upper half of a word left-shifted by some amount via upper = dat >> (WORDSIZE-amt); is unlikely to be any slower than upper = dat >> (WORDSIZE-amt-1) >> 1;. Maybe some compilers could optimize the latter into the former, but it would be better yet if there were standardized intrinsics which...
    – supercat
    Jun 1, 2015 at 15:45
  • ...meant "yield a result equivalent to shifting the operand by one bit, (unsigned)N times"; compilers could then take advantage of whatever architectural features a particular platform supported to achieve that.
    – supercat
    Jun 1, 2015 at 15:47
  • @supercat As C does not have a rotate operand nor any any concept of "carry bit", the best a platform can do is provide its own 1) rotate(var, shift), 2) int shift_with_carry(car, shift, carry_in) 3) shift_right(var, shift) that considers range outside int width 4) etc. for unquestioned access to that platform's nifty shift variants. Or course that may need an alternative standard code for portability. I suspect C's undefined behavior for large shifts is precisely to cope with the wide variety of hardwares' variant shifts operations and the flags they set. Jun 1, 2015 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.