c++ - "Isolate"来自 64 位数字的特定行/列/对角线

Question

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

Answer 1

这是一个只有 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 分之一的时间(下一个最快的)