Как я могу использовать 64-битные переменные без знака в битовых операциях в Clojure?

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

Использование Java BitSet как подсказывает @assylias, дает простое решение:

(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

** КОНЕЦ РЕДАКТИРОВАНИЯ **

Что касается производительности, я протестировал 3 версии, и это дает очень похожую синхронизацию (~10 нс) для этого быстрого стенда. 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)))

Answer 2

Вот быстрая и очень грязная реализация обратного сканирования с использованием бит-теста и без зацикливания, что может быть или не быть более эффективным.

(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)))

Важно отметить, что ^ Лонг в штучной упаковке, и я думаю, что ^ долго не может быть в штучной упаковке при правильных обстоятельствах. Числовые массивы примитивов - один из немногих случаев, когда я обнаружил, что примитивы, несомненно, являются тем, чем они должны быть в JVM (байтовый массив всегда будет байтовым массивом с непрерывными 8-битными частями памяти, но объявленным байтом сам по себе, даже в Java, может занимать более 8 бит памяти из-за оптимизации выравнивания). Я настоятельно рекомендую библиотеку примитивно-математических вычислений ztellman для нахождения случаев, когда требуется отражение для математики в Clojure, что на удивление часто и может быть очень важно для подобного кода.