java - 如何在 Clojure 的位运算中使用无符号 64 位变量？

Question

我有以下代码:

(defn BitScanReverse [^Long bit-board]
  (loop [value bit-board r 0]
    (cond
      (> value 0x00000000FFFFFFFF) (recur (unsigned-bit-shift-right value 32) (+ r 32))
      (> value 0x000000000000FFFF) (recur (unsigned-bit-shift-right value 16) (+ r 16))
      (> value 0x00000000000000FF) (recur (unsigned-bit-shift-right value 8) (+ r 8))
      (> value 0x000000000000000F) (recur (unsigned-bit-shift-right value 4) (+ r 4))
      (> value 0x0000000000000003) (recur (unsigned-bit-shift-right value 2) (+ r 2))
      (> value 0x0000000000000001) (recur (unsigned-bit-shift-right value 1) (+ r 1))
      :else r)))

它返回位板中找到的最后一位的索引。问题是当我尝试运行时:(BitScanReverse 18446462598732840960) ;;预计 63。它给了我:IllegalArgumentException 长值超出范围:18446462598732840960 clojure.lang.RT.longCast (RT.java:1134)

这个位板是黑子的初始位置。问题是 long 在 clojure 中是有符号的(在 java 中也是如此)。我尝试过使用 BigInt，但它不允许位操作。

有什么建议吗？

Answer 1

这是一个使用位测试且无循环的反向扫描的快速且非常肮脏的实现，这可能会或可能不会更有效。

(defn rev-test [^long n ^long x] (bit-test x n))
(defn BitScanReverse [^long bit-board](condp rev-test bit-board
0 0,1 1,2 2,3 3,4 4,5 5,6 6,7 7,8 8,9 9,10 10,11 11,12 12,13 13,14 14,15 15,16 16,17 17,18 18,19 19,20 20,21 21,22 22,23 23,24 24,25 25,26 26,27 27,28 28,29 29,30 30,31 31,32 32,33 33,34 34,35 35,36 36,37 37,38 38,39 39,40 40,41 41,42 42,43 43,44 44,45 45,46 46,47 47,48 48,49 49,50 50,51 51,52 52,53 53,54 54,55 55,56 56,57 57,58 58,59 59,60 60,61 61,62 62,63 63))

这将最低有效位视为 0，就像位测试和 0 索引数组一样，所以我认为它与您的实现不同。在生成输入时，带正号文字的长度将被限制为 63 位，但您仍然可以使用符号位作为第 64 位。尝试创建一个辅助方法来构造您需要的具有稍高抽象级别的数字，例如这个 fn ，它将最高有效的 32 位和最低有效的 32 位作为两个参数。这可能可以写成一个宏，但我没有足够的经验来编写一个宏并确保它能够工作。

(defn bitboard [^long upper ^long lower]
    (bit-or (bit-shift-left upper 32)
            (bit-and lower 0xffffffff)))

对于性能来说，重要的是，^Long 被装箱，并且我认为 ^long 在正确的情况下可能不会被装箱。数字基元数组是我发现的少数情况之一，其中基元确实是 JVM 上应有的样子(字节数组始终是字节数组，具有连续的 8 位内存块，但由于对齐优化，单独声明的字节即使在 Java 中也可能占用超过 8 位的内存)。我强烈推荐 ztellman 的 primitive-math用于查找 Clojure 中的数学需要反射的情况的库，这种情况出现的频率令人惊讶，并且对于像这样的位操作代码非常重要。