3

After googling for about an hour, I have to confess, that while I find a lot of documentation about functions operating on bit arrays, I cannot find a single reference on how to actually create a bit array.

Right now, it seems to me that either, some arrays with other element types can be handled as bit arrays OR that one could use (make-array :element-type (???)) where I could not find any explanation as to what to put where I wrote the "???".

So, while it is probably obvious to anyone else, I have no idea how to create a bit array. I know about how to write a literal bit array - but if I need a bit array with, say 2^16 bits - how would I do it?

Improve this question

4 Answers 4

Reset to default
4

You are right about using make-array, just use 'bit as the element type. Try (make-array initial-size :element-type 'bit). The symbol BIT names the bit type and could be replaced with any other type specifier to make an array holding objects of that type. In this example initial-size is just a variable holding a whole number.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

4

Another way to create a bit vector:

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

Comments

1

There's also a literal syntax using the #* reader macro, and notice that the concrete type may differ between using make-array and make-sequence, though I am not sure if performance may be different depending on that...

Tested with 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)
Improve this answer

2 Comments

Interesting find! Yet, in my sbcl: CL-USER> (array-element-type #*11110001010111) BIT CL-USER> (array-element-type (make-array 10 :element-type 'bit)) BIT
The key difference here is the use of :fill-pointer, which requires the implementation to use an actual vector object instead of simple-array or any of its subtypes. :adjustable is similarly problematic, as I recall, which among other things means that replacement-based array insertion/appending can be faster than side-effecting approaches due to the simple-array optimizations (There's another CL SO question which shows this).
-1

How about this:

  • (setq x 10)
  • 10
  • (setq y (read-from-string (format nil "#*~7,'0b" x)))
  • #*0001010
  • The 7 is an arbitrary length, which could be set by
  • (setq z 8)
  • 8
  • (setq y (read-from-string (format nil (concatenate 'string "#*~" (write-to-string z) ",'0b") x)))
  • #*00001010
  • A large bit array may be better handled as an unsigned integer.
Improve this answer

4 Comments

Thanks to pointer tagging, the most-positive-fixnum is CL-USER> (format nil "~B" most-positive-fixnum) "11111111111111111111111111111111111111111111111111111111111111" CL-USER> (length *) 62 62 bits. Up to that length, your answer is valid.
Had the inventors of the chess game known about pointer tagging, they would have created a chess board with only 62 squares, so magic bitboards can be implemented efficiently in Common Lisp ;) As they did not, we still have to send our letters of plea to INTEL, so they finally create a 66 bit architecture...
I think my LISP, gcl, automatically goes to "bignum", so my code can easily do 200 bits. But I like to print a large number of bits in hexadecimal, which is supported by format for a number, but it does not seem to do that for a bit vector.
All of those intermediate function calls (read-from-string, concatenate, write-to-string, but especially format) make this a pretty expensive way to create a bit vector. -- "....but it does not seem to do that for a bit vector." This shouldn't come as a surprise since a bit-vector isn't a number.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.