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

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

  • \$\begingroup\$ note that TRUNCATE can take two arguments and that it will return two values: quotient and remainder \$\endgroup\$ Jan 10, 2017 at 14:01

3 Answers 3


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)

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)))
  • \$\begingroup\$ that's a nice answer \$\endgroup\$ Jan 10, 2017 at 14:00
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jan 10, 2017 at 14:11
  • \$\begingroup\$ @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. \$\endgroup\$
    – Vatine
    Jan 11, 2017 at 14:53
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Vatine
    Jan 11, 2017 at 14:54
  • \$\begingroup\$ (ash 1 (integer-length n)) is the same as (expt 2 (integer-length n)), though SBCL will probably figure this out on its own. \$\endgroup\$
    – wvxvw
    Oct 15, 2017 at 14:01

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.


CL-USER 75 > (write (invert-bits #b1001001010010110100) :base 2)
  • \$\begingroup\$ Good point about blowing the stack. I had assumed it would be tail-recursive, but that may indeed not be the case. \$\endgroup\$ Jan 10, 2017 at 14:23
  • 1
    \$\begingroup\$ @GustavBertram: TCO depends on the implementation. But your code is not tail-recursive anyway, since the self recursive call is not in tail position. \$\endgroup\$ Jan 10, 2017 at 14:25
  • 1
    \$\begingroup\$ Doh! Well, this certainly has been very educational. Thank you. \$\endgroup\$ Jan 10, 2017 at 14:30

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
              (integer-length n))))
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 4, 2017 at 22:38
  • \$\begingroup\$ @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. \$\endgroup\$ Feb 5, 2017 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.