问题描述
好，让我们考虑一个64位的数字，其位形成一个8x8的表格。
OK, let's consider a 64-bit number, with its bits forming a 8x8 table.
例如。
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
现在，如果我们想要隔离JUST例如什么 D列（ 00100000 ）（或者行/对角线为此事）？
Now, what if we want to isolate JUST e.g. column d (00100000) (or any row/diagonal for that matter) ?
如果是这样，如何？
And if so, how?
提示：
-
（一）我的主要目标，在这里 - 虽然不是一开始提到的 - 是原始速度。我在寻找最快的算法各地，因为检索功能时每执行了一些数百万次的第二的。
（二）这是更接近我的意思：http://chessprogramming.wikispaces.com/Kindergarten+Bitboards
(b) This is what comes closer to what I mean : http://chessprogramming.wikispaces.com/Kindergarten+Bitboards
推荐答案
下面是只有4个主要步骤的解决方案：
Here's a solution with only 4 main steps:
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;
}
它的工作原理是这样的：
It works like this:
- 板被移动，以配合在左侧列
- 在它的屏蔽只包含所需的列（0..8）
- 它乘以一个幻数这导致所有的原始位推到左侧
- 最左字节右移
神奇的号码选择了在数只复制所需要的位，并让其余落入未使用的地方/溢出。这个过程看起来像这样（数字是位标识，而不是数字本身）：
The magic number is chosen to copy only the needed bits and let the rest fall into unused places / overflow over the number. The process looks like this (digits are bit "IDs", rather than the number itself):
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
如果您添加常量关键字，组装变得相当不错的实际：
If you add the const keywords, assembly becomes quite nice actually:
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。
No branching, no external data, around 0.4ns per calculation.
编辑：使用NPE的解决方案为基础约需时6号（下一个最快的国家之一）
takes around 6th of the time using NPE's solution as baseline (next fastest one)
这篇关于＆QUOT;隔离＆QUOT;特定行/列/从一个64位数字对角线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！