c - 快速位连接反转参数之一

Question

我需要将两个变量合并为一个，如下例所示:

x = 0b110101
y = 0b10011

merged(x,y) -> 0b11010111001
merged(y,x) -> 0b10011101011

因此，y 被反转并连接到 x，没有不必要的零(结果的最后一位始终为 1)

换句话说:merged(abcdefg, hijklm) 导致 abcdefgmlkjih 其中 a 和 h 是 1

在 C 中执行此操作的最有效方法是什么

编辑:最有效 = 最快，sizeof(x) = sizeof(y) = 1，CHAR_BIT= 8

EDIT2:由于问题已被搁置，我将在此处发布摘要:更多限制和更多细节:

目标语言:支持 64 位操作的 C

对于这个确切的问题，最快的方法是评论中建议的 256 元素查找表，它返回高位 N 的索引和第二个参数的反向值，因此我们可以将第一个参数转移到N 的左边，并用第二个参数的反向值执行按位 or。

如果有人需要对大于 8 位的参数有良好的性能(查找表不是一个选项)，他们可以:

1. 使用 de Bruijn 算法查找高位索引。 32 位示例:

   uint32_t msbDeBruijn32( uint32_t v )
   {
       static const int MultiplyDeBruijnBitPosition[32] =
       {
           0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
           8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
       };
   
       v |= v >> 1; // first round down to one less than a power of 2
       v |= v >> 2;
       v |= v >> 4;
       v |= v >> 8;
       v |= v >> 16;
   
       return MultiplyDeBruijnBitPosition[( uint32_t )( v * 0x07C4ACDDU ) >> 27];
   }
   

取自这个问题: Find most significant bit (left-most) that is set in a bit array

1. 使用这个 bit twiddling hack 以字节为单位(一个一个地)反转第二个参数的位

   unsigned char b; // reverse this (8-bit) byte    
   b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;  
   

取自此处:http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

所以，这个问题现在可以关闭/删除了

Answer 1

解决方案

在 C++ 和 C 中这应该可以解决问题:

unsigned int merged(unsigned char a, unsigned char b) {
    unsigned int r = a; 
    for (; b; b>>=1) 
        r = (r<<1)|(b&1);
    return r;
}

我认为没有比这更有效的方法了。这里是online demo .

它是如何工作的？

这通过从第一个参数开始构建结果来工作:

 r is 0b110101; 

然后呢left-shifts r，也就是使用你的术语，比如在 r 的最低端连接一个 0:

 0b110101 << 1 is  0b1101010; 

同时我们用 bitwise and 得到 b 的最低位, 然后使用 bitwise or 将 r 的最低位设置为相同的值:

 0b10011 & 1 is 0b00001
 so (0b110101 << 1)|(0b10011 & 1) is 0b1101011;

然后我们右移 b 以相同的方式处理下一个最低位:

 0b10011 >> 1 is 0b1001; 

只要 b 中还剩下一些位。

重要说明

您必须小心使用类型以避免溢出的风险。因此，对于 2 个 unsigned char 作为输入，您可以使用 unsigned int 作为输出。

请注意，如果左移可能导致符号位发生变化，则使用有符号整数会有风险。这就是 unsigned 在这里很重要的原因。