循环移位算法

[huangblue]

【一本全面的C语言入门教程】（311，290） Your function takes two arguments: the first, the value to be rotated, and the second,the number of bits by which the object is to be rotated. If this second argument is positive,you rotate the value to the left; otherwise, you rotate the value to the right. You can adopt a fairly straightforward approach to implementing your rotate function. For example, to compute the result of rotating x to the left by n bits, where x is of type int and n ranges from 0 to the number of bits in an int minus 1, you can extract the leftmost n bits of x, shift x to the left by n bits, and then put the extracted bits back into x at the right. A similar algorithm also can be used to implement the right rotate function.

[huangblue]

//阅读版本 // Program to illustrate rotation of integers

include

// Function to rotate an unsigned int left or right unsigned int rotate (unsigned int value, int n) { 　 unsigned int result, bits; 　 // scale down the shift count to a defined range 　 if ( n > 0 ) 　　 n = n % 32; 　 else 　　 n = -(-n % 32);

　 if ( n == 0 ) 　　 result = value; 　 else if ( n > 0 ) { // left rotate 　　 bits = value >> (32 - n); 　 　 result = value << n | bits; 　 } 　 else { // right rotate 　　 n = -n; 　　 bits = value << (32 - n); 　　 result = value >> n | bits; 　 } 　 return result; }

int main (void) { unsigned int w1 = 0xabcdef00u, w2 = 0xffff1122u; unsigned int rotate (unsigned int value, int n);

printf ("%x\n", rotate (w1, 8));
printf ("%x\n", rotate (w1, -16));
printf ("%x\n", rotate (w2, 4));
printf ("%x\n", rotate (w2, -2));
printf ("%x\n", rotate (w1, 0));
printf ("%x\n", rotate (w1, 44));
return 0;

}

[huangblue]

//运行版本 // Program to illustrate rotation of integers

include

// Function to rotate an unsigned int left or right unsigned int rotate (unsigned int value, int n) { unsigned int result, bits; // scale down the shift count to a defined range if ( n > 0 ) n = n % 32; else n = -(-n % 32);

if ( n == 0 )
    result = value;
else if ( n > 0 ) { // left rotate
    bits = value >> (32 - n);
    result = value << n | bits;
}
else { // right rotate
    n = -n;
    bits = value << (32 - n);
    result = value >> n | bits;
}
return result;

}

int main (void) { unsigned int w1 = 0xabcdef00u, w2 = 0xffff1122u; unsigned int rotate (unsigned int value, int n);

printf ("%x\n", rotate (w1, 8));
printf ("%x\n", rotate (w1, -16));
printf ("%x\n", rotate (w2, 4));
printf ("%x\n", rotate (w2, -2));
printf ("%x\n", rotate (w1, 0));
printf ("%x\n", rotate (w1, 44));
return 0;

}

[huangblue]

cdef00ab ef00abcd fff1122f bfffc448 abcdef00 def00abc

Process returned 0 (0x0) execution time : -0.000 s Press any key to continue.

[huangblue]

An n-bit rotation to the left is divided into three steps by the function.

1 First, the n leftmost bits of value are extracted and shifted to the right.This is done by shifting value to the right by the size of an int (in our case, 32) minus n.

2 Next, value is shifted n bits to the left,

3 and finally, the extracted bits are ORed back in.

A similar procedure is followed to rotate value to the right.