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.

Dirk · Accepted Answer · 2023-06-30 13:14:29Z

3

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.

edited Jun 30, 2023 at 13:14

answered Jun 30, 2023 at 13:00

Dirk

31.1k8 gold badges86 silver badges103 bronze badges

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

Comments

ignis volens · Accepted Answer · 2023-06-30 13:41:24Z

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))

answered Jun 30, 2023 at 13:41

ignis volens

9,5956 silver badges14 bronze badges

Comments

coredump · Accepted Answer · 2023-06-30 16:34:46Z

1

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)))

answered Jun 30, 2023 at 16:34

coredump

39.4k7 gold badges47 silver badges85 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related