位黑客：扩展位

Question

我正在尝试将

uint16_t

输入转换为

uint32_t

位掩码。输入中的一位会切换输出位掩码中的两位。以下是将 4 位输入转换为 8 位位掩码的示例：

Input    Output
ABCDb -> AABB CCDDb

A,B,C,D are individual bits

Example outputs:

0000b -> 0000 0000b
0001b -> 0000 0011b
0010b -> 0000 1100b
0011b -> 0000 1111b
....
1100b -> 1111 0000b
1101b -> 1111 0011b
1110b -> 1111 1100b
1111b -> 1111 1111b

有没有一种 bithack-y 的方法来实现这种行为？

Answer 1

通过二进制幻数交织位包含线索：

uint32_t expand_bits(uint16_t bits)
{
    uint32_t x = bits;

    x = (x | (x << 8)) & 0x00FF00FF;
    x = (x | (x << 4)) & 0x0F0F0F0F;
    x = (x | (x << 2)) & 0x33333333;
    x = (x | (x << 1)) & 0x55555555;

    return x | (x << 1);
}

前四个步骤连续将源位以 8、4、2、1 位为一组与零位交错，导致第一步后为

00AB00CD

，第二步后为

0A0B0C0D

，依此类推。最后一步将每个偶数位（包含原始源位）复制到相邻的奇数位中，从而实现所需的位排列。

可能有多种变体。最后一步也可以编码为

x + (x << 1)

或

3 * x

。前四步中的

|

运算符可以替换为

^

运算符。掩码也可以修改，因为某些位自然为零并且不需要清除。在某些处理器上，短掩码可以作为立即数合并到机器指令中，从而减少构建和/或加载掩码常量的工作量。增加无序处理器的指令级并行性并优化具有移位加法或整数乘加指令的处理器也可能是有利的。包含各种这些想法的一种代码变体是：

uint32_t expand_bits (uint16_t bits)
{
    uint32_t x = bits;

    x = (x ^ (x << 8)) & ~0x0000FF00;
    x = (x ^ (x << 4)) & ~0x00F000F0;
    x = x ^ (x << 2);
    x = ((x & 0x22222222) << 1) + (x & 0x11111111);
    x = (x << 1) + x;

    return x;
}

Answer 2

将 4 位输入映射到 8 位输出的最简单方法是使用 16 个条目的表。因此，只需从

uint16_t

中一次提取 4 位，进行查表，然后将 8 位值插入到输出中即可。

uint32_t expandBits( uint16_t input )
{
    uint32_t table[16] = {
        0x00, 0x03, 0x0c, 0x0f,
        0x30, 0x33, 0x3c, 0x3f,
        0xc0, 0xc3, 0xcc, 0xcf,
        0xf0, 0xf3, 0xfc, 0xff
    };

    uint32_t output;
    output  = table[(input >> 12) & 0xf] << 24;
    output |= table[(input >>  8) & 0xf] << 16;
    output |= table[(input >>  4) & 0xf] <<  8;
    output |= table[ input        & 0xf];
    return output;
}

这在性能和可读性之间提供了一个不错的折衷。它的性能不如 cmaster 的 over-the-top 查找解决方案，但它肯定比 thndrwrks 的神奇神秘解决方案更容易理解。因此，它提供了一种可以应用于更广泛问题的技术，即使用小型查找表来解决更大的问题。

Answer 3

如果您想估计相对速度，可以使用一些社区 wiki 测试代码。根据需要调整。

void f_cmp(uint32_t (*f1)(uint16_t x), uint32_t (*f2)(uint16_t x)) {
  uint16_t x = 0;
  do {
    uint32_t y1 = (*f1)(x);
    uint32_t y2 = (*f2)(x);
    if (y1 != y2) {
      printf("%4x %8lX %8lX\n", x, (unsigned long) y1, (unsigned long) y2);
    }
  } while (x++ != 0xFFFF);
}

void f_time(uint32_t (*f1)(uint16_t x)) {
  f_cmp(expand_bits, f1);
  clock_t t1 = clock();
  volatile uint32_t y1 = 0;
  unsigned n = 1000;
  for (unsigned i = 0; i < n; i++) {
    uint16_t x = 0;
    do {
      y1 += (*f1)(x);
    } while (x++ != 0xFFFF);
  }
  clock_t t2 = clock();
  printf("%6llu %6llu: %.6f %lX\n", (unsigned long long) t1,
          (unsigned long long) t2, 1.0 * (t2 - t1) / CLOCKS_PER_SEC / n,
          (unsigned long) y1);
  fflush(stdout);
}

int main(void) {
  f_time(expand_bits);
  f_time(expandBits);
  f_time(remask);
  f_time(javey);
  f_time(thndrwrks_expand);
  // now in the other order
  f_time(thndrwrks_expand);
  f_time(javey);
  f_time(remask);
  f_time(expandBits);
  f_time(expand_bits);
  return 0;
}

结果

     0    280: 0.000280 FE0C0000 // fast
   280    702: 0.000422 FE0C0000
   702   1872: 0.001170 FE0C0000
  1872   3026: 0.001154 FE0C0000
  3026   4399: 0.001373 FE0C0000 // slow

  4399   5740: 0.001341 FE0C0000
  5740   6879: 0.001139 FE0C0000
  6879   8034: 0.001155 FE0C0000
  8034   8470: 0.000436 FE0C0000
  8486   8751: 0.000265 FE0C0000

Answer 4

这是一个可行的实现：

uint32_t remask(uint16_t x)
{
    uint32_t i;
    uint32_t result = 0;
    for (i=0;i<16;i++) {
        uint32_t mask = (uint32_t)x & (1U << i);
        result |= mask << (i);
        result |= mask << (i+1);
    }
    return result;
}

在循环的每次迭代中，

uint16_t

中的相关位都会被屏蔽并存储。

然后将该位移位其位位置并与结果进行或运算，然后再次移位其位位置加 1 并与结果进行或运算。

Answer 5

如果您关心的是性能和简单性，那么您可能最好使用一个大的查找表（64k 个条目，每个条目 4 字节）。这样，您几乎可以使用任何您喜欢的算法来生成表，查找将只是一次内存访问。

如果那张桌子太大了，你不喜欢，你可以把它分开。例如，您可以使用 8 位查找表，其中包含 256 个条目，每个条目 2 字节。这样，您只需两次查找即可执行整个操作。额外的好处是，这种方法允许使用类型双关技巧，以避免使用位操作分割地址的麻烦：

//Implementation defined behavior ahead:
//Works correctly for both little and big endian machines,
//however, results will be wrong on a PDP11...
uint32_t getMask(uint16_t input) {
    assert(sizeof(uint16_t) == 2);
    assert(sizeof(uint32_t) == 4);
    static const uint16_t lookupTable[256] = { 0x0000, 0x0003, 0x000c, 0x000f, ... };

    unsigned char* inputBytes = (unsigned char*)&input;    //legal because we type-pun to char, but the order of the bytes is implementation defined
    char outputBytes[4];
    uint16_t* outputShorts = (uint16_t*)outputBytes;    //legal because we type-pun from char, but the order of the shorts is implementation defined
    outputShorts[0] = lookupTable[inputBytes[0]];
    outputShorts[1] = lookupTable[inputBytes[1]];
    uint32_t output;
    memcpy(&output, outputBytes, 4);    //can't type-pun directly from uint16 to uint32_t due to strict aliasing rules
    return output;
}

上面的代码通过仅向/从

char

进行强制转换来绕过严格的别名规则，这是严格别名规则的明确例外。它还通过按照与输入分割相同的顺序构建结果来解决小/大端字节顺序的影响。然而，它仍然暴露了实现定义的行为：具有

1, 0, 3, 2

字节顺序或其他 middle endian 顺序 的机器将默默地产生错误的结果（实际上已经有像 PDP11 这样的 CPU...）。

当然，您可以进一步拆分查找表，但我怀疑这对您有任何好处。

Answer 6

一个简单的循环。也许还不够hacky？

uint32_t thndrwrks_expand(uint16_t x) {
  uint32_t mask = 3;
  uint32_t y = 0;
  while (x) {
    if (x&1) y |= mask;
    x >>= 1;
    mask <<= 2;
  }
  return y;
}

尝试了另一种速度快两倍的方法。还是 655/272 慢如

expand_bits()

。似乎是最快的 16 循环迭代解决方案。

uint32_t thndrwrks_expand(uint16_t x) {
  uint32_t y = 0;
  for (uint16_t mask = 0x8000; mask; mask >>= 1) {
    y <<= 1;
    y |= x&mask;
  }
  y *= 3;
  return y;
}

Answer 7

试试这个，其中

input16

是 uint16_t 输入掩码：

uint32_t input32 = (uint32_t) input16;
uint32_t result = 0;
uint32_t i;
for(i=0; i<16; i++)
{
    uint32_t bit_at_i = (input32 & (((uint32_t)1) << i)) >> i;
    result |= ((bit_at_i << (i*2)) | (bit_at_i << ((i*2)+1)));
}
// result is now the 32 bit expanded mask

Answer 8

我的解决方案旨在在主流 x86 PC 上运行，并且简单且通用。我写这篇文章并不是为了争夺最快和/或最短的实现。这只是解决OP提交的问题的另一种方式。

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define BITS_TO_EXPAND (4U)
#define SIZE_MAX (256U)

static bool expand_uint(unsigned int *toexpand,unsigned int *expanded);

int main(void)
{
    unsigned int in = 12;
    unsigned int out = 0;
    bool success;
    char buff[SIZE_MAX];

    success = expand_uint(&in,&out);
    if(false == success)
    {
        (void) puts("Error: expand_uint failed");
        return EXIT_FAILURE;
    }
    (void) snprintf(buff, (size_t) SIZE_MAX,"%u expanded is %u\n",in,out);
    (void) fputs(buff,stdout);
    return EXIT_SUCCESS;
}
/*
** It expands an unsigned int so that every bit in a nibble is copied twice
** in the resultant number. It returns true on success, false otherwise.
*/
static bool expand_uint(unsigned int *toexpand,unsigned int *expanded)
{
    unsigned int i;
    unsigned int shifts = 0;
    unsigned int mask;

    if(NULL == toexpand || NULL == expanded)
    {
        return false;
    }
    *expanded = 0;
    for(i = 0; i < BIT_TO_EXPAND; i++)
    {
        mask = (*toexpand >> i) & 1;
        *expanded |= (mask << shifts);
        ++shifts;
        *expanded |= (mask << shifts);
        ++shifts;
    }
    return true;
}

Answer 9

我来晚了一点，但这里有一个扩展位掩码的通用算法。我需要将 8 位掩码扩展为 64 位整数...希望有人会发现这个算法有用。

它可能不是最快的，但它适用于硬件限制内的任意位数和扩展因子。

unsigned long expand_bitmask(unsigned long mask, unsigned nbits_in, unsigned expand_by)
{
    unsigned long result, mask_out;
    int i, shift;

    assert(nbits_in * expand_by <= 8 * sizeof(unsigned));

    // mask input
    mask &= (unsigned long)(-1) >> ((8 * sizeof(unsigned long)) - nbits_in);

    result = 0;     // holds results
    mask_out = 0;   

    for (i = 0, shift = 0; i < nbits_in; ++i, shift += expand_by)
    {
        result   |= (mask << (shift - i));  // the shift differential places the bits
                                            // in the right place.
                                            // equivalent to mask << (i * (shift - 1))
        mask_out |= (1 << shift);           // this will mask the shited bits we want to keep
                                            // equivalent to 1 << (i * shift)
    }

    result &= mask_out;   // wipe out the garbage bits

    // multiply by a mask representing the number of wanted bits.
    result *= (unsigned long)(-1) >> ((8* sizeof(unsigned long)) - expand_by);
    return result;
}

当然，由于您通常知道输入和输出的位数，因此该算法可以帮助您预先计算移位、清理掩码和因子，以获得相当快的计算时间，即每位 1 次移位 + 1 和和 1 个乘法总运算。