如何在Common Lisp中创建位数组？

Question

经过大约一个小时的谷歌搜索，我不得不承认，虽然我找到了很多关于对位数组操作的文档，但我找不到任何关于如何创建位数组的参考资料。

现在，对我来说似乎要么是一些其他元素类型的数组可以作为位数组处理，要么是可以使用 (make-array :element-type (???))，但我找不到任何关于在括号中填写"???"的解释。

因此，虽然对其他人来说这可能很明显，但我不知道如何创建位数组。我知道如何编写文字位数组 - 但如果我需要一个有2^16个位的位数组，我该怎么做？

- BitTickler

Answer 1

你在使用make-array上是正确的，只需要将元素类型使用'bit即可。尝试使用(make-array initial-size :element-type 'bit)。

符号BIT指定了位类型，并且可以替换为任何其他类型说明符来创建一个数组，以容纳该类型的对象。在这个示例中，initial-size只是保存了一个整数的变量。

- RowPJ

Answer 2

另一种创建位向量的方法：

> (make-sequence '(vector bit) 10)
#*0000000000

- Rainer Joswig

Answer 3

还有一种使用#*阅读器宏的文字语法，请注意，使用make-array和make-sequence可能会导致具体类型不同，但我不确定性能是否会因此而异...

使用SBCL进行测试：

CL-USER> (defvar arr (make-array 10 :element-type 'bit :fill-pointer 0))
ARR

CL-USER> (type-of arr)
(VECTOR T 10)

CL-USER> (defvar arr3 (make-sequence '(vector bit) 10))
ARR3

CL-USER> (type-of arr3)
(SIMPLE-BIT-VECTOR 10)

CL-USER> (type-of #*0101010100)
(SIMPLE-BIT-VECTOR 10)

- Renato

---

有趣的发现！然而，在我的sbcl中：CL-USER> (array-element-type #*11110001010111) BIT CL-USER> (array-element-type (make-array 10 :element-type 'bit)) BIT - BitTickler

这里的关键区别在于使用:fill-pointer，它要求实现使用实际的向量对象，而不是simple-array或其子类型之一。我记得:adjustable也存在类似的问题，这意味着基于替换的数组插入/追加可能比副作用方法更快，因为simple-array优化（还有另一个CL SO问题展示了这一点）。 - swapneils

Answer 4

这样怎么样：

• (setq x 10)
• 10
• (setq y (read-from-string (format nil "#*~7,'0b" x)))
• #*0001010
• 7是任意长度，可以通过以下方式设置
• (setq z 8)
• 8
• (setq y (read-from-string (format nil (concatenate 'string "#*~" (write-to-string z) ",'0b") x)))
• #*00001010
• 一个大的位数组可能更好地处理为无符号整数。

- bitflogger

---

由于指针标记的存在，most-positive-fixnum 的值为 CL-USER> (format nil "~B" most-positive-fixnum) "11111111111111111111111111111111111111111111111111111111111111"，同时它的长度为 62 位。在这个长度内，你的答案是正确的。 - BitTickler

如果象棋游戏的发明者了解指针标记，他们本可以创建一个只有62个方格的棋盘，这样就可以在Common Lisp中高效地实现魔术位板了 ;) 但是由于他们不知道这一点，我们仍然需要向INTEL发送请求信，请他们终于创建一个66位架构... - BitTickler

我认为我的LISP，gcl，自动转换为“bignum”，因此我的代码可以轻松处理200位。但是我想以十六进制打印大量位数，这是由于数字格式支持，但似乎对于位向量不起作用。 - bitflogger

所有这些中间函数调用（read-from-string，concatenate，write-to-string，但尤其是format）使得创建位向量的成本相当高。但是对于位向量来说，它似乎并不会这样做。这并不奇怪，因为bit-vector不是一个数字。 - ad absurdum