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?

• Rainer Joswig: note that TRUNCATE can take two arguments and that it will return two values: quotient and remainder

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

• Rainer Joswig: that's a nice answer
• Gustav Bertram: Oh man, I had gotten so close to this. I was stuck on (ceiling (log n 2)) instead of integer-length, which obviously fails on some edge cases.
• Vatine: @GustavBertram For "number of digits of non-negative number", you could use (1+ (floor (log n <base>))) or (ceiling (log (1+ n) <base)), with a slight preference for the latter, as it sanely handles n == 0.
• Vatine: @Renzo In this specific case, you could actually use - instead of logxor, but I'd probably do it with logxor, as it's more clearly bit manipulation.
• wvxvw: (ash 1 (integer-length n)) is the same as (expt 2 (integer-length n)), though SBCL will probably figure this out on its own.

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

• Gustav Bertram: Good point about blowing the stack. I had assumed it would be tail-recursive, but that may indeed not be the case.
• Rainer Joswig: @GustavBertram: TCO depends on the implementation. But your code is not tail-recursive anyway, since the self recursive call is not in tail position.
• Gustav Bertram: Doh! Well, this certainly has been very educational. Thank you.

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

• Gustav Bertram: Ah, in this case reversibility is not one of the requirements. I'll be sure to link a bit more context next time to make that clear.
• ben rudgers: @GustavBertram I started to play around with a lexicographic implementation using (format nil "~b" n) etc. My answer is more about what I found interesting: the friction between the idea of flipping bits and the concepts that make Common Lisp unique. In C n might be a UBYTE. Flipping 0 produces 255 and flipping 255 produces 0. Java handles numbers in a similar vein. In Common Lisp, numbers don't seem to explicitly map into bit fields like those languages. And I found the implications in terms of information theory more interesting than my code and so I wrote that up instead.