具有未定义数据大小的位反转的最有效算法

Question

实现以下最快的算法是什么：

1010 0000 => 0000 0101

转换是从 MSB LSB 到 LSB MSB。所有位都必须反转，但困难的部分是数据的大小在 1 字节到 8 字节之间，我无法在 advance.That 中知道它意味着我无法预测大小。帧到达时带有一个指示帧大小的字节。大小在 1 字节和 8 字节之间变化。

Answer 1

最佳是一个任意术语，因为您没有指定代码量或性能是您的标准。

对于 'fast' 结果，您应该只使用查找 table (LUT) 来反转每个字节中的位，然后将字节移入结果。

// there are easy ways to generate this table instead of doing it yourself
unsigned char Reverse[256] = {
  0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, 
  ...
  0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

int last = 3-1; // last element 
unsigned char in[8] = { 0x12, 0x34, 0x56 };
unsigned char out[8];

for (int index = 0; index <= last; index++) {
    // store bytes in reverse, reverse bits in each byte using LUT
    out[ last-index] = Reverse[ in[ index] ];
}

如果上述方法不太令人满意，可以使用多种替代方法在此 Bit Twiddling Hacks 页面上执行位反转

Answer 2

可以像下面这样，检查first和last位状态，如果两个位状态（0或1）不同，则切换两者。

unsigned int data = 0xa0;
for(int start = 0, end = 8*sizeof(data) - 1; start < end; start++, end--) {
        if(data>>start&1 != data>>end&1) { /*check last and 1st bit pos status */ 
                data = data ^ 1<<start;/*complimenting start bit */
                data = data ^ 1<<end;
        }
}

end = 8*sizeof(data) - 1 如果输入是 8 位长或 32 位长，则两者都适用。

Answer 3

可以通过使用位操作一次递增地移动多个位来执行此类操作。

32 位整数示例：

uint32_t reverse(uint32_t x, size_t len)
{
    assert(len > 0 && len <= 4);
    x = ((x & 0x55555555) <<  1) | ((x & 0xAAAAAAAA) >>  1);
    x = ((x & 0x33333333) <<  2) | ((x & 0xCCCCCCCC) >>  2);
    x = ((x & 0x0F0F0F0F) <<  4) | ((x & 0xF0F0F0F0) >>  4);
    x = ((x & 0x00FF00FF) <<  8) | ((x & 0xFF00FF00) >>  8);
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
    return x >> (32 - len * 8);
}

这可能是最快且缓存友好的实现。

要为自定义宽度整数实现类似功能，您需要能够构建具有 "X bit over X bit set" 的位掩码，例如1 后 1 位（每秒位），2 后 2 等。其余的应该是不言自明的。

您可以在此基础上实现其他变体。如果您需要在运行时选择它们，最好一直使用最宽的版本（64 位）以避免分支。

注意：GCC 能够识别 return 语句前最后两行中的字节交换操作，并且能够在 x86 上生成 bswap，在 ARM 上生成 rev。对于 64 位 CPU 这使得 64 位版本在速度上等同于上面的版本。

显然，如果不参考某些 paper/book/patent 的内容，现在就无法 post 基于常用技术的算法。因此，我 post 在这里获得了高度专利、版权和其他方面受保护的通用版本。 请注意，使用前请三思（因为它已获得专利）。

不幸的是，由此代码生成的程序集完全是垃圾。只有 clang 能够以某种方式理解正在发生的事情并将其优化。

我几年前写的原始实现是用 C++ 编写的，并且严重依赖模板来帮助编译器。最后这是一个可怕而复杂的混乱，但可以为 8、16、32 和 64 个整数生成许多面向位的算法（如果编译器支持它们甚至更多）。尽管如此，这可以作为对上述算法的描述。

此代码使用 64 位代码的单个实例实现 8、16、32、64 位字的反向算法。辅助函数 repeat、select 可以用作许多位算法的基础（尽管它们基本上生成所需的位掩码）。

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>

/**
 * @brief Mask with `n` bits set.
 */
static uint64_t bits(size_t n)
{
    return (((1ull << n) - 1) | (-uint64_t(n >= 64)));
}

static uint64_t do_repeat(uint64_t x, size_t w, size_t n)
{
    if (n == 0)
        return x;

    const size_t shift = w * (n - 1);
    return (x << shift) | do_repeat(x, w, n - 1);
}

/**
 * @brief Repeat pattern over 64-bit word.
 *
 * @code
 * assert(repeat(       0x1, 32) == 0x5555555555555555);
 * assert(repeat(       0x3, 16) == 0x3333333333333333);
 * assert(repeat(       0xF,  8) == 0x0F0F0F0F0F0F0F0F);
 * assert(repeat(      0xFF,  4) == 0x00FF00FF00FF00FF);
 * assert(repeat(    0xFFFF,  2) == 0x0000FFFF0000FFFF);
 * assert(repeat(0xFFFFFFFF,  1) == 0x00000000FFFFFFFF);

 * assert(repeat(       0x1, 16) == 0x1111111111111111);
 * assert(repeat(      0x12,  8) == 0x1212121212121212);
 * assert(repeat(    0x1234,  4) == 0x1234123412341234);
 * assert(repeat(0x12345678,  2) == 0x1234567812345678);
 * @endcode
 */
static uint64_t repeat(uint64_t x, size_t n)
{
    assert(n != 0);
    return do_repeat(x, 64 / n, n);
}

/**
 * @brief Selects `1 << n` bits over `1 << n` bits.
 *
 * @code
 * assert(select(0) == 0x5555555555555555);
 * assert(select(1) == 0x3333333333333333);
 * assert(select(2) == 0x0F0F0F0F0F0F0F0F);
 * assert(select(3) == 0x00FF00FF00FF00FF);
 * assert(select(4) == 0x0000FFFF0000FFFF);
 * assert(select(5) == 0x00000000FFFFFFFF);
 * @endcode
 */
static uint64_t select(size_t n)
{
    assert(n < 6);
    return repeat(bits(1 << n), 1 << (5 - n));
}

static uint64_t do_reverse(uint64_t x, size_t n)
{
    const size_t shift = (1ull << n);
    const uint64_t lo = select(n) << 0;
    const uint64_t hi = select(n) << shift;

    x = ((x & lo) << shift) | ((x & hi) >> shift);

    if (n == 0)
        return x;

    return do_reverse(x, n - 1);
}

uint64_t reverse64(uint64_t x)
{
    return do_reverse(x, 5);
}

uint32_t reverse32(uint32_t x)
{
    return do_reverse(x, 4);
}

uint16_t reverse16(uint32_t x)
{
    return do_reverse(x, 3);
}

uint8_t reverse8(uint8_t x)
{
    return do_reverse(x, 2);
}

int main()
{
    assert(repeat(       0x1, 32) == 0x5555555555555555);
    assert(repeat(       0x3, 16) == 0x3333333333333333);
    assert(repeat(       0xF,  8) == 0x0F0F0F0F0F0F0F0F);
    assert(repeat(      0xFF,  4) == 0x00FF00FF00FF00FF);
    assert(repeat(    0xFFFF,  2) == 0x0000FFFF0000FFFF);
    assert(repeat(0xFFFFFFFF,  1) == 0x00000000FFFFFFFF);

    assert(repeat(       0x1, 16) == 0x1111111111111111);
    assert(repeat(      0x12,  8) == 0x1212121212121212);
    assert(repeat(    0x1234,  4) == 0x1234123412341234);
    assert(repeat(0x12345678,  2) == 0x1234567812345678);

    assert(select(0) == 0x5555555555555555);
    assert(select(1) == 0x3333333333333333);
    assert(select(2) == 0x0F0F0F0F0F0F0F0F);
    assert(select(3) == 0x00FF00FF00FF00FF);
    assert(select(4) == 0x0000FFFF0000FFFF);
    assert(select(5) == 0x00000000FFFFFFFF);

    assert(reverse8 (              0xA5) == 0xA5);
    assert(reverse16(            0xFEA5) == 0xA57F);
    assert(reverse32(        0xFE0000A5) == 0xA500007F);
    assert(reverse64(0xFE00FE0000A500A5) == 0xA500A500007F007F);

    return 0;
}

具有未定义数据大小的位反转的最有效算法

Most Efficient Algorithm for Bit Reversal with undefined size of data

c

reverse

byte