Common Lisp でビットボードを書きたいので、64 ビット整数が必要です。Common Lispで64ビット整数を取得するにはどうすればよいですか? また、すべてをゼロから作成せずにこれを達成するのに役立つライブラリはありますか?
4222 次
4 に答える
7
(signed-byte 64)変数をor型として宣言できます(unsigned-byte 64)。
CL-USER> (typexpand '(unsigned-byte 64))
(INTEGER 0 18446744073709551615)
T
CL-USER> (typexpand '(signed-byte 64))
(INTEGER -9223372036854775808 9223372036854775807)
T
実際にこれを 8 連続バイトに詰め込むのに十分賢いかどうか、またはこれに bignum を使用するかどうかは、実装に依存します。適切なoptimize宣言が役立つ場合があります。
これは、そのような型宣言の (非常に単純な) 例であり、整数をバイナリで処理します。
(let* ((x #b01)
(y #b10)
(z (logior x y)))
(declare ((signed-byte 64) x y z))
(format t "~a~%" (logbitp 1 x))
(format t "~a~%" (logbitp 1 (logior x (ash 1 1))))
(format t "~b~%" z))
Output:
NIL
T
11
以下は、整数のビットに対する単純なセッターと、対応するゲッターを取得するための setf-expander の定義です。
(define-setf-expander logbit (index place &environment env)
(multiple-value-bind (temps vals stores store-form access-form)
(get-setf-expansion place env)
(let ((i (gensym))
(store (gensym))
(stemp (first stores)))
(values `(,i ,@temps)
`(,index ,@vals)
`(,store)
`(let ((,stemp (dpb ,store (byte 1 ,i) ,access-form))
,@(cdr stores))
,store-form
,store)
`(logbit ,i ,access-form)))))
(defun logbit (index integer)
(ldb (byte 1 index) integer))
これらは次のように使用できます。
(let ((x 1))
(setf (logbit 3 x) 1)
x)
==> 9
(let ((x 9))
(setf (logbit 3 x) 0)
x)
==> 1
(logbit 3 1)
==> 0
(logbit 3 9)
==> 1
于 2011-12-30T08:54:58.497 に答える
6
ポータブルCommonLispでは、「整数」は好きなだけ大きくなります。'fixnums'と呼ばれる整数のより効率的なサブセットがあります。fixnumの正確な範囲は、実装によって異なります。しかし、ほとんどのCommon Lisp実装は型タグビットを必要とするため、通常、使用できるのは完全な64ビット（64ビットアーキテクチャ上）ではありません。ユーザーにとっては、大きな違いはありません。Fixnumは整数のサブセットであり、2つのfixnumを追加して、非fixnum整数の結果を得ることができます。観察できる唯一の違いは、非fixnum整数を使用した計算は遅く、より多くのストレージが必要なことです...一般に、整数を使用して計算を行う場合は、64ビットで計算することを宣言する必要はありません。 。整数とそれらの通常の演算を使用するだけです。
実際の64ビットの大きな整数（64ビットのみで表され、タグなどは含まれない）とそれらを使用した計算が必要な場合は、ポータブルANSICL機能をそのままにしておきます。CLISPがそれをサポートするかどうか、またどのようにサポートするかは、CLISPメーリングリストで尋ねるのが最適です。
ドキュメンテーション
于 2011-12-31T15:29:13.950 に答える
6
8x8ビットボードを実装するためのビットベクトル/配列の使用例（厳密なアセンブラーコードを取得する方法を示すために、残酷かつ時期尚早に最適化されたコードから開始）：
(defun make-bitboard ()
(make-array '(8 8) :element-type '(mod 2) :initial-element 0))
MAKE-BITBOARDビットの配列として8x8ビットボードを作成します。SBCLを使用する場合、これは内部的に要素ごとに1ビットとして表されます（したがって、64ビット+配列インスタンスのオーバーヘッドがあります）。ボードにアクセスするときに最適化を要求すると、高速なコードが得られます。
(declaim (inline get-bitboard))
(defun get-bitboard (bit-board x y)
(declare (optimize speed (safety 0) (debug 0))
(type (simple-array (mod 2) (8 8)) bit-board)
(type fixnum x y))
(aref bit-board x y))
(declaim (notinline get-bitboard))
は、DECLAIMのローカル
インライン化要求を
許可するためにありGET-BITBOARDます。
使用例GET-BITBOARD：
(defun use-bitboard (bit-board)
(declare (optimize speed (safety 0) (debug 0))
(type (simple-array (mod 2) (8 8)) bit-board)
(inline get-bitboard))
(let ((sum 0))
(declare (type fixnum sum))
(dotimes (i 8)
(declare (type fixnum i))
(dotimes (j 8)
(declare (type fixnum j))
(incf sum (the (mod 2) (get-bitboard bit-board i j)))))
sum))
SET-BITBOARDまだないので、使用例USE-BITBOARDは次のとおりです。
(use-bitboard (make-bitboard))
逆アセンブルUSE-BITBOARD（SBCL、Linux x64）は、コンパイラーがインライン化されていることを示していますGET-BITBOARD。
; disassembly for USE-BITBOARD
; 030F96A2: 31F6 XOR ESI, ESI ; no-arg-parsing entry point
; 6A4: 31D2 XOR EDX, EDX
; 6A6: EB54 JMP L3
; 6A8: 90 NOP
; 6A9: 90 NOP
; 6AA: 90 NOP
; 6AB: 90 NOP
; 6AC: 90 NOP
; 6AD: 90 NOP
; 6AE: 90 NOP
; 6AF: 90 NOP
; 6B0: L0: 31DB XOR EBX, EBX
; 6B2: EB3E JMP L2
; 6B4: 90 NOP
; 6B5: 90 NOP
; 6B6: 90 NOP
; 6B7: 90 NOP
; 6B8: 90 NOP
; 6B9: 90 NOP
; 6BA: 90 NOP
; 6BB: 90 NOP
; 6BC: 90 NOP
; 6BD: 90 NOP
; 6BE: 90 NOP
; 6BF: 90 NOP
; 6C0: L1: 488D04D500000000 LEA RAX, [RDX*8]
; 6C8: 4801D8 ADD RAX, RBX
; 6CB: 4C8B4711 MOV R8, [RDI+17]
; 6CF: 48D1F8 SAR RAX, 1
; 6D2: 488BC8 MOV RCX, RAX
; 6D5: 48C1E906 SHR RCX, 6
; 6D9: 4D8B44C801 MOV R8, [R8+RCX*8+1]
; 6DE: 488BC8 MOV RCX, RAX
; 6E1: 49D3E8 SHR R8, CL
; 6E4: 4983E001 AND R8, 1
; 6E8: 49D1E0 SHL R8, 1
; 6EB: 4C01C6 ADD RSI, R8
; 6EE: 4883C302 ADD RBX, 2
; 6F2: L2: 4883FB10 CMP RBX, 16
; 6F6: 7CC8 JL L1
; 6F8: 4883C202 ADD RDX, 2
; 6FC: L3: 4883FA10 CMP RDX, 16
; 700: 7CAE JL L0
; 702: 488BD6 MOV RDX, RSI
; 705: 488BE5 MOV RSP, RBP
; 708: F8 CLC
; 709: 5D POP RBP
; 70A: C3 RET
コンパイラがこれらすべてを配置した理由はわかりませんがNOP（後でインストルメンテーション用のスペースを残しますか？アライメントですか？）、最後のコードを見ると、かなりコンパクトです（もちろん、手作りのアセンブラほどコンパクトではありません）。
これは、時期尚早の最適化の明らかなケースです。ここから始める正しい方法は、単に次のように書くことです。
(defun get-bitboard (bit-board x y)
(aref bit-board x y))
(defun use-bitboard (bit-board)
(let ((sum 0))
(dotimes (i 8)
(dotimes (j 8)
(incf sum (get-bitboard bit-board i j))))
sum))
...次に、ビットボードを使用するゲームコードを実行するときにプロファイラーを使用して、CPUのボトルネックがどこにあるかを確認します。SBCLには、優れた 統計プロファイラーが含まれています。
速度を宣言せずに、より単純で低速なコードから始めるのが最善です。コードのサイズを比較するだけです-私はたくさんの宣言を含むコードから始めて、最後の単純なコードを比較してさらに単純に見えるようにしました:-)。ここでの利点は、アイデアを試すときにCommon Lispをスクリプト/プロトタイピング言語として扱い、プロファイラーが提案するコードからより多くのパフォーマンスを引き出すことができることです。
アセンブリコードは、ボード全体を1つの64ビットレジスタにロードしてから個々のビットにアクセスするほど厳密ではないことは明らかです。ただし、1平方あたり1ビット以上が必要であると突然判断した場合は、アセンブラコードを変更するよりも、CLコードを変更する方がはるかに簡単です（たとえば、配列タイプをから'(mod 2)に変更するだけです）。'(mod 16)
于 2012-01-02T11:06:04.633 に答える
2
64ビット整数のようなものではなく、任意のサイズのビット配列であるビットベクトルを使用したい。実装は、内部表現を処理します。
于 2011-12-30T06:14:56.310 に答える