我怎样才能有效地改变比特？

我需要以偶数索引落在低位字节中的方式对16位无符号整数进行混洗，并且奇数索引落在高位字节中。

input: fedcba98 76543210 (contiguously numbered) output: fdb97531 eca86420 (even and odd separated) 

我的代码目前看起来像这样：

 typedef unsigned short u16; u16 segregate(u16 x) { u16 g = (x & 0x0001); u16 h = (x & 0x0004) >> 1; u16 i = (x & 0x0010) >> 2; u16 j = (x & 0x0040) >> 3; u16 k = (x & 0x0100) >> 4; u16 l = (x & 0x0400) >> 5; u16 m = (x & 0x1000) >> 6; u16 n = (x & 0x4000) >> 7; u16 o = (x & 0x0002) << 7; u16 p = (x & 0x0008) << 6; u16 q = (x & 0x0020) << 5; u16 r = (x & 0x0080) << 4; u16 s = (x & 0x0200) << 3; u16 t = (x & 0x0800) << 2; u16 u = (x & 0x2000) << 1; u16 v = (x & 0x8000); return g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v; } 

我想知道是否有一个比简单地提取和移动每个单独位更优雅的解决方案？

Answer 1

有一个非常方便的Web资源，可以帮助解决许多位置换问题： 用于位置换的代码生成器 。 在这种特殊情况下，向该页面输入“0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15”会产生相当快的代码。

不幸的是，这个代码生成器无法生成64位代码（尽管任何人都可以下载源代码并添加此选项）。 因此，如果我们需要使用64位指令并行执行4个排列，我们必须手动将所有涉及的位掩码扩展到64位：

 uint64_t bit_permute_step(uint64_t x, uint64_t m, unsigned shift) { uint64_t t; t = ((x >> shift) ^ x) & m; x = (x ^ t) ^ (t << shift); return x; } uint64_t segregate4(uint64_t x) { // generated by http://programming.sirrida.de/calcperm.php, extended to 64-bit x = bit_permute_step(x, 0x2222222222222222ull, 1); x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0cull, 2); x = bit_permute_step(x, 0x00f000f000f000f0ull, 4); return x; } 

使用SSE指令可以进一步提高并行度（一次8或16次排列）。 （最新版本的gcc可以自动对此代码进行矢量化）。

如果不需要并行性并且数据高速缓存未被程序的其他部分广泛使用，则更好的替代方案是使用查找表。 在其他答案中已经讨论了各种LUT的批准，还有一些可以在这里说：

1. 从不置换16位字的第一位和最后一位，我们只需要将位1×14混洗。 所以（如果我们想用单个LUT访问来执行任务）就足够了一个具有16K条目的LUT，这意味着32K的内存。
2. 我们可以结合表查找和计算方法。 单个256字节表中的两次查找可以分别对每个源字节进行混洗。 在此之后我们只需要交换两个中间的4位半字节。 这允许保持查找表较小，仅使用2次存储器访问，并且不需要太多计算（即平衡计算和存储器访问）。

这是第二种方法的实施：

 #define B10(x) x+0x00, x+0x10, x+0x01, x+0x11 #define B32(x) B10(x+0x00), B10(x+0x20), B10(x+0x02), B10(x+0x22) #define B54(x) B32(x+0x00), B32(x+0x40), B32(x+0x04), B32(x+0x44) uint8_t lut[256] = {B54( 0x00), B54( 0x80), B54( 0x08), B54( 0x88)}; #undef B54 #undef B32 #undef B10 uint_fast16_t segregateLUT(uint_fast16_t x) { uint_fast16_t low = lut[x & 0x00ff]; low |= low << 4; uint_fast16_t high = lut[x >> 8] << 4; high |= high << 4; return (low & 0x0f0f) | (high & 0xf0f0); } 

但是最快的方法（如果可移植性不是问题）是使用来自BMI2指令集的pext指令， 如Nils Pipenbrinck所述 。 使用一对64位pext我们可以并行执行4个16位shuffle。 由于pext指令完全适用于这种位排列，因此这种方法很容易优于其他所有方法。

Answer 2

其他人展示的表格方法是最便携的版本，可能非常快。

如果您想利用特殊指令集，还有其他一些选项。 例如，对于Intel Haswell及更高版本，可以使用以下方法（需要BMI2指令集扩展）：

 unsigned segregate_bmi (unsigned arg) { unsigned oddBits = _pext_u32(arg,0x5555); unsigned evenBits = _pext_u32(arg,0xaaaa); return (oddBits | (evenBits << 8)); } 

Answer 3

您可以为16位数字的每个字节使用256字节的表，精心设计以满足您的偶数/奇数条件。 手动编写表条目（或使用您已有的算法）来创建表，然后在编译时进行混洗。 这基本上是一个翻译表概念。

Answer 4

您可以为16位数字的每个字节使用256字节的表，精心设计以满足您的偶数/奇数条件。

啊，是的，查找救援表:)你甚至可以用一张桌子和一个额外的class次来做：

 u16 every_other[256] = { 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x02, 0x03, 0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 0x04, 0x05, 0x04, 0x05, 0x06, 0x07, 0x06, 0x07, 0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 0x08, 0x09, 0x08, 0x09, 0x0a, 0x0b, 0x0a, 0x0b, 0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f, 0x0c, 0x0d, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0f}; u16 segregate(u16 x) { return every_other[x & 0xff] | every_other[(x >> 8)] << 4 | every_other[(x >> 1) & 0xff] << 8 | every_other[(x >> 9)] << 12; } 

Answer 5

表。 但是在编译时生成它们！

 namespace details { constexpr uint8_t bit( unsigned byte, unsigned n ) { return (byte>>n)&1; } constexpr uint8_t even_bits(uint8_t byte) { return bit(byte, 0) | (bit(byte, 2)<<1) | (bit(byte, 4)<<2) | (bit(byte, 6)<<3); } constexpr uint8_t odd_bits(uint8_t byte) { return even_bits(byte/2); } templatestruct indexes{using type=indexes;}; templatestruct make_indexes:make_indexes{}; templatestruct make_indexes<0,Is...>:indexes{}; templateusing make_indexes_t=typename make_indexes::type; template constexpr std::array< uint8_t, 256 > even_bit_table( indexes ) { return { even_bits(Is)... }; } template constexpr std::array< uint8_t, 256 > odd_bit_table( indexes ) { return { odd_bits(Is)... }; } constexpr std::array< uint8_t, 256 > even_bit_table() { return even_bit_table( make_indexes_t<256>{} ); } constexpr std::array< uint8_t, 256 > odd_bit_table() { return odd_bit_table( make_indexes_t<256>{} ); } static constexpr auto etable = even_bit_table(); static constexpr auto otable = odd_bit_table(); } uint8_t constexpr even_bits( uint16_t in ) { return details::etable[(uint8_t)in] | ((details::etable[(uint8_t)(in>>8)])<<4); } uint8_t constexpr odd_bits( uint16_t in ) { return details::otable[(uint8_t)in] | ((details::otable[(uint8_t)(in>>8)])<<4); } 

实例

Answer 6

你对64位偶数和奇数位混洗的答案是不准确的。 要将16位解决方案扩展到64位解决方案，我们不仅需要扩展掩码，还需要覆盖从1到16的交换间隔：

 x = bit_permute_step(x, 0x2222222222222222, 1); x = bit_permute_step(x, 0x0c0c0c0c0c0c0c0c, 2); x = bit_permute_step(x, 0x00f000f000f000f0, 4); **x = bit_permute_step(x, 0x0000ff000000ff00, 8); x = bit_permute_step(x, 0x00000000ffff0000, 16);** 

Answer 7

赞成做空：

 unsigned short segregate(unsigned short x) { x = (x & 0x9999) | (x >> 1 & 0x2222) | (x << 1 & 0x4444); x = (x & 0xC3C3) | (x >> 2 & 0x0C0C) | (x << 2 & 0x3030); x = (x & 0xF00F) | (x >> 4 & 0x00F0) | (x << 4 & 0x0F00); return x; }