我试图将一个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
有没有一种比较巧妙的方法来实现这种行为？
InterleaveBMN是二进制幻数的一种应用，可用于对比特进行交错。
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位一组与零位交错，并保留HTML标记，第一步后结果为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;
}
x = (x << 1) + x; 可以简化为 x *= 3; 证明：((x <<1) + x ) ~= (x * 2 + x) ~= x * 3. - Mr Anderson将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过度复杂的查找解决方案那样高效，但肯定比thndrwrks神秘的解决方案更容易理解。因此，它提供了一种可以应用于更多问题的技术，即使用小型查找表来解决更大的问题。
table声明为static const应该会提高性能。 - chqrlietable 具有局部作用域 (2) table 从未被用作lvalue (3) 函数中没有指针，因此没有任何东西可以指向table。 - user3386109如果你想要获得一些关于相对速度的估计，这里提供了一些社区维基测试代码。根据需要进行调整。
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
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中取出相应的位并进行掩码处理，并将其存储。然后，该位按其位位置进行移位，再进行OR运算，然后按其位位置加1进行移位，再进行OR运算，并将结果存储。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;
}
尝试了另一个速度快两倍的方法，但仍然比expand_bits()慢655/272。看起来这是最快的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;
}
//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或其他中间端序字节顺序的机器将会悄无声息地产生错误的结果（实际上曾经有过像PDP11这样的CPU...）。uint8_t 更一致，似乎更好 --> uint8_t outputBytes[4];uint32_t。uint8_t。但我决定不这样做，以便清楚地表明我实际上正在使用 char 类型，该类型在严格别名规则中有例外。据我所知，虽然标准要求 sizeof(char) 为 1，但它并不要求 char 正好是八位，也不要求 sizeof(uint8_t) 为 1。因此，我怀疑我没有标准许可来假设 uint8_t 与 unsigned char 相同，从而导致严格别名例外适用于 uint8_t。 - cmaster - reinstate monicauint32_t，而不是uint32。已经更正了。 - cmaster - reinstate monicauint8_t之间的问题很棘手。由于char至少有8位，而uint8_t恰好有8位（如果存在），因此其大小必须为1。但这仍然不使它成为字符类型，因此仍然不免于别名规则。我曾经看到过一个GCC错误跟踪器线程，其中有人建议利用uint8_t不能别名其他类型的规则。 - CodesInChaosinput16是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
uint8_t 来表示 bit_at_i 是有风险的——在计算 result 时，它会被转换为（带符号的）int。建议改用 uint32_t，这样可以避免问题。在掩码操作中，您也可以使用 1U 而不是 1，出于类似的原因，尽管现在很少有系统使用 16 位纯 int。 - Jonathan Lefflerint。像8051这样的产品比大多数ARM产品销售得更多。还有PIC16、AVR、各种HC08/05/12衍生产品和许多其他的8或16位MCU，我就是不记得了。然后还有DSP等等。 - too honest for this site我的解决方案旨在运行在主流的x86个人电脑上，而且简单通用。我并没有为了竞争最快和/或最短的实现而编写此代码。这只是另一种解决由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;
}
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;
}
input_mask &= 0b11;
result = input_mask;
result |= (input_mask << 1); // 1 * (2 bits out - 1)
result = (result & 0b0101) * 0b0011; // mask has bits set every 2 bits.
// mutiplied by 2 set bits for expansion
pdep？ - harold_pdep_u32内置函数吗？ - harold