我有以下代码:
(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值超出long:18446462598732840960 clojure.lang.RT.longCast(RT.java:1134)的范围
这个位板是黑色碎片的初始位置。问题是long是用clojure(也用java)签名的。我尝试过使用BigInt,但它不允许位操作。
有什么建议吗?
这里有一个使用位测试和无循环的反向扫描的快速且非常脏的实现,这可能更有效,也可能不更有效。
(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比特作为两个arg。这可能是作为一个宏来写的,但我没有足够的经验来写一个并确定它会起作用。
(defn bitboard [^long upper ^long lower]
(bit-or (bit-shift-left upper 32)
(bit-and lower 0xffffffff)))
对于性能来说,重要的是,^Long被装箱了,我认为在正确的情况下^Long可能不会被装箱。数字基元数组是我发现的少数几种基元确实是JVM上应该有的情况之一(字节数组将始终是一个字节数组,具有连续的8位内存,但由于对齐优化,一个单独声明的字节,即使在Java中,也可能占用8位以上的内存)。我强烈推荐ztellman的原始数学库来查找Clojure中数学需要反射的情况,这种情况非常常见,对于像这样的代码来说非常重要。
按照@assilias的建议使用Java BitSet
,可以提供一个简单的解决方案:
(import 'java.util.BitSet)
(defn bit-scan-reverse [^long bit-board]
(let [board (BitSet/valueOf (long-array [bit-board]))]
(.previousSetBit board 63)))
编辑由于签署了long
,上述解决方案不起作用。用BitSet
继续搜索,我找到了:
(defn bit-scan-reverse2 [bit-board]
(let [board (-> (biginteger bit-board) ; coerce to BigInteger
.toByteArray ; as byte[] big-endian
reverse ; to little-endian
byte-array
BitSet/valueOf)
max-index (.size board)]
(.previousSetBit board max-index)))
这很好用,但似乎很复杂。然后查看BigInteger
文档,我发现了bitLength()
方法,它实际上回答了这个问题:
bitLength():返回此BigInteger的最小二进制补码表示中的位数,不包括符号位。
由于我们只关心板表示的正数,因此可以使用此bitLength()
方法来查找64位板中最左边的位集:
(defn bit-scan-reverse3 [bit-board]
(-> bit-board
biginteger
.bitLength
dec))
(map bit-scan-reverse3 '(0xFFFF000000000000 0x0 0x1 0xF 0xFFF))
user> 63 -1 0 3 11
**结束编辑**
就性能而言,我测试了这三个版本,它为这个快速板凳提供了非常相似的时间(~10ns)。BitScanReverse2
是@notostraca:提供的解决方案
(require '[clojure.data.generators :as gen])
(require '[criterium.core :as c])
(let [bunch-of-longs (doall (take 10000 (filter (partial < 0)
(repeatedly gen/long))))]
(c/quick-bench (map BitScanReverse bunch-of-longs))
(c/quick-bench (map BitScanReverse2 bunch-of-longs))
(c/quick-bench (map bit-scan-reverse bunch-of-longs))
(c/quick-bench (map bit-scan-reverse2 bunch-of-longs))
(c/quick-bench (map bit-scan-reverse3 bunch-of-longs)))