c - 位选择算法

Question

我想找到一种有效的方法，使用 C 中另一个流的位来从一个流中选择位。处理的数据量为 TB，因此速度很重要。

“位选择器”的作用是从位序列中仅选择某些位。例如，如果源流为 [ 1, 0, 1, 0, 1, 0, 1 ]，选择标准为 [ 1, 1, 0, 0, 1, 0, 0 ]，则结果将为 [ 1 , 0, 1]。

执行此操作的示例如下:

uint64_t source[5];
source[0] = 1234567890987654321;
source[1] = 3456789098765432198;
source[2] = 5678909876543219876;
source[3] = 7890987654321987654;
source[4] = 9098765432198765432;
uint64_t selector[5];
selector[0] = 8214263800482614621;
selector[1] = 4251759498365531188;
selector[2] = 1628009771533217836;
selector[3] = 6890182644227957152;
selector[4] = 3018964452491735032;
size_t count_values = 5;
uint64_t result[5];

size_t xCurrentResultBits = 0;
uint64_t result_value = 0;
size_t result_index = 0;
for( size_t xSelector = 0; xSelector < count_values; xSelector ){
   uint64_t current_selector = selector[ xSelector ];
   uint64_t current_source = source[ xSelector ];
   for( size_t bit = 0; bit < 64; bit++ ){
      uint64_t mask = 1;
      mask = mask << bit;
      uint64_t selector_value = current_selector | mask;
      if( selector_value > 0 ){ // keep the bit in the source
         uint64_t source_value = current_source | mask;
         result_value = result_value << 1;
         if( source_value > 0 ) result_value = result_value + 1;
         xCurrentResultBits++
      } else {
         // throw away source bit
      }
      if( xCurrentResultBits == 63 ){ // filled up a result value
         result[ result_index ] = result_value;
         result_index++;
         result_value = 0;
         xCurrentResultBits = 0;
      }
   }
}

问题是这个方法可能比它应有的速度慢很多。有没有一种众所周知的算法可以快速做到这一点？

Answer 1

我会根据查找表逐字节进行操作。

创建一个查找表，为您提供要或(移位后)到输出的当前字节和下一个字节的位模式。该表由 [sourceByte][selectorByte] 索引，因此它是一个 256*256 字节值表。

将表结果移位当前输出字节中已占用的位数，并将其或到当前和下一个字节(或者可能对结果使用更大的 block )。

将输出位位置和字节指针前进来自选择器字节的位数(另一个表字节[256]可能比位调整更容易)。

但最后，您必须分析程序并尝试哪种方法更快(以及是否位调整确实占了运行时的显着部分)。