[racket-dev] Implementation of bit vectors

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Mon Nov 26 13:43:51 EST 2012

Hi All,

I have implemented an alternative version of bit-vectors using bignums
to represent the bits.

As is the bignum implementation is much slower, than the vector-of-fixnum one.

The main reason as far as I can tell is due to bit-vector-set! .
Since bignums aren't mutable I can not simply flip a bit and need to compute
a new bignum. Unless bignums are sharing limbs this will be slow for large

Another possibility is that I have missed something obvious.
The functions bit-vector-set! is here:

(define (bit-vector-set! bv n b)
  ; bv is a bit-vector
  ; n is the bit number
  ; b is #f or #t
  (define bits (bit-vector-bits bv))
  (define mask (arithmetic-shift 1 n))
     (set-bit-vector-bits! bv (bitwise-ior bits mask))]
    [(bitwise-bit-set? bits n)
     (set-bit-vector-bits! bv (bitwise-xor bits mask))]
    [else (void)]))

The entire implementation is here:


The benchmark is here:


Jens Axel Søgaard

Posted on the dev mailing list.