“隔离"来自 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 10 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

现在，如果我们想隔离只是例如列 d (00100000)(或任何行/对角线)?

Now, what if we want to isolate JUST e.g. column d (00100000) (or any row/diagonal for that matter) ?

这能做到吗? 如果能，怎么做?

提示:

• (a) 我在这里的主要目标——虽然最初没有提到——是原始速度.我正在寻找最快的算法，因为检索"功能正在执行数百万次每秒.

(b) 这更接近我的意思:https://www.chessprogramming.org/Kindergarten_Bitboards

(b) This is what comes closer to what I mean : https://www.chessprogramming.org/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;
}

它是这样工作的:

• 将板移动以将列与左侧对齐
• 它被屏蔽为仅包含所需的列 (0..8)
• 它乘以一个幻数，导致所有原始位被推到左侧
• 最左边的字节向右移动

选择幻数来仅复制所需的位，而让其余的位落入未使用的位置/溢出数字.这个过程看起来像这样(数字是位ID"，而不是数字本身):

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

如果添加const关键字，汇编实际上变得相当不错:

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)

这篇关于“隔离"来自 64 位数字的特定行/列/对角线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！