＆QUOT;隔离＆QUOT;特定行/列/从一个64位数字对角线 [英] "Isolate" specific Row/Column/Diagonal from a 64-bit number

问题描述

好，让我们考虑一个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

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

可以这样做？如果是这样，如何​​？

Can this be done? And if so, how?

提示：

• （一）我的主要目标，在这里 - 虽然不是一开始提到的 - 是原始速度。我在寻找最快的算法各地，因为检索功能时每执行了一些数百万次的第二的。

（二）这是更接近我的意思：<一href="http://chessprogramming.wikispaces.com/Kindergarten+Bitboards">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位数字对角线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！