Invert the bits of a non-negative integer in Common Lisp (SBCL)

Question

I'm doing code challenges to learn Common Lisp. I'm trying to invert all the bits in any given positive integer.

My current solution does it the math way, by recursing on a number, dividing it by two, and inverting the remainder before multiplying and adding back up:

(defun invert-bits (n)
    (if (> n 0)
        (+ (* (invert-bits (truncate (/ n 2))) 2)
           (if (= (rem n 2) 1) 0 1))
        0))

Is there a simpler way to do this using built-in functions?

Answer 1

A possible way is to use one of the bitwise logical operators on integers, that treat integers as binary numbers. For instance, by using the logxor operator, we could write:

(defun invert-bits2 (n)
  (if (> n 0)
      (logxor (1- (expt 2 (integer-length n))) n)
      0))

The function integer-length returns the number of bits of the binary representation of an integer, so that (1- (expt 2 (integer-length n))) is a binary number with all ones and the same length as n.

CL-USER> (loop for f in '(identity invert-bits invert-bits2)
            do (format t "~20b~%" (funcall f 300212)))
 1001001010010110100
  110110101101001011
  110110101101001011
NIL

Answer 2

See Renzo's answer for a really good solution.

Remarks about your solution:

• truncate can take two arguments and returns two values
• your recursive function is limited by max stack depth

This would be a similar iterative version:

(defun invert-bits (n &aux r)
  (loop for i from 0
        while (plusp n)
        do (setf (values n r) (truncate n 2))
        sum (ash (logxor r 1) i)))

(truncate n 2) returns two values and (setf (values n r) ...) assigns them to n and r.

Example:

CL-USER 75 > (write (invert-bits #b1001001010010110100) :base 2)
110110101101001011
224075

Answer 3

Potentially Surprising Behavior

Without specifying the number of bits we are interested in the inversions don't necessarily behave the way a programmer might expect:

(invert-bits (invert-bits 8)) ; => 0
; because
(invert-bits 8) ; => 7
(invert-bits 7) ; => 0

In general two successive calls to invert-bits does not obey the principle of least surprise:

(invert-bits (invert-bits 54)) ; => 6
(invert-bits (invert-bits 1024)) ; => 0
(invert-bits (invert-bits 4000)) ; => 32

The issue, if it is actually an issue, arises from inverting bits in the abstract rather than in a particular context. In a practical application, there is probably a specific type that we are concerned with, for example a 16-bit integer.

Analysis of Issue

As written the function throws away information by treating a leading bit value of 0 as equivalent to the absence of information. From an information theory standpoint, a zero leading bit is information.

Sketch of information retaining function

Using Common Lisp's &Optional parameters is a mechanism for passing the number of interesting bits through the recursive calls to invert-bits. Using values at the bottom of the function passes the bit-depth across the recursive calls.

(defun invert-bits (n &Optional number-of-bits)
  ;; code which will:
  ;; turn n into some-number taking into account
  ;; the bits if provided
  (values some-number
          (if number-of-bits
              number-of-bits
              (integer-length n))))