Newsgroups: comp.lang.c
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 10 Dec 92 23:27:25 GMT
Subject: Re: How to do an efficient ROTATE in C?

mo...@thunder.mcrcim.mcgill.edu (der Mouse) writes:

>raym...@kronos.arc.nasa.gov (Eric A. Raymond) writes:

>> C has those lovely >> and << ops for shifting, but no built in rotate
>> operators?

I generally use (val<<shift)|((val>>(wordsize-shift))&((1<<shift)-1))
and trust the optimizer to fix it (or wish I could trust the
optimizer).

>> Why isn't this part of the language?  Perhaps it's not a common
>> instruction on many CPU's?

>Perhaps because the PDP-11 model(s) used when developing C didn't
>have it?

I'm pretty sure it was in the original PDP11 instruction set.

>Some models do, but I don't know how widespread it is, and the
>ones that do have it rotate by only one bit, through the carry, which
>makes it hard to represent in C.

I'm sure anything in C would be a 16-bit or 8-bit rotate not involving
the carry.  For a multiple bit rotate left, you clear the carry, then
repeatedly rotate left and add the carry.  For a multiple bit rotate
right, you can either simulate with a complementary rotate left, or
you can duplicate the quantity to be rotated, then alternately rotate
the scratch copy and rotate the good copy.  The scratch copy is just
used to set the carry bit.

>> Perhaps it's not that commonly needed as shift?

One thing is that it's relatively more dependent on word size than
shift.  A signed shift doesn't depend on the word size unless it
overflows.  But that's more applicable to a language like Lisp, where
you treat integers as unbounded bit strings (with all but finitely
many of the bits zero or one).

Dan Hoey
Hoey@AIC.NRL.Navy.Mil