C/C++やCudaでは、char配列を斜めにビット単位で効果的に反転する方法はありますか？

Question

inputを意味している、私はchar配列char input[8] = "abcdabcd"を持っている、と私は対角線でそれを反転ビット単位にしたい：

input[0] == 'a': 0 1 1 0 0 0 0 1 
input[1] == 'b': 0 1 1 0 0 0 1 0 
input[2] == 'c': 0 1 1 0 0 0 1 1 
input[3] == 'd': 0 1 1 0 0 1 0 0 
input[4] == 'a': 0 1 1 0 0 0 0 1 
input[5] == 'b': 0 1 1 0 0 0 1 0 
input[6] == 'c': 0 1 1 0 0 0 1 1 
input[7] == 'd': 0 1 1 0 0 1 0 0 

output：

    a b c d a b c d 
output[0] == 0 : 0 0 0 0 0 0 0 0 
output[1] == 255 : 1 1 1 1 1 1 1 1 
output[2] == 255 : 1 1 1 1 1 1 1 1 
output[3] == 0 : 0 0 0 0 0 0 0 0 
output[4] == 0 : 0 0 0 0 0 0 0 0 
output[5] == 17 : 0 0 0 1 0 0 0 1 
output[6] == 102 : 0 1 1 0 0 1 1 0 
output[7] == 170 : 1 0 1 0 1 0 1 0 

我々は2つのループを使用できることは明らかですビット単位の操作やターゲットビットを1つずつ設定する操作と組み合わされていますが、これは少なくとも64 * nの操作が必要であることを意味します。
入力と出力は異なる方向（行単位または列単位）でメモリを読み取ることにすぎないので、それ以上の効果がありますか？
また、特別なメモリレイアウトに基づいてこの操作を行うことや、配列の数や文字を変更することは、かなり受け入れられ、意味があると思います。
ありがとうございます！

Answer 1

ここはHacker's Delightからのトリックに基づく私のコードです。これはCPUコードですが、パラレルCUDAコードに簡単に変換できます。

このコード自体は、任意のサイズのビットマップを転置するためのものです。本当に必要なのは、uint64_t xを別のuint64_tに転記するコードです。

using BitBlock = uint8_t; 
using BitBlocks = std::vector<BitBlock>; 

void FPTransMap::transpose_bitmap(BitBlocks& bitmap, size_type blocks_per_row) 
{ 
    assert(bitmap.size() % blocks_per_row == 0); 
    assert((bitmap.size()/blocks_per_row) % 8 == 0); 

    BitBlocks transposed(bitmap.size()); 
    size_type nrow = bitmap.size()/blocks_per_row, row_blocks = nrow/8; 
    for (index_type i = 0; i < row_blocks; ++i) { 
     for (index_type j = 0; j < blocks_per_row; ++j) { 
      uint64_t x = (uint64_t(bitmap[ i * 8  * blocks_per_row + j ]) << 56) | 
         (uint64_t(bitmap[ (i * 8 + 1) * blocks_per_row + j ]) << 48) | 
         (uint64_t(bitmap[ (i * 8 + 2) * blocks_per_row + j ]) << 40) | 
         (uint64_t(bitmap[ (i * 8 + 3) * blocks_per_row + j ]) << 32) | 
         (uint64_t(bitmap[ (i * 8 + 4) * blocks_per_row + j ]) << 24) | 
         (uint64_t(bitmap[ (i * 8 + 5) * blocks_per_row + j ]) << 16) | 
         (uint64_t(bitmap[ (i * 8 + 6) * blocks_per_row + j ]) << 8) | 
         (uint64_t(bitmap[ (i * 8 + 7) * blocks_per_row + j ])); 
      uint64_t y = (x & 0x8040201008040201LL) | 
         ((x & 0x0080402010080402LL) << 7) | 
         ((x & 0x0000804020100804LL) << 14) | 
         ((x & 0x0000008040201008LL) << 21) | 
         ((x & 0x0000000080402010LL) << 28) | 
         ((x & 0x0000000000804020LL) << 35) | 
         ((x & 0x0000000000008040LL) << 42) | 
         ((x & 0x0000000000000080LL) << 49) | 
         ((x >> 7) & 0x0080402010080402LL) | 
         ((x >> 14) & 0x0000804020100804LL) | 
         ((x >> 21) & 0x0000008040201008LL) | 
         ((x >> 28) & 0x0000000080402010LL) | 
         ((x >> 35) & 0x0000000000804020LL) | 
         ((x >> 42) & 0x0000000000008040LL) | 
         ((x >> 49) & 0x0000000000000080LL); 
      transposed[ (j * 8) * row_blocks + i ]  = uint8_t((y >> 56) & 0xFF); 
      transposed[ (j * 8 + 1) * row_blocks + i ] = uint8_t((y >> 48) & 0xFF); 
      transposed[ (j * 8 + 2) * row_blocks + i ] = uint8_t((y >> 40) & 0xFF); 
      transposed[ (j * 8 + 3) * row_blocks + i ] = uint8_t((y >> 32) & 0xFF); 
      transposed[ (j * 8 + 4) * row_blocks + i ] = uint8_t((y >> 24) & 0xFF); 
      transposed[ (j * 8 + 5) * row_blocks + i ] = uint8_t((y >> 16) & 0xFF); 
      transposed[ (j * 8 + 6) * row_blocks + i ] = uint8_t((y >> 8) & 0xFF); 
      transposed[ (j * 8 + 7) * row_blocks + i ] = uint8_t(y & 0xFF); 
     } 
    } 
    std::swap(bitmap, transposed); 
}