# Rotate array problem

Discussion in 'Programmer's Corner' started by Art, Jul 7, 2009.

1. ### Art Thread Starter Distinguished Member

Sep 10, 2007
797
61
Hi Guys,
This is a function that can rotate a 256 element array:

Problem is it rotates in the wrong direction.
Anyone want to have a crack at the other direction?
No matter what I try I break it.

I realise I can just replace the 1 for 255 and use this for the same effect
as the other direction, but that takes too much time for the application.
Cheers, Art.

2. ### THE_RB AAC Fanatic!

Feb 11, 2008
5,435
1,305
Here are 2 simple systems, they circular rotate the data either way. The rotation has been kept as simple as possible and the last array element
is manually held in dat and restored at the end. There's plenty of other
ways to do it, but these are basically a mirror image of each other so
you might find them easy to understand.

Code ( (Unknown Language)):
1.
2. // rotates array data right (up)
3. unsigned char i;
4. unsigned char dat;
5.
6. i=0;
7. dat = colours[0];
8. while(--i)
9. {
10.     colours[i+1] = colours[i];
11. }
12. colours[1] = dat;
13.
14.
15. // rotates array data left (down)
16. unsigned char i;
17. unsigned char dat;
18.
19. i=0;
20. dat = colours[1];
21. while(++i)
22. {
23.     colours[i] = colours[i+1];
24. }
25. colours[0] = dat;
26. [/i][/i]

Last edited: Jul 15, 2009
3. ### RiJoRI Well-Known Member

Aug 15, 2007
536
26
Some compilers will not do this as desired:
Code ( (Unknown Language)):
1. i=0;
2. while(i--)
They will (should? ) test i before decrementing it -- which is, after all, what you are telling it to do. The code also assumes a char is an 8-bit value.

A better way would be
Code ( (Unknown Language)):
1. for(i = 0; i < 256; i++)
This way it is quite plain what you are trying to do.

And don't forget, marketing is going to want to change the colour array to 300 entries in a few years. Searching for all occurrences of 256 is going to be A Real Pain.

--Rich
(Burnt by C)

4. ### Mark44 Well-Known Member

Nov 26, 2007
626
1
Neither Rich nor THE_RB mentioned this, but your outer loop executes only once. Surely you didn't intend that. Here is your code, unchanged except that I formatted it for better readability.
Code ( (Unknown Language)):
1.
2. int ii, jj;
3.
4. for (ii = 1; ii <=1; ii++)
5. {
6.     for (jj = 256-1; jj > 0; jj--)
7.     {
8.         colours[jj-1] = colours[jj-1] + colours[jj];
9.         colours[jj] = colours[jj-1] - colours[jj];
10.         colours[jj-1] = colours[jj-1] - colours[jj];
11.     }
12. }
13.

5. ### Art Thread Starter Distinguished Member

Sep 10, 2007
797
61
Thanks for the replies
Yeah, the constant 1 can be a variable that determines how many places to shift.

6. ### THE_RB AAC Fanatic!

Feb 11, 2008
5,435
1,305
A good point, but I believe you are wrong. In C the compiler will perform the expression first, before evaluating it. That is if the compiler conforms to C rules which it should.

Yeah I hear you there, a for() expression is the standard way to do it. But the while() expression compiles to a lot smaller and faster code, something i've been made very aware of lately since my C coding these days is mainly for low level PIC micros where every uS counts.

When the original poster mentioned "takes too much time for the application" I assumed execution time was critical and stripped the code to the very fastest and minimal code I could think up in 2 minutes.

7. ### RiJoRI Well-Known Member

Aug 15, 2007
536
26
From: http://docs.hp.com/en/B3901-90007/ch05s09.html

As to the for/while question, I usually check the output of the compiler to see which, if either, is faster. A possible reason for sluggishness is the arithmetic contortions the OP is going through in the loop. I'd look to see if using pointers was better, or maybe strcpy().

--Rich

8. ### Mark44 Well-Known Member

Nov 26, 2007
626
1
Rich is right on the mark here. Not to pile on here, but for the post-decrement expression i--, the compiler generates code that evaluates the expression (an expression doesn't get performed), and after that decrements the variable.

Jul 17, 2007
22,183
1,729
10. ### THE_RB AAC Fanatic!

Feb 11, 2008
5,435
1,305
Whoops my apologies Rich, you are right I should have typed;

while(--i)
and
while(++i)
(I fixed it now with an edit)

I do understand pre and post incrementing but that typo slipped past me, which was why I was defending the fact that it performs the ++i increment expression first before being evaluated by the while() expression.

Nice link Sgtwookie. Still the best way to handle a circular array is still to leave the data where it is and reference it by a pointer. How often do you actually NEED to rotate the data in a circular array?