基于16位无符号整数Bitboard的邻接棋子计数技术问询

嘿，这个问题我熟！咱们先把思路理清楚，再一步步补全细节～

先明确核心问题 #

你用16位无符号整数实现4x4棋盘的Bitboard（1表示有棋子，0表示无），要统计至少有一个水平、垂直或对角相邻棋子的棋子总数——也就是找出所有“身边至少有一个同伴”的棋子，对吧？

你找到的算法拆解 #

先看看你给出的算法：

total = 0;
for each bitIndex in bitscanForward(bitboard) {
    total += bitPopCount(bitboard & (ADJACENT_MASK << bitIndex));
}
return total;

这里先澄清一个点：这个算法其实计算的是所有相邻棋子对的总次数（每对相邻棋子会被统计两次，比如棋子A和B相邻，遍历A时会算B，遍历B时会算A）。如果你的目标是统计“有至少一个相邻的棋子数量”，我们后面会调整，但先把这个算法的细节补全。

1. 定义ADJACENT_MASK #

首先要确定ADJACENT_MASK的值——它是棋盘上某个基准位置（比如bitIndex=0，对应棋盘右下角）的所有相邻位的掩码。假设我们的16位Bitboard对应4x4棋盘，位的排布是从下到上、从右到左（也可以是行优先，只要统一即可）：

15 14 13 12 （第0行，最上方）
11 10 9  8   （第1行）
7  6  5  4   （第2行）
3  2  1  0   （第3行，最下方）

那么bitIndex=0的相邻位是：右方（1）、上方（4）、右上方（5），所以ADJACENT_MASK就是0b1101（即十进制的13）。这个掩码左移不同的bitIndex，就能得到对应位置的所有相邻位掩码。

2. 实现bitscanForward函数 #

bitscanForward的作用是遍历Bitboard中所有置1的位，返回每个位的索引（也就是找出所有有棋子的位置）。对于16位无符号整数，我们可以用两种方式实现：

方式一：用语言内置函数（推荐）

比如在C/C++中，__builtin_ctz(u)可以返回无符号整数u中末尾0的个数，也就是最低位1的索引。结合循环清零最低位1，就能遍历所有置1的位：

void bitscanForward(uint16_t bitboard, void (*callback)(int)) {
    while (bitboard != 0) {
        // 找到最低位1的索引
        int bitIndex = __builtin_ctz(bitboard);
        // 回调处理这个索引
        callback(bitIndex);
        // 清零最低位1，继续下一个
        bitboard &= bitboard - 1;
    }
}

方式二：手动实现（兼容无内置函数的环境）

如果不能用内置函数，我们可以手动遍历每一位：

void bitscanForward(uint16_t bitboard, void (*callback)(int)) {
    for (int i = 0; i < 16; i++) {
        if (bitboard & (1 << i)) {
            callback(i);
        }
    }
}

3. bitPopCount的实现 #

bitPopCount是统计整数中置1的位数，同样可以用内置函数或手动实现：

• 内置函数：C/C++的__builtin_popcount(bitboard)（注意如果是16位，要转成unsigned int）
• 手动实现：

int bitPopCount(uint16_t bitboard) {
    int count = 0;
    while (bitboard) {
        count++;
        bitboard &= bitboard - 1;
    }
    return count;
}

调整算法：统计“至少有一个相邻的棋子数量” #

如果你要的是有至少一个相邻棋子的棋子总数（而不是相邻对的次数），只需要把算法改成判断每个棋子是否有相邻，有就计数1：

int countAdjacentPieces(uint16_t bitboard) {
    int total = 0;
    uint16_t adjacentMask = 0b1101; // 对应4x4棋盘的基准相邻掩码
    uint16_t temp = bitboard;
    while (temp != 0) {
        int bitIndex = __builtin_ctz(temp);
        // 计算当前位置的相邻位掩码
        uint16_t currentAdjacent = adjacentMask << bitIndex;
        // 检查是否有相邻棋子
        if (bitboard & currentAdjacent) {
            total++;
        }
        // 清零当前位
        temp &= temp - 1;
    }
    return total;
}

额外优化：更高效的Bitboard技巧 #

其实还有更高效的方法，不需要遍历每个棋子——直接用Bitboard运算生成“有相邻棋子的位置掩码”，再统计置位数：

int countAdjacentPieces(uint16_t bitboard) {
    // 生成所有有相邻棋子的位置掩码
    uint16_t mask = 0;
    // 右相邻
    mask |= bitboard << 1;
    // 左相邻
    mask |= bitboard >> 1;
    // 上相邻（假设每行4位，上移4位）
    mask |= bitboard << 4;
    // 下相邻
    mask |= bitboard >> 4;
    // 右上相邻
    mask |= bitboard << 5;
    // 左上相邻
    mask |= bitboard << 3;
    // 右下相邻
    mask |= bitboard >> 5;
    // 左下相邻
    mask |= bitboard >> 3;
    // 过滤掉棋盘外的位（比如最左边的棋子左移会溢出到其他行，需要掩码清除）
    uint16_t rowMask = 0b1111; // 每行的掩码
    mask &= (rowMask << 12) | (rowMask << 8) | (rowMask << 4) | rowMask;
    // 现在mask是所有有相邻棋子的位置，和原bitboard取交集就是有相邻的棋子
    uint16_t adjacentPieces = bitboard & mask;
    // 统计数量
    return __builtin_popcount(adjacentPieces);
}

这个方法不需要遍历每个棋子，直接用位运算一步到位，效率更高～

内容的提问来源于stack exchange，提问作者Loheek