【题解讨论】去日苦多，何不留下些什么？

[lzhlyle]

题解思路简要概括为：借位运算解构棋子移动，BFS求解最短路径问题。

详见 题解博客 与 题解源码 。有什么想说的？快来一起讨论吧！

• 在 题解博客 - 棋局压缩 一节的末尾，留下了几点思考

  • 找最低位 1 的位置，是试着逐个位右移后，每次都判断移后最低位是否为 1 ，更好的写法是？
  • 纵观全局，虽返回值为 long ，但判重的哈希集合 visited 类型为 Set<Long> ，意味着存在装箱、拆箱，可有更好方案？

• 在 题解博客 - 抽象优化 一节中，只是简要表达了可优化的方向。你有更好的优化切入点吗？

  • 由空位定移动 寻找可能的移动时，先确定空位，减少逐棋子逐方向尝试，可大量剪枝，加快速度。
  • 抽象形状判断 对于移动前的形状筛选，以及压缩前的同形排序，都可通过抽象形状判断，而非固定索引值的方式来硬执行，由此可适应更多开局。

[lzhlyle]

找最低位 1 的位置，是试着逐个位右移后，每次都判断移后最低位是否为 1 ，更好的写法是？

可通过 temp[i] & -temp[i] 取最低位 1 后，再对数所得

long lowest = log2(temp[i] & -temp[i]);

private static int log2(int n) {
    if (n <= 0) throw new IllegalArgumentException();
    return 31 - Integer.numberOfLeadingZeros(n);
}

补充知识： x & -x 指的是取最低位的 1 及后面的所有 0。

int x = 0b10010110101011000;
int lowest = x & -x; // 1000，最低位的1及后面的0