How do you increment a bit of a bit-array from a position in array?

Question

I would like to (modulo) increment a particular bit of a bit-array. How do you do that in Common Lisp ?

For example, I want to increment the value of bit 3 in bit-array #*0001 (The bit 3 has the value 1). I want to modulo-increment it by 1, so that it would turn to 0.

CL-USER> (setf x #*0001)
#*0001

CL-USER> (bit x 3)
1 (1 bit, #x1, #o1, #b1)

CL-USER> (setf (bit x 3) (+ (bit x 3) 1))
TYPE-ERROR :
The value
  2
is not of type
  BIT
when setting an element of (ARRAY BIT)
   [Condition of type TYPE-ERROR]

Of course, I have the same error when using INCF instead of SETF. I want a modulo-increment, that is I don't want #*0001 to turn to #*0010 but to be #*0000.

I have an error when using NOT in :

CL-USER> (setf (bit x 3) (not (bit x 3)))

Value of #:NEW1 in ((SETF AREF) #:NEW1 #:G0 3) is NIL, not a BIT.
   [Condition of type SIMPLE-TYPE-ERROR]

All the same, when using LOGNOT:

CL-USER> (setf (bit x 3) (lognot (bit x 3)))

Value of (LOGNOT (BIT X 3)) in
((SETF AREF) #:NEW1 #:G0 3)
is
  -2,
not a
  BIT.
   [Condition of type SIMPLE-TYPE-ERROR]

I don't see how I could use BIT-NOT as it wants 2 bit-arrays as input. I just want to invert (modulo-increment) a bit in a bit-array from its position in the bit array.

Answer 1

The "literal" way to do this would be something like

(defvar *array* (make-array 4 :element-type 'bit :initial-element 0))
(setf (bit *array* 2) (mod (1+ (bit *array* 2)) 2))
(print *array*) ;; ==> #*0010
(setf (bit *array* 2) (mod (1+ (bit *array* 2)) 2))
(print *array*) ;; ==> #*0000

or as self-contained function:

(defun nbit-flip (bitset index)
  (setf (bit bitset index) (mod (1+ (bit bitset index)) 2))
  bitset)

You could use (logxor 1 ...) to do the flipping like

(defun nbit-flip (bitset index)
  (setf (bit bitset index) (logxor 1 (bit bitset index)))
  bitset)

Just stick to that which signals your intention most clearly.

Answer 2

You need the result to be a bit and since CL tries to do correct arithmetic this means you need to actually make it be a bit as bits aren't closed under addition. An obvious approach is

(setf (bit a ...) (mod (+ (bit a ...) increment) 2))

Answer 3

• not is only for logical values and returns either T or NIL (boolean type).

• (lognot 1) is -2 (two's complement) the negative sign is there because integers have no fixed width (they can be arbitrary long), and you need to mask the result to a particular width to obtain a positive value. Since you are using bit values, you can simply combine it with logand as follows:

  (logand (lognot 0) 1) => 1
  (logand (lognot 1) 1) => 0
  

• logxor as explained in another answer is fine too

• you could also compute (- 1 b):

   (defun bit1+ (b)
    (declare (type bit b))
    (the bit (- 1 b)))
  

In any case, you can also define a bit-increment macro:

(defmacro bitincf (place)
  `(setf ,place (bit1+ ,place)))