代码之家 › 专栏 › 技术社区 › Yair Halberstadt

有效地向左移动整数并环绕[复制]

bit-manipulation optimization c#

Yair Halberstadt · 技术社区 · 7 年前

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

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

0 回复 | 直到 7 年前

mkf 12 年前

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页),编译器将只在一条(非常快)指令中计算出您想要做什么并执行旋转。

TrebledJ 7 年前

阅读到目前为止的答案和评论,人们似乎对你想要完成的事情有些困惑——这可能是因为你使用的词汇。在位操作中,有几个“标准”的事情你可以做。我将对其中一些进行总结,以帮助澄清不同的概念。 在接下来的所有事情中,我将使用 abcdefgh 表示8位 (可以是1或0)-当它们移动时,同一个字母将指同一个位(可能在不同的位置);如果一个位变成“肯定的” 0 或 1 ,我会这样表示)。

(一) 移位 :这实际上是“快速乘或除以2的幂”。使用的符号是 << 对于“左移”(乘法)或 >> 用于右移(除法)。因此

abcdefgh >> 2 = 00abcdef

(相当于“除以四”)和

abcdefgh << 3 = abcdefgh000

(相当于“乘8”-假设有“空间”来移动 abc 否则可能导致溢出)

2个) 位掩蔽 :有时需要将某些位设置为零。通过对一个数字执行AND操作来实现此目的,该数字的一个要保留一位,而零个要清除一位。

abcdefgh & 01011010 = 0b0de0g0

或者,如果要确保某些位是一位,可以使用或操作:

abcdefgh | 01011010 = a1c11f1h

三) 循环移位 :这有点棘手-有些情况下,您希望“移动位”,而“一端脱落”的出现在另一端。在C语言中没有这个符号,也没有“快速指令”(尽管大多数处理器都有一个内置指令,汇编代码可以利用它进行FFT计算等)。如果要执行三个位置的“左循环移位”:

circshift(abcdefgh, 3) = defghabc

(注:没有 circshift 函数在标准C库中,虽然它存在于其他语言中,例如Matlab。同样,“右转”也会是

circshift(abcdefgh, -2) = ghabcdef

(四) 位反转 :有时需要反转数字中的位。反转位时,没有“左”或“右”-反转:

reverse(abcdefgh) = hgfedcba

同样,标准C库中实际上没有“reverse”函数。

现在,让我们看看实现最后两个函数的一些技巧( 循环移位 和 reverse )在C语言中,有很多网站都致力于“巧妙地操作位”-例如 this excellent one . 为一个精彩的“比特黑客”集合,虽然其中一些可能是有点先进。。。

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) ;换句话说,负数右移和正数左移是一样的,并且 反之亦然 .

现在让我们看看 颠倒 功能。有“快速方法”和“慢速方法”可以做到这一点。上面的代码给出了一种“非常慢”的方式——假设编译器允许使用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语言中位操作的可能性。

Dolda2000 12 年前

如果根据您的评论,您希望准确地移动一点,那么实现这一点的一个简单方法是:

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

你的代码所做的是反转位,而不是旋转位。例如,它将使10111001变为10011101,而不是0111011。