6

我想用普通的 lisp 写一个位板，所以我需要一个 64 位整数。如何在 common lisp 中获得 64 位整数？此外，是否有任何库可以帮助我完成此任务，而无需从头开始编写所有内容？

4

4 回答 4

7

您可以将变量声明为类型(signed-byte 64)或(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的 -declarations 可能会有所帮助。

这是此类类型声明的（非常简单的）示例，并以二进制形式处理整数：

(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

在可移植的 Common Lisp 中，“整数”可以随心所欲。有一个更有效的整数子集称为“fixnums”。fixnums 的确切范围取决于实现。但通常不能使用完整的 64 位（在 64 位架构上），因为大多数 Common Lisp 实现都需要类型标记位。对于用户来说，差别不大。Fixnums 是整数的子集，可以将两个 fixnums 相加并得到一个非fixnum 整数结果。唯一可以观察到的区别是使用非固定整数的计算速度较慢，需要更多的存储空间，...一般来说，如果你想用整数进行计算，你不需要声明你想用 64 位计算. 您只需使用整数和通常的操作。

如果您想要真正的 64 位大整数（仅以 64 位表示，没有标签等）并使用它们进行计算，您将放弃可移植的 ANSI CL 功能。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))

DECLAIMs 允许本地 内联请求. 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

不知道为什么编译器会放入所有这些NOPs （为以后的检测留出空间？对齐？）但是如果你看一下最后的代码，它非常紧凑（当然不像手工汇编器那么紧凑）。

现在这是一个明显的过早优化案例。从这里开始的正确方法是简单地编写：

(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 视为脚本/原型设计语言，然后从分析器建议的代码中挤出更多性能。

汇编代码显然不如将整个电路板加载到一个 64 位寄存器中然后访问各个位那么紧凑。但是，如果您突然决定每平方需要超过 1 位，则更改 CL 代码比更改汇编代码容易得多（例如，只需将数组类型从 更改'(mod 2)为'(mod 16)）。

于 2012-01-02T11:06:04.633 回答
2

您想使用位向量，它是任意大小的位数组，而不是 64 位整数之类的东西。实现将为您处理内部表示。

于 2011-12-30T06:14:56.310 回答