好的,让我们考虑一个 64 位的数字,它的位组成一个 8x8 的表。
例如
0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0
写成
a b c d e f g h
----------------
0 1 1 0 1 0 1 0
0 1 1 0 1 0 1 1
0 1 1 1 1 0 1 0
0 1 1 0 1 0 1 0
1 1 1 0 1 0 1 0
0 1 1 0 1 0 1 0
0 1 1 0 1 1 1 0
0 1 1 0 1 0 1 0
现在,如果我们只想隔离例如d 列(00100000
)(或任何行/对角线)?
这可以做到吗?如果可以,怎么做?
提示:
(a) 我在这里的主要目标——虽然最初没有提到——是原始速度。我正在寻找最快的算法,因为“检索”功能正在执行数百万次每秒。
(b) 这更接近我的意思:https://www.chessprogramming.org/Kindergarten_Bitboards
最佳答案
这是一个只有 4 个主要步骤的解决方案:
const uint64_t column_mask = 0x8080808080808080ull;
const uint64_t magic = 0x2040810204081ull;
int get_col(uint64_t board, int col) {
uint64_t column = (board << col) & column_mask;
column *= magic;
return (column >> 56) & 0xff;
}
它是这样工作的:
- 板被移动以使列与左侧对齐
- 它被屏蔽为仅包含所需的列 (0..8)
- 乘以一个魔数(Magic Number),将所有原始位推到左侧
- 最左边的字节向右移动
选择魔数(Magic Number)以仅复制所需的位,并让其余的位落入未使用的位置/溢出该数字。这个过程看起来像这样(数字是位“ID”,而不是数字本身):
original column: ...1.......2.......3.......4.......5.......6.......7.......8....
aligned column: 1.......2.......3.......4.......5.......6.......7.......8.......
multiplied: 123456782345678.345678..45678...5678....678.....78......8.......
shifted to right:........................................................12345678
如果你添加 const
关键字,汇编实际上变得非常好:
get_col:
.LFB7:
.cfi_startproc
movl %esi, %ecx
movabsq $-9187201950435737472, %rax
salq %cl, %rdi
andq %rax, %rdi
movabsq $567382630219905, %rax
imulq %rax, %rdi
shrq $56, %rdi
movl %edi, %eax
ret
无分支,无外部数据,每次计算大约 0.4ns。
编辑:使用 NPE 的解决方案作为基线大约需要 6 分之一的时间(下一个最快的)
关于c++ - "Isolate"来自 64 位数字的特定行/列/对角线,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14537831/