Conversion to base -2, in Emacs Lisp.

neg2.el

;;; Don't just eval-buffer this; it's got a mix of definitions and example evaluations.

(defun neg2-range (width)
  (if (zerop width) (cons 0 0)
    (let ((range (neg2-range (1- width)))
          (offset (expt -2 (1- width))))
      (if (< offset 0)
          (incf (car range) offset)
        (incf (cdr range) offset))
      range)))

(neg2-range 0) (0 . 0)
(neg2-range 1) (0 . 1)
(neg2-range 2) (-2 . 1)
(neg2-range 3) (-2 . 5)
(neg2-range 4) (-10 . 5)
(neg2-range 5) (-10 . 21)
(neg2-range 6) (-42 . 21)

(defun neg2-from-num (n)
  (let ((width 0)
        (start 0)
        (end 0))
    (while (or (< n start) (< end n))
      (let ((offset (expt -2 width)))
        (if (< offset 0)
            (incf start offset)
          (incf end offset))
        (incf width)))

    (let (result)
      (while (> width 0)
        (decf width)
        ;(setq result (lsh result 1))
        (let ((offset (expt -2 width))
              (midpt (+ start (/ (- end start) 2))))
          (when (eq (minusp offset) (<= n midpt))
            (push offset result)
            (decf n offset))
          (if (minusp offset)
              (decf start offset)
            (decf end offset))))

      result)))

(neg2-from-num 0) 0    nil
(neg2-from-num 1) 1    (1)
(neg2-from-num 2) 6    (  -2 4)
(neg2-from-num 3) 7    (1 -2 4)
(neg2-from-num 4) 4    (     4)
(neg2-from-num 5) 5    (1    4)
(neg2-from-num 6) 26   (  -2   -8 16)
(neg2-from-num 7) 27   (1 -2   -8 16)
(neg2-from-num 8) 24   (       -8 16)
(neg2-from-num 9) 25   (1      -8 16)
(neg2-from-num 10) 30  (  -2 4 -8 16)
(neg2-from-num 11) 31  (1 -2 4 -8 16)
(neg2-from-num 12) 28  (     4 -8 16)
(neg2-from-num 13) 29  (1    4 -8 16)
(neg2-from-num 14) 18  (  -2      16)
(neg2-from-num 15) 19  (1 -2      16)
(neg2-from-num 16) 16  (          16)
(neg2-from-num 17) 17  (1         16)
(neg2-from-num 18) 22  (  -2 4    16)
(neg2-from-num 19) 23  (1 -2 4    16)
(neg2-from-num 20) 20  (     4    16)
(neg2-from-num 21) 21  (1    4    16)
(neg2-from-num 22) 106 (  -2   -8    -32 64)
(neg2-from-num 23) 107 (1 -2   -8    -32 64)
(neg2-from-num 24) 104 (       -8    -32 64)
(neg2-from-num 25) 105 (1      -8    -32 64)
(neg2-from-num 26) 110 (  -2 4 -8    -32 64)
(neg2-from-num 27) 111 (1 -2 4 -8    -32 64)
(neg2-from-num 28) 108 (     4 -8    -32 64)
(neg2-from-num 29) 109 (1    4 -8    -32 64)
(neg2-from-num 30) 98  (  -2         -32 64)
(neg2-from-num 31) 99  (1 -2         -32 64)
(neg2-from-num 32) 96  (             -32 64)

(neg2-from-num -0)  0   nil
(neg2-from-num -1)  3   (1 -2)
(neg2-from-num -2)  2   (  -2)
(neg2-from-num -3)  13  (1    4 -8)
(neg2-from-num -4)  12  (     4 -8)
(neg2-from-num -5)  15  (1 -2 4 -8)
(neg2-from-num -6)  14  (  -2 4 -8)
(neg2-from-num -7)  9   (1      -8)
(neg2-from-num -8)  8   (       -8)
(neg2-from-num -9)  11  (1 -2   -8)
(neg2-from-num -10) 10  (  -2   -8)
(neg2-from-num -11) 53  (1    4    16 -32)
(neg2-from-num -12) 52  (     4    16 -32)
(neg2-from-num -13) 55  (1 -2 4    16 -32)
(neg2-from-num -14) 54  (  -2 4    16 -32)
(neg2-from-num -15) 49  (1         16 -32)

(defun neg2-simple-positive (n)
  (let ((negbit 2))
    (while (>= n negbit)
      ;; If the binary representation of n has a bit set that would be a
      ;; negative power of two in base -2, then we need to compensate for its
      ;; negation by adding in the next power of two higher.
      (if (logand negbit n)
          (incf n (* 2 negbit)))
      (setq negbit (lsh 2 negbit))))
  n)
(neg2-simple-positive 0) 0
(neg2-simple-positive 1) 1
(neg2-simple-positive 2) 6
(neg2-simple-positive 3) 7
(neg2-simple-positive 4) 24
(neg2-simple-positive 5) 25