我要实现一个向左和向右执行循环旋转的函数.所以我为这两个操作写了同样的东西.例如,如果你正在旋转左边1010变成0101.这是对的吗？
unsigned char rotl(unsigned char c) {
int w;
unsigned char s = c;
for (w = 7; w >= 0; w--) {
int b = (int)getBit(c, w);//
if (b == 0) {
s = clearBit(s, 7 - w);
} else if (b == 1) {
s = setBit(s, 7 - w);
}
}
return s;
}
unsigned char getBit(unsigned char c, int n) {
return c = (c & (1 << n)) >> n;
}
unsigned char setBit(unsigned char c, int n) {
return c = c | (1 << n);
}
unsigned char clearBit(unsigned char c, int n) {
return c = c &(~(1 << n));
}
mkf*_*mkf 13
C中没有旋转运算符,但如果你写:
unsigned char rotl(unsigned char c)
{
return (c << 1) | (c >> 7);
}
然后,根据这个:http://www.linux-kongress.org/2009/slides/compiler_survey_felix_von_leitner.pdf(第56页),编译器将弄清楚你想要做什么,并只在一个中执行旋转(非常快) )指令.
Flo*_*ris 11
到目前为止,阅读答案和评论,似乎有一些关于你想要完成的事情的混淆 - 这可能是因为你使用的词语.在位操作中,您可以执行几项"标准"操作.我将总结其中一些以帮助澄清不同的概念.在接下来的所有内容中,我将abcdefgh用来表示8位(可以是1或0) - 当它们四处移动时,相同的字母将指向相同的位(可能位于不同的位置); 如果有点变成"绝对0或者1,我将表示如此".
1)位移:这基本上是"快速乘法或除以2的幂".使用的符号用于<<"左移"(乘)或>>右移(除).从而
abcdefgh >> 2 = 00abcdef
(相当于"除以4")和
abcdefgh << 3 = abcdefgh000
(相当于"乘以8" - 假设有"空间" abc转入;否则可能导致溢出)
2)位屏蔽:有时你想要将某些位设置为零 - 你可以通过一个AND运算来实现这一点,该运算的数字包含你想保留一个位的数字,并且你想要清除一个位置的零
abcdefgh & 01011010 = 0b0de0g0
或者,如果要确保某些位是1,则使用OR运算:
abcdefgh | 01011010 = a1c11f1h
3)循环移位:这有点棘手 - 有些情况下你想要"移动位",而"一端掉落"的那些重新出现在另一端.在C中没有这个符号,也没有"快速指令"(尽管大多数处理器都有内置指令,汇编代码可以利用这些指令进行FFT计算等).如果你想通过三个位置进行"左循环移位":
circshift(abcdefgh, 3) = defghabc
(注意= circshift标准C库中没有函数,尽管它存在于其他语言中 - 例如Matlab).出于同样的原因,"正确的转变"将是
circshift(abcdefgh, -2) = ghabcdef
4)位反转:有时你需要反转一个数字中的位.反转位时,没有"左"或"右" - 反转相反:
reverse(abcdefgh) = hgfedcba
同样,标准C库中实际上没有"反向"功能.
现在,让我们看一下在C中实现最后两个函数(circshift和reverse)的一些技巧.整个网站致力于"巧妙地操作位" - 例如参见优秀的http://graphics.stanford.edu/ ~seander/bithacks.html收集了一些精彩的"黑客攻击",虽然其中一些可能有点先进......
unsigned char circshift(unsigned char x, int n) {
return (x << n) | (x >> (8 - n));
}
这使用了上面的两个技巧:移位,并使用OR操作将位设置为特定值.让我们来看看它是如何工作的,因为n = 3(注意 - 我忽略了第8位以上的位,因为函数的返回类型是unsigned char):
(abcdefgh << 3) = defgh000
(abcdefgh >> (8 - 3)) = 00000abc
采用这两个的按位OR给出
defgh000 | 00000abc = defghabc
这正是我们想要的结果.还要注意的a << n是a >> (-n)- 换句话说,右移右移与左移左移相同,反之亦然.
现在让我们来看看这个reverse功能.这样做有"快速方式"和"慢速方式".上面的代码给出了一种"非常慢"的方式 - 让我以"非常快"的方式向您展示,假设您的编译器允许使用64位(long long)整数.
unsigned char reverse(unsigned char b) {
return (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}
你可能会问自己"刚刚发生了什么"？让我演示给你看:
b = abcdefgh
* 0x0000000202020202 = 00000000 00000000 0000000a bcdefgha bcdefgha bcdefgha bcdefgha bcdefgh0
& 0x0000010884422010 = 00000000 00000000 00000001 00001000 10000100 01000010 00100000 00010000
= 00000000 00000000 0000000a 0000f000 b0000g00 0c0000h0 00d00000 000e0000
请注意,我们现在只有一次所有位 - 它们只是一个相当奇怪的模式.模1023师将"感兴趣"的部分"折叠"在一起 - 这就像魔术一样,我无法解释它.结果确实如此
hgfedcba
稍微不那么模糊的方法来实现同样的事情(效率较低,但对于较大的数字非常有效)可以识别出如果你交换相邻的位,然后相邻的位对,然后是相邻的半字节(4位组)等 - 你最终得到了一个完整的位反转.在那种情况下,字节反转变为
unsigned char bytereverse(unsigned char b) {
b = (b & 0x55) << 1 | (b & 0xAA) >> 1; // swap adjacent bits
b = (b & 0x33) << 2 | (b & 0xCC) >> 2; // swap adjacent pairs
b = (b & 0x0F) << 4 | (b & 0xF0) >> 4; // swap nibbles
return b;
}
在这种情况下,字节发生以下情况b = abcdefgh:
b & 0x55 = abcdefgh & 01010101 = 0b0d0f0h << 1 = b0d0f0h0
b & 0xAA = abcdefgh & 10101010 = a0c0e0g0 >> 1 = 0a0c0e0g
OR these two to get badcfehg
下一行:
b & 0x33 = badcfehg & 00110011 = 00dc00hg << 2 = dc00hg00
b & 0xCC = badcfehg & 11001100 = ba00fe00 >> 2 = 00ba00fe
OR these to get dcbahgfe
最后一行:
b & 0x0F = dcbahgfe & 00001111 = 0000hgfe << 4 = hgfe0000
b & 0xF0 = dcbahgfe & 11110000 = dcba0000 >> 4 = 0000dcba
OR these to get hgfedcba
你追求的是反向字节.应该很容易看出只有几行(类似于上面的)会让你得到一个反向整数(32位).随着数量的增加,这种技巧相对而言变得越来越有效.
我相信你所寻找的答案在上面的"某个地方".如果没有别的,我希望你能更清楚地了解C中位操作的可能性.
如果根据您的评论，您想精确移动一位，那么实现这一点的一种简单方法是：
unsigned char rotl(unsigned char c)
{
return((c << 1) | (c >> 7));
}
你的代码所做的就是反转这些位；不旋转它们。例如，它将把 10111001 变成 10011101，而不是 01110011。