4

像这样：

input:  10010011
(10->01->00->11)

output: 11000110
(11->00->01->10)


input:  11010001
(11->01->00->01)

output: 01000111
(01->00->01->11)

有人对此有任何想法吗？

4

7 回答 7

7

比lserni的算法更少的操作：

uint32_t reverseByTwo(uint32_t value) {
    value = ((value & 0x03030303) << 2) | ((value >> 2) & 0x03030303); // swap adjacent pairs
    value = ((value & 0x0F0F0F0F) << 4) | ((value >> 4) & 0x0F0F0F0F); // swap nibbles
    value = ((value & 0x00FF00FF) << 8) | ((value >> 8) & 0x00FF00FF); // swap bytes
    value = ((value & 0x0000FFFF) << 16) | ((value >> 16) & 0x0000FFFF);
    return value;
}

对于 64 位值，只需为 32 位一半添加另一个交换，对于较小的类型，只需省略最后几个交换。

于 2012-08-30T20:56:29.020 回答
3

Weird request. I'd do it like this:

uint32_t reverseByTwo(uint32_t value)
{
    int i;
    uint32_t new_value = 0;
    for (i = 0; i < 16; i++)
    {
        new_value <<= 2;            
        new_value |= (value & 0x3);
        value >>= 2;
    }
    return new_value;
}

At each iteration, the two LSB of value are placed in the two LSB of new_value, which is shifted to the left.

For an eight-bit value,

uint8_t reverseByTwo(uint8_t value)
{
    int i;
    uint32_t new_value = 0;
    for (i = 0; i < 4; i++)
    {
        new_value <<= 2;            
        new_value |= (value & 0x3);
        value >>= 2;
    }
    return new_value;
}

if performances are at a premium, you can manually unroll the loop (GCC should do this by itself, but sometimes doesn't bother) and declare the function as inline.

    new_value = 0;
    // new_value <<= 2; // First time not necessary
    new_value |= (value & 0x3);
    value >>= 2;
    new_value <<= 2;            
    new_value |= (value & 0x3);
    value >>= 2;
    new_value <<= 2;            
    new_value |= (value & 0x3);
    value >>= 2;
    new_value <<= 2;            
    new_value |= (value & 0x3);
    // value >>= 2; 
    return new_value;
于 2012-08-30T20:45:03.257 回答
2

将单个字节 (char) 中的位转换为另一个单个字节的最快方法是自己构建一个数组：

unsigned char rev[256];
rev[0]   = 0;     /* 00000000 -> 00000000 */
...
rev[147] = 198;   /* 10010011 -> 11000110 */
...
rev[198] = 147;   /* 11000110 -> 10010011 */
...
rev[255] = 255;   /* 11111111 -> 11111111 */

要将数字 x 转换为其位反转形式，只需编写rev[x]. 如果您有多个字节要转换，例如在 4-byteint中，只需查找rev表中的 4 个字节。

编写此代码时，您需要将二进制转换为另一个基数（这里，我使用十进制），因为 C 没有二进制常量（这将比八进制常量有用十倍）。

您也可以将值放入初始化程序，但您必须计算位置以确保所有内容都在正确的位置。（也许写一个小程序来做到这一点！）

unsigned char rev[256] = {0, ..., 198, ..., 147, ..., 255};

在正确的位置填写...所有其他数字。

于 2012-08-30T21:22:41.533 回答
1 
$x = (($x & 0x33333333) << 2) | (($x & 0xCCCCCCCC) >> 2);
$x = (($x & 0x0F0F0F0F) << 4) | (($x & 0xFOFOFOFO) >> 4);
$x = (($x & 0x00FF00FF) << 8) | (($x & 0xFF00FF00) >> 8);
$x = (($x & 0x0000FFFF) << 16) | (($x & 0xFFFF0000) >> 16);

值得称赞的是，这个算法出自 Henry S. Warren, Jr. 的“Hacker's Delight”。唯一的区别是书中的算法没有成对反转；它只是颠倒了这些位。

于 2012-08-30T21:14:22.743 回答
0 
#include <limits.h>

#define INT_BITS  (sizeof(int) * CHAR_BIT)

unsigned reverse_bits(unsigned x) {
#define PAIR(i)       ((((x) >> (i*2)) & 3) << (INT_BITS - (i+1)*2))
    unsigned result = 0;
    unsigned i;
    for(i = 0; i < INT_BITS/2; i++) {
        result |= PAIR(i);
    }
    return result;
}

虽然这对于 unsigned int 可以做到这一点，但您可能希望将intand替换unsigned为charand unsigned char。

于 2012-08-30T20:54:36.387 回答
0

如果你想尽可能快：

output =
  ((input & 0xc0) >> 6) |
  ((input & 0x30) >> 2) |
  ((input & 0xc) << 2) |
  ((input & 0x3) << 6);
于 2012-08-30T20:56:43.420 回答
0

你有位 (ab cd ef gh) 和想要 (gh ef cd ab)
如果你乘以 0x101 并存储在 16 位 int 中，你得到 (ab cd ef gh ab cd ef gh)。
然后，您将在该数字中的位模式分为两组，每组四位：

  • (00 00 ef 00 ab 00 00 00),
  • (00 00 00 gh 00 cd 00 00)

所以你只需要适当地转移和掩盖

unsigned char swap_bit_pairs(unsigned char b)
{
    unsigned int a = 0x101*b;
    return ((a >> 6) & 0x33) | ((a >> 2) & 0xCC);
}

所以有可能在 6 次操作中

编辑：哎呀！我写的是 0x66 而不是 0xCC

于 2012-08-31T10:48:50.573 回答