5

我正在尝试实现一个函数，该函数执行一个字节向左和向右的循环旋转。

我为这两个操作编写了相同的代码。例如，如果您向左旋转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));
}
4

3 回答 3

17

There is no rotation operator in C, but if you write:

unsigned char rotl(unsigned char c)
{
    return (c << 1) | (c >> 7);
}

then, according to this: http://www.linux-kongress.org/2009/slides/compiler_survey_felix_von_leitner.pdf (page 56), compilers will figure out what you want to do and perform the rotation it in only one (very fast) instruction.

于 2013-10-06T02:48:46.440 回答
14

到目前为止，阅读答案和评论，似乎对您要完成的工作有些困惑——这可能是因为您使用的词语。在位操作中，您可以做一些“标准”的事情。我将总结其中的一些以帮助澄清不同的概念。在接下来的所有内容中，我将使用abcdefgh8 位（可能是 1 或 0）来表示 - 当它们四处移动时，相同的字母将指代相同的位（可能在不同的位置）；如果有点变成“绝对0或1，我将这样表示它）。

1）位移：这本质上是“快速乘以或除以2的幂”。使用的符号用于<<“左移”（乘法）或>>右移（除法）。因此

abcdefgh >> 2 = 00abcdef

（相当于“除以四”）和

abcdefgh << 3 = abcdefgh000

（相当于“乘以八” - 并假设有“空间”可以移入abc；否则这可能会导致溢出）

2）位掩码：有时您想将某些位设置为零。为此，您可以对一个数字进行 AND 操作，该数字在您想要保留位的位置和想要清除位的位置为零。

abcdefgh & 01011010 = 0b0de0g0

或者，如果您想确保某些位为 1，请使用 OR 操作：

abcdefgh | 01011010 = a1c11f1h

3)循环移位：这有点棘手 - 在某些情况下，您想要“移动位”，而“在一端脱落”的那些会重新出现在另一端。在 C 中没有用于此的符号，也没有“快速指令”（尽管大多数处理器都有一个内置指令，汇编代码可以利用该指令进行 FFT 计算等）。如果您想通过三个位置进行“左循环”：

circshift(abcdefgh, 3) = defghabc

（注意：标准 C 库中没有circshift函数，尽管它存在于其他语言中 - 例如 Matlab）。出于同样的原因，“右移”将是

circshift(abcdefgh, -2) = ghabcdef

4）位反转：有时您需要反转数字中的位。反转位时，没有“左”或“右” - 反转是反转：

reverse(abcdefgh) = hgfedcba

同样，标准 C 库中实际上没有“反向”函数。

现在，让我们看一下在 C 中实现最后两个函数 (circshift和reverse) 的一些技巧。整个网站都致力于“巧妙地操作位” - 例如，参见这个优秀的。对于“bit hacks”的精彩集合，虽然其中一些可能有点先进......

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

取这两者的按位或得到

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 中位操作的可能性有更清晰的了解。

于 2013-10-07T03:32:08.257 回答
2

如果根据您的评论，您想精确地移动一位，那么实现这一目标的一种简单方法是：

unsigned char rotl(unsigned char c)
{
    return((c << 1) | (c >> 7));
}

您的代码所做的是反转位；不旋转它们。例如，它将 10111001 变成 10011101，而不是 01110011。

于 2013-10-06T02:43:19.663 回答