Как поразрядно перевернуть массив символов по диагонали в C / C ++ или Cuda?
У меня есть массив символов char input[8] = "abcdabcd"и я хочу поразрядно перевернуть его по диагонали, что означает
input:
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
Очевидно, что мы можем использовать два цикла в сочетании с побитовой или операцией для установки целевого бита один за другим, однако это означает, что нам нужно по крайней мере 64 * n операции, которые я считаю неэффективными.
Поскольку ввод и вывод предназначены только для чтения памяти в разных направлениях (по строкам или по столбцам), есть ли более эффективный способ?
Кроме того, я думаю, что это вполне приемлемо и имеет смысл делать эту операцию, основываясь на специальной компоновке памяти, или изменять число или символы в массиве.
Спасибо!
Решение
Вот мой код, основанный на уловке из Восторг Хакера. Хотя это код процессора, он может быть легко преобразован в параллельный код CUDA.
Этот код сам по себе для транспонирования растровых изображений произвольных размеров. Что вам действительно нужно, так это код для переноса uint64_t х в другой 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 );
}
Другие решения
Других решений пока нет …