# Circular Shift?

Ok. What is a circular shift? How does it work? Is there some code I can look at that will implement it? I've been reading some papers that just *ASSUME* the reader knows what it is and how to do it and I'm lost.

Anyone who can give me a decent explanation and some decent code will get some decent points ;) I'm putting it at 100 now, but I'm prepared to increase it by at least another hundred for something that really makes me feel like I understand it and can use it in my programs.
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
i'm not 100% sure if what i've been taught as a circular shift is the same the papaers your reading but heres how i understand it:

a circular right shift is the following:
A = 00001111
A >> 1
A = 10000111

so the bit shifted out is replaced on the otherside of the number. in ASM its shifted to a carry bit and the carry bit is shifted in.

so to implement a circular shift right
find out what the right most bit is and save that.
shift the number right by one.
take the saved bit and | it into the left most posistion.

There might be an easy way to do that in C but i don't know it. so heres my hard way:) thou untested.

int a = 0x0F;
int b = 0;
b = a & 0x80;
a = a >> 1;
a = a | (b >> 31);

a has now been circular shifted right.

Hope that helps (and that i'm right!)
0
Commented:
A normal shift shunts one bit off the end.  A left shift will move all the bits one position to the left and lose the top bit, a right shift will move all the bits one position to the right an lose the bottom bit.

In a circular shift, instead of using a 0 for the new bit, the 'lost' bit is used.  So

00001111 right circular shift becomes 1000111
11110000 left circular shift becomes 11100001

Some machines have a 'with carry' circular shift.  These next to impossible to implement purely in C.  The 'lost' bit goes into the carry and the carry bit is used as the shunt.

C=1 10101010 right circular shift with carry becomes C=0 11010101

Circular shift with carry is useful for multiplication in multiple precision arithmetic.  How you do a circular shift depends on your word size.  A left circular shift of cshift would be

#define WORDSIZE 16
cshift = ((cshift & (1 << (WORDSIZE - 1))) >> (WORDSIZE -1)) | (cshift << 1);

A right circular shift would be
cshift = ((cshift & 1) << (WORDSIZE - 1)) | (cshift >> 1);

The code generated is of course horrendous (how do you spell that horrible word).  Some machines have built in circular shifts in assembler.

WARNING WARNING WARNING: make sure you always deal with unsigned integers.  I've been caught out by this several times.  With signed integers, an arithmetic shift will be used and has a different result.  Again, assuming 16 bit words (too much to type for 32 bits)

short x = 0x8000;
short y = x >> 1;

On some machines y=0x4000 - that is a logical shift.  On some machines y=0xC000 - that is an arithmetic shift.  The arithmetic shift always retains the ms bit.  However, if both x and y are unsigned, you will always get 0x4000.

Another warning.  On some machines

1 << 8 = 0

That is because 1 is treated as an unsigned char which is 8 bits so 1 << 8 shifts it off the end.  To get around it, cast 1 to the required entity i.e.

((unsigned long) 1) << 32

This doesn't always happen but run a few experiments first to know what your compiler does.  You may assume something but the compiler may do something completely different even though it claims to be ANSI C++.
0
Commented:
is "circular shift" the same as "rotate"?

If so it is a simple manner of shifting and oring:

unsigned int x;

unsigned int y = (x << 27) | (x >> 5);

if sizeof(int) == 4 (32 bit int) then y will be a rotate right by 5 bits (same as rotate left by 27 bits).

If sizeof(int) == 2 a rotate right by 5 bits is instead:
unsigned short int y = (x << 11) | (x >> 5);

Be careful if you have signed variables on input:

int x;
int y = (x << 27) | ((x >> 5) & 0x7ffffff);

will do a rotate of 32 bit int. The & is necessary since otherwise you would get the sign bit copied and if x was negative that would get the wrong result.

Is this what is meant by "circular shift"?

Alf
0
Author Commented:
Cup, yours was very informative but I'm still a little confused about some things...

I dont fully understand what the & and | do. I know they are bitwise 'and' and 'or' and I know, conceptually, what they are supposed to do but how do those work to create a circular shift?

I actually did a little more looking on my own and found this version of a circular shift:

( (v>>b) | ( v<<(32-b) ) );

where v is the value to be shifted by b bits. I assume that this code assumes a 32 bit number? The code is different but whats the difference in the way it affects the bits?

0
Commented:
& does a logical and between 2 numbers, example:
00001111 & 00111100 = 00001100

| does a logical or:
00001111 & 00111100 = 00111111

and yes, that assumes a 32bit number
0
Commented:
Circular shift is the same as rotate; Intel instructions being ROR and ROL.  The version with carry is RLC and RRC.

An example of how it works.  This is a left shift/rotate.  Take a pattern

x = 99; // binary 10011001

Take out the top bit

top = x & 1000000; // top = 1000000

Shift the top to the bottom

top = x >> 7;  // top = 00000001

Shift x on position left

x = x << 1;   // x = 00110010

Or x and top to achieve the result

x = x | top;  // x = 00110011
0
Commented:
How does (v << b) | (v >> (32 - b)) create a circular shift or rotate operation? Here is how:

I will consider circular right shift, the circular left shift is identical but with left/right and high/low bits swapped. I.e. when I below say "b high bits" for a right rotate it would be the "b low bits" for a left rotate.

In a circular shift you shift right b bits, those b high bits will be dropped from the high position, since bit in position (32-b-1) becomes the bit in position (32-1) and so on. Bit 0 moves to position b.

(v << b) does that kind of shift.

The bits in position 0 to b-1 all becomes 0 in a right shift. In a rotate they instead get the bits that used to be the high bits. That is, bit (32-b) moves to bit 0, bit 32-b+1) moves to bit 1 etc to bit 31 which moves to bit b-1.

(v >> (32 - b)) almost does that operation. If v is unsigned it will do that operation in that bit the bits in those positions moves to positions 0 to b-1 and bits b..31 all becomes 0. If v is a signed data type this shift will instead do an arithmetic shift and those bits will all copy the sign bit instead, so they all become equal to the bit that used to be in position 31 (sign bit) but is now moved to position b-1. Thus all the bits at position k where k >= b are now equal to the bit in position b-1.

Clearly it is better for us to keep them all 0. One way to do that is to cast the data type to an unsigned type. One can also get them all zero by AND the resulting integer value with a value where all those bits from position b to 31 are all 0 but this require an extra AND operation.

So  (static_cast<unsigned int>(v) >> (32-b)) will produce a word with bits b..31 all 0 and bits 0..b-1 equal to the old bits 32-b..31.

Now, to make the rotate all we have to do is combine those two:

w = (v << b) | (static_cast<unsigned int>(v) >> (32 - b));

Now if we let w[k] mean bit k in w and w[i..j] mean bit i through j (both inclusive) of w then we have:

w[0..b-1] == v[32-b..31]
w[b..31]  == v[0..31-b]

And w is a rotate right by b bits of v.

If v is already unsigned int then we don't have to do that static_cast and so it becomes simply:

w = (v << b) | (v >> (32 - b));

The | operation does a bitwise OR, so that you combine two patterns:

(0xab00 | 0x00cd) == 0xabcd
(0xa0c0 | 0x0b0d) == 0xabcd also

This way you can merge bits. However, it is usually a good idea to make sure that the position where one operand has 'significant bits' is such that the other operand has all 0 bits in that same position.

You can maks away bits and force bits to zero by the & operation:

(0xabcd & 0xff00) == 0xab00
(0xabcd & 0xf0f0) == 0xa0c0

Some times it is also useful to use the ~ operand, it toggles the bits, those that were 0 becomes 1 and those that was 1 becomes 0:

~0x0f0f00ff == 0xf0f0ff00
~0xabcdef43 == 0x543210bc

So if 0x00ffe000 is a mask that indicate some bits.
then ~0x00ffe000 == 0xff001fff is the mask of the other bits, so therefore you can often see things like:

What goes on here?

if v is an integer that holds some flags, then v & ~mask is the old flags anded with a mask that is the opposite of 'mask', i.e. those bits in mask which is 1 becomes 0 in ~mask and are the bits we toss away while those bits in mask which is 0 becomes 1 in ~mask and are the bits we keep. In w we mask away all bits except those that are 1 in mask so we only keep the bits in mask.

When these are combined they have the effect of having all bits in v kept except those specified by mask which takes their new value from w.

if v is 0xabcd1234 before the operation and mask is 0x00ff0f0f and w is 0x6789abcd then we get:

w & ~mask == 0x6789abcd & ~0x00ff0f0f == 0x6789abcd & 0xff00f0f0 == 0x6700a0c0

v & mask == 0xabcd1234 & 0x00ff0f0f == 0x00cd0204

These two combined becomes:

(v & mask) | (w & ~mask) == 0x00cd0204 | 0x6700a0c0 == 0x67cda2c4

Do you see how the result is a combination of v and w and how the combination is done is determined by the mask?

Hope this is of help.

Alf
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.