?
Solved

Circular Shift?

Posted on 2003-02-22
7
Medium Priority
?
4,089 Views
Last Modified: 2012-05-04
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.
0
Comment
Question by:AI_Agent
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
  • 2
  • +1
7 Comments
 

Expert Comment

by:Fallen_Knight
ID: 8001904
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
 
LVL 11

Expert Comment

by:cup
ID: 8002069
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
 
LVL 12

Expert Comment

by:Salte
ID: 8002863
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:AI_Agent
ID: 8006287
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?

Thanks for your help
0
 

Expert Comment

by:Fallen_Knight
ID: 8006338
& 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
 
LVL 11

Expert Comment

by:cup
ID: 8006804
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
 
LVL 12

Accepted Solution

by:
Salte earned 400 total points
ID: 8007290
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:

   v = (v & ~mask) | (w & mask);

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

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

800 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question