循环移位_循环移位性质 - CSDN
精华内容
参与话题
  • 循环移位算法

    千次阅读 2013-09-11 12:27:03
    分析:比如数组 1 2 3 4循环右移1位 将变成 4 1 2 3, 观察可知1 2 3 的顺序在移位前后没有改变,只是和4的位置交换了一下,所以等同于1 2 3 4 先划分为两部分1 2 3 | 4,然后将1 2 3逆序,再将4 逆序 得到 3 2 1 4...
    将一个含有n个元素的数组向右循环移动k位,要求时间复杂度是O(n),且只能使用两个额外的变量,这是在微软的编程之美上看到的一道题

    分析:比如数组 1 2 3 4循环右移1位 将变成 4 1 2 3, 观察可知1 2 3 的顺序在移位前后没有改变,只是和4的位置交换了一下,所以等同于1 2 3 4 先划分为两部分1 2 3 | 4,然后将1 2 3逆序,再将4 逆序 得到 3 2 1 4,最后整体逆序 得到 4 1 2 3;

    《编程之美》中的题目要求只使用两个附加变量。王晓东编著的《算法设计与实验题解》中要求只用到O(1)的辅助空间。其它地方两本书的要求相同,都是O(n)的时间复杂度。两本书中的解法总结起来就是三种方法:(1)循环换位算法(2)三次反转算法(3)排列循环算法。这三种算法在王晓东的著作中都有实现代码。第一种算法是最原始的算法。第二种算法比较巧妙,即使用VU=reverse(reverse(U)reserve(V)),写成数学形式就是:

     。

    于是使用三次反转也可实现。

    第二种方法实现代码:

    #include <string.h>
    #include <assert.h>
    static void Swap(char *p, char *q);
    static void Reverse(char *str, int i, int n);
    void String_Shift_Reverse(char *str, int n)
    {
        int len;    
        assert(NULL != str);
        len = strlen(str);
        if (n <=0 || n >= len) {
            return;
        }
        Reverse(str, 0, n - 1);
        Reverse(str, n, len - 1);
        Reverse(str, 0, len - 1);
    }
    static void Swap(char *p, char *q)
    {
        char tmp;
        tmp = *p;
        *p = *q;
        *q = tmp;
    }
    static void Reverse(char *str, int i, int n)
    {
        int l, r;
        for (l = i, r = n; l < r; l++, r--) {
            Swap(&str[l], &str[r]);
        }
    }
    或者:

    // 将buffer中start和end之间的元素逆序
    void Reverse( int buffer[], int start, int end )
    {
        while ( start < end )
        {
            int temp = buffer[ start ] ;
            buffer[ start++ ] = buffer[ end ] ;
            buffer[ end-- ] = temp ;
        }
    }
    
    // 将含有n个元素的数组buffer右移k位
    void Shift( int buffer[], int n, int k )
    {
        k %= n ;
    
        Reverse( buffer, 0, n - k - 1) ;
        Reverse( buffer, n - k, n - 1 ) ;
        Reverse( buffer, 0, n - 1 ) ;
    }

    第三种方法与数学有较大关系,以下着重解释第三种方法,借此复习一下数学。

    对于第三种方法,王晓东老师在著作中介绍了一条循环置换分解定理:对于给定数组A[0..N-1]向后循环换位N-K位运算,可分解为恰好gcd(K,N-K)个循环置换,且0,...,gcd(K,N-K)-1中的每个数恰属于一个循环置换。其中gcd(x,y)表示x和y的最大公因数。

    我们从头开始分析这个问题,对于数组A[0..n-1],要将其向后循环移动k位元素。因为每个元素右移n位后又回到了原来的位置上,所以右移k位等于右移k mod n位。考虑每个元素右移k位后的最终位置,比如对于A[0],右移k位后在k mod n位置上,原来在k mod n位置上的元素右移k位后到了2*k mod n的位置上,把如此因为A[0]的移动而受到连环影响必须移动的位置列出来,就是下面这样一个位置序列:0,k,2*k,...,(t-1)k。其中每一项都是在模n的意义下的位置。t*k mod n 的结果是0。t是使得t*k mod n的结果为0的最小正整数。

    这个位置序列实质上是模n加法群中由元素k生成的一个循环子群。由群论中的结论(该结论的证明见最后)知,循环子群(k)的周期为n / gcd(k,n),元数为n / gcd(k,n),其陪集个数为gcd(k,n)。换句话说,A[0..n-1]循环右移k位的结果是循环子群(k)以及它的所有陪集循环右移一位。例如,将A[0..5] = {1,2,3,4,5,6}循环右移4位,这里n = 6, k = 4, gcd(k, n) = 2。A[0]的最终位置是4,A[4]的最终位置是2,A[2]的最终位置是0,这样,位置0,4,2便是由k=4生成的循环群,周期为6 / gcd(4,6) = 6 / 2 = 3,这样的循环子群共有gcd(4,6) = 2个。

    第三种方法的完整代码如下:

    // 数组的循环移位
    #include <cstdio>
    
    int gcd(int m, int n) {
    	int r;
    	while(r = m % n) {
    		m = n; n = r;
    	}
    	return n;
    }
    
    void shiftArray(int A[], int n, int k) {
    	// 因为左移的代码比右移的代码好实现的多,而右移k位
    	// 等价于左移-k位,-k = n - k。以下代码是通过左移-k位来实现右移k位
    	k = n - (k % n);
    	for(int i = 0, cnt = gcd(n, k); i < cnt; i++) {
    		int t = A[i], p = i, j = (k+i) % n;
    		while(j != i) {
    			A[p] = A[j]; p = j; j = (k + p) % n;
    		}
    		A[p] = t;
    	}
    }
    
    void printArray(int A[], int n) {
    	for(int i = 0; i < n; i++) {
    		printf("%-3d", A[i]);
    		if((i+1)%10 == 0) printf("/n");
    	}
    }
    int main() {
    	int A[] = {1,2,3,4,5,6, 7};
    	shiftArray(A, 7, 4);
    	printArray(A, 7);
    	return 0;
    }

    上述所用到的那个群论结论的证明:

    结论:设G是一个循环群,其中一个生成元素为a,若r和n的最大公约数为d,则a^r的周期为n / d。

     

    在模n加法群中,1是一个生成元素,任意元素k=1*k,所以任意元素k生成的循环子群(k)的周期为n / gcd(k,n)。因为gcd(k,n)=gcd(k,n-k),所以也可以写成n / gcd(k, n-k)。

    #include <iostream>
    
    using namespace std;
    
    inline Swap(char& a, char& b)
    {
    	char temp;
    	if (a != b) {
    		temp = a;
    		a = b;
    		b = temp;
    	}
    }
    
    void ReverseString(char *v, int s, int e)
    {
    	if (v == NULL || s > e) {
    		return ;
    	}
    
    	char temp;
    	while (s < e) {
    		Swap(v[s], v[e]);	
    		++ s;
    		-- e;
    	}
    }
    
    int main(int argc, char **argv)
    {
    	char str[] = "1234567";
    	const int len = strlen(str);
    	const int n = 3;
    
    	ReverseString(str, 0, n - 1);
    	ReverseString(str, n, len - 1);
    	ReverseString(str, 0, len -1);
    
    	cout<<"len = "<<len<<", str = "<<str<<endl;
    
    	return 0;
    
    }


    最大公约数:

    int gcd(int a, int b)
    {
    	int temp;
    
    	if (a < b) {
    		temp = a;
    		a = b;
    		b = temp;
    	}
    
    	while (b != 0) {
    		temp  = a % b;
    		a = b;
    		b = temp;
    	}
    
    	return a;
    }

    #include <iostream>
    
    using namespace std;
    
    int gcd(int a, int b)
    {
    	int temp;
    
    	if (a < b) {
    		temp = a;
    		a = b;
    		b = temp;
    	}
    
    	while (b != 0) {
    		temp  = a % b;
    		a = b;
    		b = temp;
    	}
    
    	return a;
    }
    
    int lcm(int a, int b)
    {
    	return a*b / gcd(a,b);
    }
    
    int main(int argc, char **argv)
    {
    	int a = 5;
    
    	int b = 13;
    
    	cout<<"最大公约数: "<<gcd(a,b)<<endl;
    		
    	cout<<"最小公倍数: "<<lcm(a,b)<<endl;
    	return 0;
    }





    展开全文
  • 循环移位:循环左移和循环右移

    万次阅读 多人点赞 2018-04-30 16:22:55
    换句话说,循环移位就是将移出的低位放到该数的高位(循环右移)或把移出的高位放到该数的低位(循环左移),左移,和右移动都是对整数进行的操作,在Win32控制台应用程序中,整形占4Byte节32bit。 &nbsp; &...

           循环移位就是把数值变成二进制,然后循环移动的过程;换句话说,循环移位就是将移出的低位放到该数的高位(循环右移)或把移出的高位放到该数的低位(循环左移),左移,和右移动都是对整数进行的操作,在Win32控制台应用程序中,整形占4Byte节32bit。


           循环左移的过程:
    这里写图片描述
           循环左移的过程可以分为3步:
    1. 将x左端的n位先移动到y的低n位中,x>>(32-n);
    2. 将x左移n位,其右面低位补0,x<<n;
    3. 进行按位或运算(x >> (32 - n) | (x << n));


           循环右移的过程:

    这里写图片描述
           循环右移的过程可以分为3步:
    1. 将x的左端的低n位先移动到y的高n位中x<<(32-n)
    2. 将x右移n位,其左面高n位补0x>>n;
    3.进行按位或操作(x << (32 - n) | (x >> n));


            假如将一个无符号的数据val,长度为N,需要循环移动n位。可以利用下面的公式:
            循环左移:(val >> (N - n) | (val << n))
            循环右移:(val << (32 - n) | (val >> n))


           C语言实现循环移位:循环移位是对二进制序列进行操作,所以实现循环移位先需要将需要移位的数转换为二进制序列,然后按照上面描述的步骤进行移位,最后将移位后的二进制序列打印出来;

    源代码

    #include <stdio.h>
    #include <Windows.h>
    
    //将一个十进制数转换为二进制
    void  trans_binary(unsigned int  val)
    {
        int a[32];
        int i = 0;
        for(i=0;i<=31;i++)
        { 
            a[i] = val % 2;
            val /= 2;
        }
        //倒序输出,每输出8位,输出一个空格
        for (int j = 31,k = 1; j >= 0; j--,k++)
        {
            printf("%d", a[j]);
            if (k % 8 == 0)
            {
                printf(" ");
            }
        }
        printf("\n");
    }
    
    //循环左移
    
    void left_move(unsigned val, int n)
    {
        unsigned int z;
        printf("需要移位的二进制序列为:\n");
        trans_binary(val);
        z = (val >> (32 - n) | (val << n));
        printf("移位后:\n");
        trans_binary(z);
    }
    
    void right_move(unsigned val, int n)
    {
        unsigned int z;
        printf("需要移位的二进制序列为:\n");
        trans_binary(val);
        z =  (val << (32 - n) | (val >> n));
        printf("移位后:\n");
        trans_binary(z);
    }
    
    int main()
    {
        int num = 0;
        int n = 0;
        int select = 0;
        printf("请输入要移位的数和移动位数:\n");
        scanf("%d%d", &num, &n);
        printf("请输入选择:(-1-:左移 -2-:右移 -0-:退出):\n");
        scanf("%d", &select);
        switch (select)
        {
        case 1:left_move(num, n);
            printf("\n");
            break;
        case 2:right_move(num, n);
            break;
        case 0:exit(0);
            break;
        default:
            printf("输入有误!\n");
            break;
        }
        system("pause");
        return 0;
    }

    运行结果

    这里写图片描述

            为了更直观的显示结果,选取了一个比较大的数1234567891,移动位数:8,移动方式:循环左移;根据循环左移的方法,先取出高8(移动的位数)位,移动到底8位(右移24位),然后将其余位数依此左移8位,结果与运行结果一致。

    展开全文
  • 循环移位的问题

    2019-07-15 10:47:48
    设计一个算法,把一个含有N个元素的数组循环右移K位,要求时间复杂度为O(N),且只允许使用两个附加变量。 求解方法1: voidRightShift(char*arr,intN,intk){  k= k % K;while(k--){chart=arr[N-1];for(inti=N...

    1. 简述

        设计一个算法,把一个含有N个元素的数组循环右移K位,要求时间复杂度为O(N),且只允许使用两个附加变量。

     

    求解方法1:

    void RightShift(char *arr, int N, int k)
    {

      k = k % K;
        
    while(k--)
        {
            
    char t = arr[N-1];
            
    for(int i = N-1; i > 0; i--)
                arr[i] 
    = arr[i-1];
            arr[
    0= t;
        }
    }

     

    求解方法2:

     

    #include <stdio.h>

     

    #define  N    10

     

    void Loop_Shifting(int a[], int n, int k);
    void Reverse(int a[], int low, int high);
    void PrintNode(int a[], int n);
    int main()
    {
     int a[N] = {1,2,3,4,5,6,7,8,9,0};

     

     int n = 0;
     int k = 0;

     

     n = N;
     k = 4;

     

     PrintNode(a, n);
     Loop_Shifting(a, n, k);
     PrintNode(a, n);

     

     return 0;
    }

     

    void Reverse(int a[], int low, int high)
    {
     int tmp = 0;

     

     for(; low < high; low++, high--)
     {
      tmp = a[high];
      a[high] = a[low];
      a[low] = tmp;
     }
    }

     

    void Loop_Shifting(int a[], int n, int k)
    {
     k = k % N;

     

     Reverse(a, 0, (n - k - 1));
     Reverse(a, (n - k), (n - 1));
     Reverse(a, 0, (n - 1));
    }

     

    void PrintNode(int a[], int n)
    {
     int i = 0;

     

     for (i = 0; i < n; i++)
     {
      printf("%d", a[i]); 
     }

     

     printf("\n");
    }

     

    转载于:https://www.cnblogs.com/wulijun/archive/2012/03/06/2381955.html

    展开全文
  • 【C编程】循环移位

    千次阅读 2019-06-20 15:18:40
    循环移位分为循环左移和循环右移。 1、循环左移 如图,将x的左端n位先放到z中的低n位中,由语句z>>(32-n)实现,将x左移n位,其右边的低n位补0,由y=x<<n实现,将y与z按位或运算,由语句y=y|z实现 2...

    循环移位分为循环左移和循环右移。

    1、循环左移

    如图,将x的左端n位先放到z中的低n位中,由语句z>>(32-n)实现,将x左移n位,其右边的低n位补0,由y=x<<n实现,将y与z按位或运算,由语句y=y|z实现

    2、循环右移

    如图,将x的右端n位先放到z中的高n位中,由语句z<<(32-n)实现,将x左移n位,其右边的高n位补0,由y=x>>n实现,将y与z按位或运算,由语句y=y|z实现

    代码:

    #include<stdio.h>
    
    move(unsigned value, int n)			/*自定义移位函数*/
    {
        unsigned z;
    	if(n>0)
    	{
    		z = (value >> (32-n)) | (value << n);	/*循环左移的实现过程*/
    	}
    	else
    	{
    		n=-n;
    		z = (value << (32-n)) | (value >> n);  /*循环右移的实现过程*/
    	}
    	return z;
    }
    
    void main()
    {
        unsigned a;
        int n;
        printf("请输入一个八进制数:\n");
        scanf("%o", &a);				/*输入一个八进制数*/
        printf("请输入要移位的位数:\n");
        scanf("%d", &n);			    /*输入要移位的位数*/
        printf("移位后的结果是:%o\n", move(a, n));	/*将移位后的结果输出*/
    }
    

    执行结果:

    展开全文
  • ROL: 循环左移指令,低位补高位移除的数据。 例如: 1000,0001 b, a = 1000,0001 b << 1; 则: a = 0000,0010 b; a = ROL 1000,0001 b,1; 则: a = 0000,0011 b; 补充: 循环左移ROL(Rot...
  • 数组循环移位问题

    2019-02-09 20:55:08
    数组循环移位问题
  • 循环移位(翻转算法)

    千次阅读 2017-02-20 22:30:34
    循环移位
  • 循环移位(c语言)

    千次阅读 2012-12-07 17:41:21
    移位运算符 符号 含义 左移位 >> 右移位 举例(32位ubuntu系统,unsigned short int 16bit) #include #include void intTobinary(unsigned int); int main() { unsigned short int a = 15; int i; //首先a...
  • 循环移位

    2019-07-17 16:08:15
    循环移位, 有n个整数,使前面各数顺序向后移动k个位置,移出的数再从开头移入。 题目就是把n个数围成一个环,分别把数往后移k个位置。 代码实现:for (i=0; i<n; i++) b[(i+k)%n] = a[i]; 当然解法...
  • 基于OpenCV+VS2013实现的图像行方向循环移位,适用于3通道或单通道图像,移位起始点是0到高度之内的随机整数。若需列方向循环移位,可首先旋转原图。
  • C++ 循环移位简单加密

    2020-07-21 10:00:39
    ex:输入移动位数 1 输入语句:a 输出 b 输入语句: b 输出 c
  • 四位循环移位寄存器代码!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  • 数据循环移位

    2013-09-24 20:17:32
    //比如一个数组 1 2 3 4 5 6 循环右移 2 位,将变成 5 6 1 2 3 4, 经过观察,可以看到1 2 3 4 部分的顺序在移位前后的相对位置并没有变化,只是5 6 放在了最前面。 //因此思路可为:1)先化分为两部分:1 2 3 4 ...
  • C语言循环移位及位操作

    千次阅读 2013-11-09 00:53:14
    ---xiaoxiaopig ...C语言中没有提供循环移位的操作符,但可以通过简洁的方式实现循环移位 设一个操作数x有s位则循环左移n位的操作为: (x > (s - n)); 同理右移n位位: (x >> n) | (x 实际编程中可以用宏定义
  • c语言循环移位

    千次阅读 2015-04-24 10:42:41
    #include #include int move(int value,int n) { if(n==0) { value=value; } if(n>0) { value=(value>>n)|(value(sizeof(value)-n)); } if(n) { n=-n; value=(value>(sizeof(value)-n));... }
  • 循环移位方阵

    千次阅读 2014-04-02 09:40:31
    //【习2.19】 循环移位方阵。 //采用一维数组,将数组看成环形。 /* 对于给定的一个数据元素序列,如{0,1,2,3,4},输出如下形式的循环移位方阵: 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 *...
  • C++实现循环移位

    2020-04-22 16:54:22
    C++实现循环移位 1.1 大循环 1.2 小循环
  • 51单片机之循环移位

    万次阅读 2012-12-06 16:53:35
    51单片机之循环移位函数 今天在看书的时候看到了循环移位函数,想跟大家分享下,呵呵,大牛们不要嘲笑,由于本人刚起步,莫笑。 如果你使用keil软件编写C51程序的话,那么你可以打开Keil下的C51下的HLP文件,...
  • 字节数组(byte[])实现二进制串的循环移位 最近去公司实习了。公司的主业是网络安全,先说一个:密码学中的移位都是循环移位。现在用字节数组byte[]存储二进制串,1024个二进制数字就是128个字节,byte[128],如何...
  • 二进制循环移位问题

    千次阅读 2017-10-21 07:41:49
    循环移位 Time Limit: 3000ms, Memory Limit: 10000KB , Accepted: 2516, Total Submissions: 3693 Description 编写函数实现value左右循环移位(即移出的位在另一端填入)。函数原型为int move(int value,int n...
1 2 3 4 5 ... 20
收藏数 47,518
精华内容 19,007
关键字:

循环移位