<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<!-- -*- coding:utf-8 -*- -->

  <LINK REL="icon"          HREF="/favicon.ico" TYPE="image/x-icon">
  <LINK REL="shortcut icon" HREF="/favicon.ico" TYPE="image/x-icon">
  <LINK REL="stylesheet"    HREF="../../default.css"  TYPE="text/css">
  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8">
  <META NAME="author"             CONTENT="Pascal J. Bourguignon">

  <META HTTP-EQUIV="Description"
        CONTENT="Write a function f on 32-bit integers that, applied twice, it negates the integer.">
  <META NAME="keywords"
        CONTENT="32-bit,negation,integer,modulo,interview question, ">
  <TITLE>  f(f(n)) = -n  </TITLE>


<!-- This section is automatically generated by html-update, -->
<!-- from data in 'node.el'.    Please, do not edit it here. -->
<!-- This section is automatically generated by html-update, -->
<!-- from data in 'node.el'.    Please, do not edit it here. -->
 <A CLASS="button" HREF="../../toc.html">Contents</a> |
 <A CLASS="button" HREF="../../index.html">Home</a> |
 <A CLASS="button" HREF="../interleave/index.html">Previous</a> |
 <A CLASS="button" HREF="../usenet.html">Up</a> |
 <A CLASS="button" HREF="../cl-types/index.html">Next</a> |

<div class="document" id="ffn=-n">
<h1>f(f(n)) = -n</h1>

<p>In a comment to Steve Yegge's blog <a


    <p><b><a href="http://www.blogger.com/profile/13466586996802181998">Vlad Patryshev</a> said...</b></p>

    <p>Tactically, you are very right. Strategically... I don't know. You
       mix two things together, strict typing in general, abuse of UML and
       class hierarchy, and overuse of strict typing where it is not
       necessary (I mean JavaScript).</p>

    <p>Regarding class structures - it's probably hard to force people
       that love bureaucracy not to fill their code with Managers,
       Handlers, Helpers, and the like (none of these does any work, but
       they pass it around, like in real life). But I'm afraid this
       anti-bureaucratic rant has nothing to do with the issue of modeling
       in general.</p>

    <p>I'll give you one example, an interview problem. Write a function f
       on 32-bit integers that, applied twice, it negates the
       integer. f(f(n)) = -n.</P>

    <p>Try to solve it without any kind of model, by just applying
       randomly ad-hoc xors and shifts.</p>

    <p></i>9:00 PM, February 11, 2008</i></p>


<p>Assuming Vlad means integers represented in two-complement, which
   is the case with 99% of the processors nowadays, such a function
   just doesn't exist. Here's the mathematical proof.</p>

<p>First, in ℤ, such functions indeed exist. For example:</p>

    (defun integer/f (n)
    Assuming n is an INTEGER, (= (- n) (f (f n)))
         0 -->  0
        +1 --> -2 --> -1 --> +2 --> +1
        +3 --> -4 --> -3 --> +4 --> +3
        +(2k+1) --> -(2k+2) --> -(2k+1) --> +(2k+2) --> +(2k+1)
      (declare (type integer n))
      (if (zerop n)
          (if (plusp n)
              (if (oddp n)
                  (1- (- n))
                  (1- n))
              (if(oddp n)
                  (1+ (- n))
                  (1+ n)))))

<p>The same function works in one-complement representation, too
   (assuming <code>zerop</code> indicates both +0 and -0).</p>

<p>But things are different in ℤ/<sub>m</sub>, because of the special
   properties of the negation in these sets.</p>

<p>When m=2<sup>p</sup> with p>2:</p>
<p>Let i be the identity function:  ∀ a ∈ ℤ/<sub>m</sub>, i(a)=a
<p>Let n be the negation function in two-complement on
   ℤ/<sub>2<sup>p</sup></sub>. n is defined as: n(x) = 1+(¬x), with ¬x
   being the bitwise not operation.</p>
<p>Here are some properties of n:
<li>let M = -2<sup>p-1</sup>.  In two-complement arithmetic, n(M)=M.
<li>∀ a ∈ ℤ/<sub>2<sup>p</sup></sub>∖{0, M}, n(a)≠a
<li>∀ a ∈ ℤ/<sub>2<sup>p</sup></sub>, n(n(a))=a ; n<sup>2</sup> = i
<li>∀ (a,b) ∈ ℤ/<sub>2<sup>p</sup></sub><sup>2</sup>,
    n(a)=n(b) ⇒ a=b (trivially deduced from 4.)

<p>Properties 3 and 4 allow partitionning
ℤ/<sub>2<sup>p</sup></sub>∖{0, M} in two symetrical subsets, one
representing the positive integers, and the other their opposite
negative integers.</p>

<p>Now, assume there is a function f such as ∃ x ∈ ℤ/<sub>2<sup>p</sup></sub>,  f(f(x))=n(x).</p>
<p>Let's denote the composition of functions by mere juxtaposition: fg = f○g.</p>
<li>f<sup>0</sup> = i
<li>f<sup>2</sup> = n
<li>f<sup>3</sup> = nf<sup>1</sup> = f<sup>1</sup>n
<li>f<sup>1</sup> = nf<sup>3</sup> = f<sup>3</sup>n = f
<li>f<sup>4</sup> = n<sup>2</sup> = i
and so on, ∀ k ∈ ℕ, f<sup>4k</sup>=i, f<sup>4k+1</sup>=f, f<sup>4k+2</sup>=n, f<sup>4k+3</sup>=nf.

<p>Let C be the function from ℤ/<sub>2<sup>p</sup></sub> to
2<sup>ℤ/<sub>2<sup>p</sup></sub></sup> such as:
C(x) = { f<sup>0</sup>(x), f<sup>1</sup>(x),
         f<sup>2</sup>(x), f<sup>3</sup>(x) }</p>

<p>Now, let (a,b) ∈ ℤ/<sub>2<sup>p</sup></sub><sup>2</sup>, such as
   a ∉ {0, M}, f<sup>2</sup>(a)=n(a) and b ∉ C(a) [H]</p>

<p>Since a ∉ {0, M} and f<sup>2</sup>(a)=n(a), | C(a) | = 4.</p>
<li>b = f<sup>0</sup>(b) ≠ a, by hypothesis [H].
<li>f<sup>1</sup>(b) ≠ a, since by hypothesis [H], b ≠ f<sup>3</sup>(a).
<li>f<sup>2</sup>(b) ≠ a, since by hypothesis [H], b ≠ f<sup>2</sup>(a).
<li>f<sup>3</sup>(b) ≠ a, since by hypothesis [H], b ≠ f<sup>1</sup>(a).
<br>in consequence, all the subsets C(x) are disjoint and form a partition of ℤ/<sub>2<sup>p</sup></sub>.

<p>However, since C(0) = { 0, f<sup>1</sup>(0) }, and C(M) = { M,
f<sup>1</sup>(M) }, and ℤ/<sub>2<sup>p</sup></sub> is divisible by 4
when p>2, there is at least two other elements of
ℤ/<sub>2<sup>p</sup></sub>, let's call them N and O, such as C(O) = {
O, f<sup>1</sup>(O) } and C(N) = { N, f<sup>1</sup>(N) }. </p>

<p>We have f<sup>2</sup>(O) = O and f<sup>2</sup>(N) = N, which shows
that ∃ x ∈ ℤ/<sub>2<sup>p</sup></sub>, f(f(x)) ≠ -x.

<p><em>Conclusion</em>: When p>2, there is no function on
ℤ/<sub>2<sup>p</sup></sub> such as f<sup>2</sup> = n.</p>  At most, we
can find functions such as f(f(x)) = -x for all elements x of
ℤ/<sub>2<sup>p</sup></sub> but for two of our choosing.  Note that we
can choose to break the formula for 0 and M, since -0 is not very
interesting and -M in two-complement is pathologic anyways.</p>

<p>(For other sets, ℤ/<sub>q</sub> if q ≡ 1 [4] or  q ≡ 2 [4],
then there are functions such as f<sup>2</sup>=n).</p>

<p>Finally, we can implement a function that does almost what was
asked, only with a bug: we get to choose which two values for which
f(f(x)) ≠ -x.

<p>But of course, not using only XOR and SHIFT operations!  Using only
NAND and SHIFT, it would be possible (since NAND is all is needed to
build all the boolean operators, but XOR is not powerful enough to do
so, see Wikipedia articles on
<a href="http://en.wikipedia.org/wiki/Logical_connective">Logical connective</a>
or on <a href="http://en.wikipedia.org/wiki/Functional_completeness">Functional completeness</a>).

<p>Technically, we don't need full functional completeness for XOR
   (⊻), we'd only need to be able to implement logical not and
   increment.  For logical not, there's no problem, a ⊻ 1 = ¬a, but
   for increment, we need to implement a semi-adder, where s = a ⊻ b
   and c = a ∧ b.  But there is no way to get AND from XOR, because
   XOR is closed over {0, 1, a, b, ¬a, ¬b, a⊻b, ¬(a⊻b)} (any
   application of XOR on two elements of this set gives an element of
   this set).</p>


<p>Since two-complement negation on binary words of length w is
defined as <code>(mod (1+ (lognot n)) (expt 2 w))</code>, we need more
than just XOR and SHIFT...  Two impossibilities for one <em>interview
question</em>.  Vicious!  And asking to do that "without any kind of
model", tskss, tskss, I wouldn't like to work at such a company,
unless the question was designed exactly for that, to weed out people
doing what they're told without thinking...</p>

(declaim (ftype (function (integer) (unsigned-byte 32))

(defun 32-bit (x)
  "Mask off 32-bits of X"
  (logand #xffffffff x))

(defun 32-bit/plusp (n)
  "Whether N represents a positive integer."
  (declare (type (unsigned-byte 32) n))
  (zerop (ldb (byte 1 31) n)))

(defun 32-bit/2-complement-neg (n)
  "Return the negation of N in 2-complement."
  (declare (type (unsigned-byte 32) n))
  (32-bit (1+ (lognot n))))

(defun 32-bit/f (n)
Assuming n is a 32-bit 2-complement signed integer different
from 0 and -2³¹,  (= (- n) (f (f n)))
  (declare (type (unsigned-byte 32) n))
   (case n                              ; (f (f n))
     ((#x00000000) #x80000001)          ; --> 0x80000000
     ((#x80000000) #x7FFFFFFF)          ; --> 0x00000000
     ((#x7FFFFFFF) #x00000000)          ; --> 0x80000001
     ((#x80000001) #x80000000)          ; --> 0x7fffffff
     ;;  For the above exceptions, any permutation is valid;
     ;;  we choose here to break it for 0 and M, with
     ;;  f(f(0))=M and f(f(M))=0,
     ;;  to keep f(f(2³¹-1))= -(2³¹-1) and f(f(-(2³¹-1)))= 2³¹-1
      (if (32-bit/plusp n)
          (if (oddp n)
              (lognot n)
              (1- n))
          (if (oddp n)
              (+ (lognot n) 2)
              (1+ n)))))))




C/USER[83]> (load"<a href="ffn=-n.lisp">ffn=-n.lisp</a>")
;; Loading file ffn=-n.lisp ...
;; Loaded file ffn=-n.lisp
C/USER[84]> (test-f)

           i           -i    (f (f i))        (f i) (- (f (f i)))
    00000000     00000000 /=  80000000    80000001     80000000
    00000001     FFFFFFFF     FFFFFFFF    FFFFFFFE     00000001
    00000002     FFFFFFFE     FFFFFFFE    00000001     00000002
    00000003     FFFFFFFD     FFFFFFFD    FFFFFFFC     00000003
    00000004     FFFFFFFC     FFFFFFFC    00000003     00000004
    00000005     FFFFFFFB     FFFFFFFB    FFFFFFFA     00000005
    00000006     FFFFFFFA     FFFFFFFA    00000005     00000006
    00000007     FFFFFFF9     FFFFFFF9    FFFFFFF8     00000007
    00000008     FFFFFFF8     FFFFFFF8    00000007     00000008
    00000009     FFFFFFF7     FFFFFFF7    FFFFFFF6     00000009
    0000000A     FFFFFFF6     FFFFFFF6    00000009     0000000A
    0000000B     FFFFFFF5     FFFFFFF5    FFFFFFF4     0000000B
    0000000C     FFFFFFF4     FFFFFFF4    0000000B     0000000C
    0000000D     FFFFFFF3     FFFFFFF3    FFFFFFF2     0000000D
    0000000E     FFFFFFF2     FFFFFFF2    0000000D     0000000E
    0000000F     FFFFFFF1     FFFFFFF1    FFFFFFF0     0000000F
    00000010     FFFFFFF0     FFFFFFF0    0000000F     00000010
    00000011     FFFFFFEF     FFFFFFEF    FFFFFFEE     00000011
    00000012     FFFFFFEE     FFFFFFEE    00000011     00000012
    00000013     FFFFFFED     FFFFFFED    FFFFFFEC     00000013
    FFFFFFFF     00000001     00000001    00000002     FFFFFFFF
    FFFFFFFE     00000002     00000002    FFFFFFFF     FFFFFFFE
    FFFFFFFD     00000003     00000003    00000004     FFFFFFFD
    FFFFFFFC     00000004     00000004    FFFFFFFD     FFFFFFFC
    FFFFFFFB     00000005     00000005    00000006     FFFFFFFB
    FFFFFFFA     00000006     00000006    FFFFFFFB     FFFFFFFA
    FFFFFFF9     00000007     00000007    00000008     FFFFFFF9
    FFFFFFF8     00000008     00000008    FFFFFFF9     FFFFFFF8
    FFFFFFF7     00000009     00000009    0000000A     FFFFFFF7
    FFFFFFF6     0000000A     0000000A    FFFFFFF7     FFFFFFF6
    FFFFFFF5     0000000B     0000000B    0000000C     FFFFFFF5
    FFFFFFF4     0000000C     0000000C    FFFFFFF5     FFFFFFF4
    FFFFFFF3     0000000D     0000000D    0000000E     FFFFFFF3
    FFFFFFF2     0000000E     0000000E    FFFFFFF3     FFFFFFF2
    FFFFFFF1     0000000F     0000000F    00000010     FFFFFFF1
    FFFFFFF0     00000010     00000010    FFFFFFF1     FFFFFFF0
    FFFFFFEF     00000011     00000011    00000012     FFFFFFEF
    FFFFFFEE     00000012     00000012    FFFFFFEF     FFFFFFEE
    FFFFFFED     00000013     00000013    00000014     FFFFFFED
    FFFFFFEC     00000014     00000014    FFFFFFED     FFFFFFEC
    7FFFFFEC     80000014     80000014    7FFFFFEB     7FFFFFEC
    7FFFFFED     80000013     80000013    80000012     7FFFFFED
    7FFFFFEE     80000012     80000012    7FFFFFED     7FFFFFEE
    7FFFFFEF     80000011     80000011    80000010     7FFFFFEF
    7FFFFFF0     80000010     80000010    7FFFFFEF     7FFFFFF0
    7FFFFFF1     8000000F     8000000F    8000000E     7FFFFFF1
    7FFFFFF2     8000000E     8000000E    7FFFFFF1     7FFFFFF2
    7FFFFFF3     8000000D     8000000D    8000000C     7FFFFFF3
    7FFFFFF4     8000000C     8000000C    7FFFFFF3     7FFFFFF4
    7FFFFFF5     8000000B     8000000B    8000000A     7FFFFFF5
    7FFFFFF6     8000000A     8000000A    7FFFFFF5     7FFFFFF6
    7FFFFFF7     80000009     80000009    80000008     7FFFFFF7
    7FFFFFF8     80000008     80000008    7FFFFFF7     7FFFFFF8
    7FFFFFF9     80000007     80000007    80000006     7FFFFFF9
    7FFFFFFA     80000006     80000006    7FFFFFF9     7FFFFFFA
    7FFFFFFB     80000005     80000005    80000004     7FFFFFFB
    7FFFFFFC     80000004     80000004    7FFFFFFB     7FFFFFFC
    7FFFFFFD     80000003     80000003    80000002     7FFFFFFD
    7FFFFFFE     80000002     80000002    7FFFFFFD     7FFFFFFE
    7FFFFFFF     80000001     80000001    00000000     7FFFFFFF
    80000013     7FFFFFED     7FFFFFED    7FFFFFEE     80000013
    80000012     7FFFFFEE     7FFFFFEE    80000013     80000012
    80000011     7FFFFFEF     7FFFFFEF    7FFFFFF0     80000011
    80000010     7FFFFFF0     7FFFFFF0    80000011     80000010
    8000000F     7FFFFFF1     7FFFFFF1    7FFFFFF2     8000000F
    8000000E     7FFFFFF2     7FFFFFF2    8000000F     8000000E
    8000000D     7FFFFFF3     7FFFFFF3    7FFFFFF4     8000000D
    8000000C     7FFFFFF4     7FFFFFF4    8000000D     8000000C
    8000000B     7FFFFFF5     7FFFFFF5    7FFFFFF6     8000000B
    8000000A     7FFFFFF6     7FFFFFF6    8000000B     8000000A
    80000009     7FFFFFF7     7FFFFFF7    7FFFFFF8     80000009
    80000008     7FFFFFF8     7FFFFFF8    80000009     80000008
    80000007     7FFFFFF9     7FFFFFF9    7FFFFFFA     80000007
    80000006     7FFFFFFA     7FFFFFFA    80000007     80000006
    80000005     7FFFFFFB     7FFFFFFB    7FFFFFFC     80000005
    80000004     7FFFFFFC     7FFFFFFC    80000005     80000004
    80000003     7FFFFFFD     7FFFFFFD    7FFFFFFE     80000003
    80000002     7FFFFFFE     7FFFFFFE    80000003     80000002
    80000001     7FFFFFFF     7FFFFFFF    80000000     80000001
    80000000     80000000 /=  00000000    7FFFFFFF     00000000


<!-- This section is automatically generated by html-update, -->
<!-- from data in 'node.el'.    Please, do not edit it here. -->
 | <a href="http://www.informatimago.com//articles/ffn=-n/index.html">Mirror on informatimago.com</a>
 | <a href="http://informatimago.free.fr/i//articles/ffn=-n/index.html">Mirror on free.fr</a>
 | </small></code>

      <a href="http://validator.w3.org/check?uri=referer"><img
          alt="Valid HTML 4.01!" height="31" width="88"></a>