如何在常见的lisp中获得64位整数？

Question

我想在常见的lisp中写一个位板,所以我需要一个64位整数.如何在常见的lisp中获得64位整数？此外,是否有任何库可以帮助我实现这一目标而无需从头开始编写所有内容？

Answer 1

您可以将变量声明为类型(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声明可能会有所帮助.

这是一个(非常简单的)这种类型声明的例子,并处理二进制中的整数:

(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定义,用于获取整数位的简单setter,以及相应的getter:

(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

Answer 2

在便携式Common Lisp中,"Integers"和你一样大.有一个更高效的整数子集称为"fixnums".fixnums的确切范围是实现依赖的.但它通常不是可以使用的完整64位(在64位架构上),因为大多数Common Lisp实现都需要类型标记位.对于用户而言,没有太大区别.Fixnums是整数的子集,可以添加两个fixnums并获得not-fixnum整数结果.可观察到的唯一差异是使用非fixnum整数的计算速度较慢,需要更多存储空间,...通常,如果要使用整数进行计算,则不需要声明要使用64位进行计算.您只需使用Integers和常用操作即可.

如果你想要真正的64位大整数(仅用64位表示,没有标签等)并使用它们进行计算,你将保留可移植的ANSI CL功能.CLISP是否以及如何支持,最好在CLISP邮件列表中询问.

文档

• 键入FIXNUM
• 输入INTEGER

Answer 3

使用位向量/数组实现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

不知道为什么编译器会放入所有这些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视为脚本/原型语言,然后从分析器建议的代码中挤出更多性能.

汇编代码显然不如在一个64位寄存器中加载整个电路板然后访问各个位一样紧凑.但是,如果你突然决定要每平方米超过1位,它更容易改变CL码比改变汇编代码(只是改变数组从类型到处'(mod 2)到'(mod 16),例如).

Answer 4

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