3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ note that TRUNCATE can take two arguments and that it will return two values: quotient and remainder \$\endgroup\$ – Rainer Joswig Jan 10 '17 at 14:01
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ that's a nice answer \$\endgroup\$ – Rainer Joswig Jan 10 '17 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\$ – Gustav Bertram Jan 10 '17 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 '17 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 '17 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 '17 at 14:01
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Good point about blowing the stack. I had assumed it would be tail-recursive, but that may indeed not be the case. \$\endgroup\$ – Gustav Bertram Jan 10 '17 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\$ – Rainer Joswig Jan 10 '17 at 14:25
  • 1
    \$\begingroup\$ Doh! Well, this certainly has been very educational. Thank you. \$\endgroup\$ – Gustav Bertram Jan 10 '17 at 14:30
0
\$\begingroup\$

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))))
\$\endgroup\$
  • \$\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\$ – Gustav Bertram Feb 4 '17 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\$ – ben rudgers Feb 5 '17 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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