Столбец матрицы отображения C ++ в рангово — битовые манипуляции

Question

Столбец матрицы отображения C ++ в рангово — битовые манипуляции

У меня есть (двоичные) матрицы, представленные uint64_t (из C ++ 11). И я хотел бы иметь возможность эффективно отображать любой столбец в первый ранг. Например

0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0

uint64_t matrice = 0x4040400040400040uLL;
uint64_t matrice_2 = map(matrice, ColumnEnum::Column2);

1 1 1 0 1 1 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

matrice_2 содержит 0xED00000000000000uLL;

3

bit-manipulation c++c++11 matrix transpose

Решение

Другие решения

Хорошая маленькая загадка. Вот разумно читаемая версия:

matrice = (matrice >> (8ull - column)) & 0x0101010101010101ull;
uint64_t result((  ((matrice >>  0ul)  & 0x01ull)
| ((matrice >>  7ul)  & 0x02ull)
| ((matrice >> 14ull) & 0x04ull)
| ((matrice >> 21ull) & 0x08ull)
| ((matrice >> 28ull) & 0x10ull)
| ((matrice >> 35ull) & 0x20ull)
| ((matrice >> 42ull) & 0x40ull)
| ((matrice >> 49ull) & 0x80ull)) << 56ull);

3

Сначала определите битовую маску для каждого столбца:

uint64_t columns[8] = {
0x8080808080808080uLL,
0x4040404040404040uLL,
//...
0x0101010101010101uLL
};

Применив битовую маску столбца к вашей «матрице», вы получите только этот столбец:

uint64_t col1 = matrice & columns[1]; // second column - rest is empty

сдвигая, вы можете получить только первый случай столбца:

uint64_t col0 = (col1 << 1); // second column - rest is empty
//                       ^ this number is just zero based index of column,,,

Теперь первый бит находится на правильном месте — просто установите следующие 7 бит:

 col0 |= (col0 & (1 << 55)) << 7; // second bit...
// ....

Или просто использовать std::bitset<64>, Я бы сделал….

1

Источник

Accepted Answer

Отличный вопрос Я действительно наслаждался взломом. Вот мое решение:

uint64_t map(uint64_t x, int column)
{
x = (x >> (7 - column)) & 0x0101010101010101uLL;
x = (x | (x >> 7)) & 0x00FF00FF00FF00FFuLL;
x = (x | (x >> 14))& 0x000000FF000000FFuLL;
x = (x | (x >> 28))& 0x00000000000000FFuLL;
return x << 56;
}

Рабочий пример можно найти по адресу ideone, где звонок действительно map(matrice, ColumnEnum::Column2),

3