将32 0/1值打包到单个32位变量的位中的最快方法是什么？
我正在使用x86或x86_64机器。 我有一个数组unsigned int a[32]所有元素的值都是0或1.我想设置单个变量unsigned int b这样(b >> i) & 1 == a[i]将保持为a的所有32个元素。 我正在使用Linux上的GCC（我猜不应该这么做）。
在C中执行此操作的最快方法是什么？
最近的x86处理器上最快的方法可能是使用MOVMSKB系列指令，它们提取SIMD字的MSB并将它们打包成普通的整数寄存器。
我担心SIMD内在函数不是我真正的东西，但是如果你有一个配备AVX2的处理器，那么这些内容应该有用：
uint32_t bitpack(const bool array[32]) { __mm256i tmp = _mm256_loadu_si256((const __mm256i *) array); tmp = _mm256_cmpgt_epi8(tmp, _mm256_setzero_si256()); return _mm256_movemask_epi8(tmp); }
假设sizeof(bool) = 1 。 对于较旧的SSE2系统，您必须将一对128位操作串联起来。 将数组对齐在32字节边界上，并应保存另一个周期左右。
其他答案包含一个明显的循环实现。
这是第一个变种：
unsigned int result=0; for(unsigned i = 0; i < 32; ++i) result = (result<<1) + a[i];
在现代的x86 CPU上，我认为寄存器中任何距离的移位都是不变的，这种解决方案也不会更好。 你的CPU可能不那么好; 这段代码最大限度地降低了长途class次的成本; 它执行32个1位移位，每个CPU都可以执行（您可以始终将结果添加到自身以获得相同的效果）。 其他人所示的明显的循环实现通过移动等于循环索引的距离来进行大约900（总和32）1位移位。 （参见@Jongware对评论差异的测量结果; x86上的长时间偏移不是单位时间）。
让我们尝试更激进的事情。
假设你可以以某种方式将m个布尔值打包成一个int（通常你可以为m == 1执行此操作），并且你有两个实例变量i1和i2包含这样的m个打包位。
然后下面的代码将m * 2个布尔值打包成一个int：
(i1<
使用这个我们可以打包2 ^ n位如下：
unsigned int a2[16],a4[8],a8[4],a16[2], a32[1]; // each "aN" will hold N bits of the answer a2[0]=(a1[0]<<1)+a2[1]; // the original bits are a1[k]; can be scalar variables or ints a2[1]=(a1[2]<<1)+a1[3]; // yes, you can use "|" instead of "+" ... a2[15]=(a1[30]<<1)+a1[31]; a4[0]=(a2[0]<<2)+a2[1]; a4[1]=(a2[2]<<2)+a2[3]; ... a4[7]=(a2[14]<<2)+a2[15]; a8[0]=(a4[0]<<4)+a4[1]; a8[1]=(a4[2]<<4)+a4[3]; a8[1]=(a4[4]<<4)+a4[5]; a8[1]=(a4[6]<<4)+a4[7]; a16[0]=(a8[0]<<8)+a8[1]); a16[1]=(a8[2]<<8)+a8[3]); a32[0]=(a16[0]<<16)+a16[1];
假设我们友好的编译器将[k]解析为（标量）直接存储器访问（如果没有，你可以简单地用an_k替换变量an [k]），上面的代码（抽象地）抽取63次，31次写入，31次移位和31添加。 （有64位的明显扩展）。
在现代的x86 CPU上，我认为寄存器中任何距离的移位都是不变的。 如果没有，这段代码可以最大限度地降低长途class次的成本; 它实际上是64位1位移位。
在x64机器上，除了原始布尔值a1 [k]的提取之外，我希望编译器可以调度所有其余的标量以适应寄存器，因此32个内存提取，31个移位和31个添加。 很难避免提取（如果原始的布尔分散在周围）并且移位/添加匹配明显的简单循环。 但是没有循环，所以我们避免了32个增量/比较/索引操作。
如果起始布尔值确实在数组中，则每个位占据底部位，否则为零字节：
bool a1[32];
那么我们可以滥用我们的内存布局知识来一次取几个：
a4[0]=((unsigned int)a1)[0]; // picks up 4 bools in one fetch a4[1]=((unsigned int)a1)[1]; ... a4[7]=((unsigned int)a1)[7]; a8[0]=(a4[0]<<1)+a4[1]; a8[1]=(a4[2]<<1)+a4[3]; a8[2]=(a4[4]<<1)+a4[5]; a8[3]=(a8[6]<<1)+a4[7]; a16[0]=(a8[0]<<2)+a8[1]; a16[0]=(a8[2]<<2)+a8[3]; a32[0]=(a16[0]<<4)+a16[1];
在这里，我们的成本是8次（4组）布尔，7class和7加。 同样，没有循环开销。 （同样有一个明显的64位泛化）。
为了比这更快，你可能不得不放入汇编程序并使用那里可用的许多精彩和奇怪的指令（向量寄存器可能具有可能很好地工作的分散/收集操作）。
一如既往，这些解决方案需要进行性能测试。
如果sizeof(bool) == 1那么你可以使用这里讨论的技术在快速乘法的计算机中将8个bool一次打包成8位（更多的是128位乘法）
假设bo a[0]到a[7]的最低有效位分别为ah。 将这8个连续的bool作为一个64位字处理并加载它们，我们将在小端机器中以相反的顺序得到这些位。 现在我们将进行乘法运算（此处点为零位）
| a7 || a6 || a4 || a4 || a3 || a2 || a1 || a0 | .......h.......g.......f.......e.......d.......c.......b.......a x 1000000001000000001000000001000000001000000001000000001000000001 ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ ↑......h.↑.....g..↑....f...↑...e....↑..d.....↑.c......↑b.......a ↑.....g..↑....f...↑...e....↑..d.....↑.c......↑b.......a ↑....f...↑...e....↑..d.....↑.c......↑b.......a + ↑...e....↑..d.....↑.c......↑b.......a ↑..d.....↑.c......↑b.......a ↑.c......↑b.......a ↑b.......a a ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ = abcdefghxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
添加箭头以便更容易在幻数中看到设置位的位置。 此时，在最高字节中放置了8个最低有效位，我们只需要将剩余的位屏蔽掉
因此，通过使用幻数0b1000000001000000001000000001000000001000000001000000001000000001或0x8040201008040201我们有以下代码
inline int pack8b(bool* a) { uint64_t t = *((uint64_t*)a); return (0x8040201008040201*t >> 56) & 0xFF; } int pack32b(bool* a) { return (pack8b(a) << 24) | (pack8b(a + 8) << 16) | (pack8b(a + 16) << 8) | (pack8b(a + 24)); }
当然，您需要确保bool数组正确对齐8字节。 您也可以展开代码并对其进行优化，例如只移位一次而不是向左移动56位
对不起，我忽略了这个问题，看到了doynax的boolarrays以及误读了“32 0/1值”并认为他们是32 bool s。 当然，使用相同的技术也可以使用128位乘法同时打包4 uint32_t ，或者使用正常的64位乘法同时打包2个，但它比打包字节的效率低很多
在具有BMI2的较新x86 CPU上，可以使用PEXT指令。 上面的pack8bfunction可以替换为
_pext_u64(*((uint64_t*)a), 0x0101010101010101ULL);
并且要打包2 uint32_t因为问题需要使用
_pext_u64(*((uint64_t*)a), (1ULL << 32) | 1ULL);
我可能会这样做：
unsigned a[32] = { 1, 0, 0, 1, 1, 1, 0 ,0, 1, 0, 0, 0, 1, 1, 0, 0 , 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1 }; int main() { unsigned b = 0; for(unsigned i = 0; i < sizeof(a) / sizeof(*a); ++i) b |= a[i] << i; printf("b: %u\n", b); }
编译器优化可以很好地展开，但万一你总是可以尝试：
int main() { unsigned b = 0; b |= a[0]; b |= a[1] << 1; b |= a[2] << 2; b |= a[3] << 3; // ... etc b |= a[31] << 31; printf("b: %u\n", b); }
要确定最快的方式，请计算所有各种建议。 这是最好的“最快”（使用标准C，没有处理器相关的SSE或类似） ：
unsigned int bits[32][2] = { {0,0x80000000},{0,0x40000000},{0,0x20000000},{0,0x10000000}, {0,0x8000000},{0,0x4000000},{0,0x2000000},{0,0x1000000}, {0,0x800000},{0,0x400000},{0,0x200000},{0,0x100000}, {0,0x80000},{0,0x40000},{0,0x20000},{0,0x10000}, {0,0x8000},{0,0x4000},{0,0x2000},{0,0x1000}, {0,0x800},{0,0x400},{0,0x200},{0,0x100}, {0,0x80},{0,0x40},{0,0x20},{0,0x10}, {0,8},{0,4},{0,2},{0,1} }; unsigned int b = 0; for (i=0; i< 32; i++) b |= bits[i][a[i]];
数组中的第一个值是最左边的位：最高可能值。
用一些粗略的时序测试概念validation表明，这确实不比使用b |= (a[i]<<(31-i))的简单循环更好：
Ira 3618 ticks naive, unrolled 5620 ticks Ira, 1-shifted 10044 ticks Galik 10265 ticks Jongware, using adds 12536 ticks Jongware 12682 ticks naive 13373 ticks
（相对时序，使用相同的编译器选项。）
（'adds'例程是我的，索引替换为两个索引数组的指针和显式添加。它慢了10％，这意味着我的编译器有效地优化了索引访问。很高兴知道。）
unsigned b=0; for(int i=31; i>=0; --i){ b<<=1; b|=a[i]; }
您的问题是使用的好机会--> ，也称为downto运算符：
unsigned int a[32]; unsigned int b = 0; for (unsigned int i = 32; i --> 0;) { b += b + a[i]; }
使用-->的优点是它适用于有符号和无符号循环索引类型。
这种方法具有可移植性和可读性，可能无法生成最快的代码，但是clang会展开循环并产生不错的性能，请参阅https://godbolt.org/g/6xgwLJ