C++映射矩阵列进行排序 - 位操作

我已经有（二进制）矩阵表示由uint64_t（从C++ 11）。我希望能够从任何专栏有效地映射到第一级。例如C++映射矩阵列进行排序 - 位操作

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包含0xED00000000000000LL;

来源

2012-11-16 Dejwi

为什么不只是...迭代并做到这一点？你有尝试过什么吗？ – Xymostech

最简单的解决方案将由uint8_t迭代uint8_t，并通过逻辑和适当的掩码检查第7位（本例中），并生成输出矩阵。但我怀疑这是否是最好的解决方案。 – Dejwi

伟大的问题。我真的很喜欢黑客。这里是我的解决方案：

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)被发现。

来源

2012-11-16 23:23:35 ipc

这看起来很棒！有类似的方式回去吗？某种地图从一级到前一列？ – Dejwi

首先定义位掩码中的每一列：通过移动，你只能得到第一列的情况下

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

：通过应用栏位掩码为您的“矩阵的计算方法”

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

你只有此列：

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>，我会做....

来源

2012-11-16 22:43:03 PiotrNycz

一个不错的小谜语。这是一个合理的可读版本：

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);

来源

2012-11-16 22:51:11

C++映射矩阵列进行排序 - 位操作

回答

相关问题