15

A bit of a philosophical question, I suppose.

The C language has the standard set of bit-wise operations, including OR, AND, XOR, SHIFT LEFT/RIGHT, and NOT. Why aren't rotate left/rotate right operators or functions included in the language?

These operators are of the same complexity as other bit-wise operators and normally require a single assembly instruction, like the others. Besides, I can think of a lot of uses for rotate operator, probably not less than, say, xor operator - so it sounds a bit strange to me that they aren't included in C along with the rest.

If you do need to rotate in C or C++, there's a separate FAQ question about best-practices for it. Discussion of that is off-topic for this question.

Community
  • 1
  • 1
SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
  • 1
    It can be done in assembly with ease. http://stackoverflow.com/questions/776508/circular-shift-operations-in-c – Anirudh Ramanathan Oct 27 '12 at 10:41
  • 3
    @Cthulhu I know that and even wrote that in the question body. The question is about C – SomeWittyUsername Oct 27 '12 at 10:43
  • 1
    Because it had been forgotten? ;-) I like these ones: http://stackoverflow.com/a/12733007/694576 – alk Oct 27 '12 at 10:46
  • I suppose it may have been due to the fact that you are sometimes not entirely sure of the size of different data types in C. Rotation would behave different with a 64 bit integer than it would with a 32 bit one. (I know this also applies to shifts, it would just be more evident with rotations). – Will Oct 27 '12 at 10:47
  • @Cthulhu or you could just use shifts and an OR, every sane compiler detects that pattern anyway and unlike inline asm it won't inhibit optimizations. – harold Oct 27 '12 at 10:48
  • @Will as far as the compiler concerns, the size of the operand is well defined. If the outcome doesn't match the expectations, that would be a bug in the program. – SomeWittyUsername Oct 27 '12 at 11:07
  • @alk: the answer you link to is bogus, there's no evidence of that in the standard drafts (and certainly not in C++11). – Mat Oct 27 '12 at 11:17
  • You are right. Linking such gosip with out qualifing it, is bad manners, sry ... @Mat – alk Oct 27 '12 at 11:27
  • @icepack I wasn't saying that it would be a problem for the compiler. I was merely speculating that it could have been a reason why it was left out of the language specification. Another could be that K & R just forgot :-p – Will Oct 27 '12 at 12:08
  • I suspect the reasons may be political. Rotate left/rotate right make sense on platforms where the length of `unsigned int` is a power of two and contains no padding. It makes less sense on other platforms. For the Standards Committee to define an operation which only makes sense on 99% of C platforms would be to effectively brand the remaining 1% as oddballs. From a technical standpoint, it would be easier for most compilers to include an intrinsic for left/right rotate than to have a peephole optimizer recognize the hundreds (thousands?) of different minimal-complexity ways... – supercat Aug 18 '15 at 16:04
  • ...the expression could be written in strictly-compliant C. It's possible, though, that the decision not to define a standard way to perform left/right rotates was predicated upon an expectation that code needing to rotate `x` left by `y` bits would most likely be written as `(x<>(32-y))`, or the same thing with sides reversed, so peephole optimization wouldn't require any complex semantic analysis. Unfortunately, since around 2009, that simple expression has ceased to be reliable. – supercat Aug 18 '15 at 16:13

2 Answers2

6

I think it's because there are two types of rotations: with and without carry, which makes the rotation to be done differently, according to the resulting machine's CARRY flag (1 or 0). That would imply implementing a total of 4 operators, thus making the language unnecessarily complex, provided that rotation can be simply implemented as @Aniket has shown.

EDIT:

Nevertheless, shifting may also be done signed and unsigned. Actually Javascript has both operators, AFAIK. However, since C supports signed and unsigned variables, I think it has no sense to perform signed shifts, because the compiler should know whether we are shifting a signed or unsigned variable. Signed/unsigned shifts are useful for arithmetical computations, and a C compiler may use them to generate the assembly code. For instance, many arithmetical operations such as multiplying or dividing by a power of 2 are translated by the compiler into shift operations. The only reason we have shift operators in C is for working with bitmasks.

Claudi
  • 5,224
  • 17
  • 30
  • @Claudix I was mostly referring to a rotation operator without carry, but good point. Anyway, `xor` isn't essential as well, as it can be implemented with other operators. – SomeWittyUsername Oct 27 '12 at 11:04
  • Yep, but xor is an unambigous operator. Who knows, maybe the C maintainers noticed that there was no clear dominant convention of how rotation should be done :-) – Claudi Oct 27 '12 at 11:08
  • @icepack then most other operators are not needed either. We can just have 1 operator(NAND) and realize all boolean logic that way – Aniket Inge Oct 27 '12 at 11:08
  • `simply`?! ... it is a word ... but actually it is not so simple – Memos Electron Oct 27 '12 at 11:08
  • I think C performs through operators what can be done at machine level without ambiguity: and, or, xor, not... all of them are unambigous thus implemented as part of the language. – Claudi Oct 27 '12 at 11:10
  • @Aniket Not sure it's enough for shifts and rotations, but basically - yes. – SomeWittyUsername Oct 27 '12 at 11:11
  • @Claudix Not sure what do you mean by ambiguous operator, but for that sake shifting operator isn't different from rotation. – SomeWittyUsername Oct 27 '12 at 11:12
  • Yes, I know. Shifting may be done signed and unsigned. Actually Javascript has both operators, AFAIK. However, since C supports signed and unsigned variables, I think it has no sense to perform signed shifts, because the compiler should detect whether we are shifting a signed or unsigned variable. Signed/unsigned shifts are performed for arithmetical computations, but in C you use to shift for bitmasking (i.e. unsigned shifts). – Claudi Oct 27 '12 at 11:16
  • By the way, shifts in assembly can also use carry, so they're not different from rotation for that sake – SomeWittyUsername Oct 27 '12 at 11:16
  • @icepack: most (all?) CPUs support both logical and arithmethic shifts, and they behave the same provided the shift amount is < word bits. OTOH, some CPUs support only rotate through carry, while others support only rotate without carry. – ninjalj Oct 27 '12 at 12:43
1

C doesn't have rotate-left and rotate-right for binary. You can code rotate left and rotate-right functions yourself. But as per standards: nope.

Simple rotate-left :

int rotate_left(int num, int bits)
{
  return ((num << bits) | (num >> (32 -bits)));
} 

int rotate_right(int num, int bits)
{
  return ((num >> bits) | (num << (32 -bits)));
}

The above functions will work with 32 bit integers only :)

Now for the philosophy: C was meant to be portable as much as possible. That's what the standards team want it to be "a portable assembler". There is no guarantee that rol and ror is present on architectures of the future. Or might behave differently. Hence it was kept away from standards.

Aniket Inge
  • 25,375
  • 5
  • 50
  • 78
  • good.. Better to right it as macro – Grijesh Chauhan Oct 27 '12 at 10:50
  • 3
    good but the actual question is `Anyone has an idea why rotate left/rotate right isn't included in the language? ` – Memos Electron Oct 27 '12 at 10:52
  • @memosdp yes, edited after posting – Aniket Inge Oct 27 '12 at 10:53
  • 4
    @GrijeshChauhan: **no!** – Mat Oct 27 '12 at 10:55
  • @icepack the question was why rol/ror isn't in C. Philosophically(this is the original question). Answer: C was suppose to be a minimal language, it needn't have everything and the kitchen sink. what if the architecture doesn't support rol/ror? – Aniket Inge Oct 27 '12 at 10:58
  • @Mat : No! really!..please give me the reason – Grijesh Chauhan Oct 27 '12 at 10:58
  • @GrijeshChauhan: how do you propose writing that macro in a way that is both portable & doesn't evaluate its arguments twice? – Mat Oct 27 '12 at 10:59
  • @Aniket That's exactly the question. Why `xor` is essential and `rol` isn't? Either include them all or include just the necessary basics that can be used for implementing the rest. – SomeWittyUsername Oct 27 '12 at 11:01
  • 6
    There's a lot of undefined behaviour lurking in that code, left-shifting negative integers is UB, left shifting of signed integers of non-negative value is UB if `value * 2^shift` isn't representable in the type. Right-shifting of negative integers is implementation-defined, and often does sign-extension, so these wouldn't actually rotate. Make them operate on unsigned integers, and your only problem becomes the constraint that the shift distance needs to be non-negative and smaller than the width of the type (`bits &= 31`, and if `bits == 0`, return num). – Daniel Fischer Oct 27 '12 at 11:07
  • Checking `bits &= 31` actually leads to extra instructions, on x86 with gcc 4.9.2: See my comment on http://stackoverflow.com/questions/2835469/how-to-perform-rotate-shift-in-c. It's really annoying when so much behaviour is undefined, mostly because the standard doesn't want to assume 2's complement. – Peter Cordes Jul 12 '15 at 23:24