473,326 Members | 2,110 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

circular shift array

Hi,

What is a simple way to shift the elements in an array, circularly? Is
there a way to do it so that you don't need a separate storage array?

IE I want to shift array A{1,2,3,4,5,6,7,8} by 3 to the right. The result
would be B{6,7,8,1,2,3,4,5)

Thanks!
B

Jul 31 '07 #1
2 10906
On Jul 31, 8:10 am, "Bint" <b...@csgs.comwrote:
Hi,

What is a simple way to shift the elements in an array, circularly? Is
there a way to do it so that you don't need a separate storage array?

IE I want to shift array A{1,2,3,4,5,6,7,8} by 3 to the right. The result
would be B{6,7,8,1,2,3,4,5)

Thanks!
B
In addition, sometimes shifting might not be required, like shifting 8
times on your array gives the same result, so have some kind of logic
like the following,

int no_of_shifts;
no_of_shifts = shift%n;
if(no_of_shifts == 0) return; /* No need to shift */
else if (n <= no_of_shifts/2) right_shift(no_of_shifts);
else left_shift(no_of_shifts);

Jul 31 '07 #2
On Mon, 30 Jul 2007 22:10:30 -0500, Bint wrote:
Hi,

What is a simple way to shift the elements in an array, circularly? Is
there a way to do it so that you don't need a separate storage array?

IE I want to shift array A{1,2,3,4,5,6,7,8} by 3 to the right. The result
would be B{6,7,8,1,2,3,4,5)

Thanks!
B
Well, as others have said, the best way is to avoid the need for shifting.
If you can't, the code below works, I believe. The basic idea is that to
shift n by s you do gcd(n,s) loops which shift a loop round, eg to shift
6 by 4 the loops are 0->4->2->0 and 1->5->3->1.
The code below uses two objects worth of storage for a shift count other
than 1. Could it be done with one objects worth?
If you are going to make heavy use of such a routine for a fixed type
you might want to make a specialised version, where you use assignment
rather than memcpy.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* !! b <= a */
static int gcd( int a, int b)
{
int c;
while ( (c = a % b) != 0)
{ a = b; b = c;
}
return b;
}

static void cshift_r( int nelt, size_t size, void* base, int ns, char* buff)
{
char* b = base;
if ( ns == 1)
{ memcpy( buff, b+(nelt-1)*size, size);
memmove( b+size, b, (nelt-1)*size);
memcpy( b, buff, size);
}
else
{
char* bs[2];
int nloops = gcd( nelt, ns);
int i, iw, p;
bs[0] = buff; bs[1]=buff+size;
for( i=0; i<nloops; ++i)
{ memcpy( bs[0], b+i*size, size);
for( p=0, iw=(i+ns)%nelt; iw != i; iw=(iw+ns)%nelt, p^=1)
{ memcpy( bs[p^1], b+iw*size, size);
memcpy( b+iw*size, bs[p], size);
}
memcpy( b+i*size, bs[p], size);
}
}
}
/* circularly shift the nelt block (of objects of size size)
** staring at base by ns (positive means rightwards)
*/
void cshift( int nelt, size_t size, void* base, int ns)
{
int s;
char* buff;
if ( nelt<0 || size==0 || ns == 0)
{ return;
}
if ( ns 0)
{ s = ns % nelt;
if ( s == 0)
{ return;
}
}
else if ( ns < 0)
{ s = (-ns) % nelt;
if ( s == 0)
{ return;
}
s = nelt-s;
}
if ( (buff = malloc( (s==1 ? 1 : 2)*size)) == NULL)
{ exit( EXIT_FAILURE);
}
cshift_r( nelt, size, base, s, buff);
free( buff);
}

Jul 31 '07 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Bob Jenkins | last post by:
I have this cute data structure that I just found a second opportunity to use. I googled for references to it, but came up empty. I probably just don't know its name. The algorithm on this...
3
by: Simon Johnson | last post by:
Is there an inbuilt circular shift operator in c#? I've googled it but because c# happens to be musical note.. i get a large noise to signal ratio :P Simon.
2
by: Alberto | last post by:
I need a listview where the user can select the items with the arrow keys but I also want that it works in a circular way: if you are in the first item and press key up, the last item is selected...
23
by: Rogers | last post by:
I want to compare strings of numbers that have a circular boundary condition. This means that the string is arranged in a loop without an end-of-string. The comparaison of two strings now...
11
by: Kenneth Lantrip | last post by:
Anyone got any ideas as to how this process could be improved for speed? this is what I have... Dim j, q As Integer Dim x(16), y(16) As Byte x.CopyTo(y, 0) ' shift left circular 24 bits
10
by: avsrk | last post by:
Hi Folks I want to create a circular queue for high speed data acquistion on QNX with GNU C++ . Does any one know of efficient ways either Using STL or in any other way . I am thing of ...
4
by: sandhya | last post by:
Hello Folks, i hava a problem in coding of circular left shift of 25 bits in my program...how do i perform it, and how do i use unsigned in VB. My program (IDEA algorithm implementation in VB) ...
7
by: toton | last post by:
Hi, I want a circular buffer or queue like container (queue with array implementation). Moreover I want random access over the elements. And addition at tail and remove from head need to be low...
7
by: Bint | last post by:
Hi, What is a simple way to shift the elements in an array, circularly? Is there a way to do it so that you don't need a separate storage array? IE I want to shift array A{1,2,3,4,5,6,7,8} by...
1
by: pantagruel | last post by:
Hi, I have an array like the following: for(x=0;x<results.length;x++){ alert(results.length); extracted=results.shift(); alert(results.length); if(results.indexOf(extracted)== -1){
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.