Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question from somebody's job interview made me puzzled:

Design a function f, such that:

$f(f(n)) = -n$ ,

where n is a 32 bit signed integer; you can't use complex numbers arithmetic. If you can't design such a function for the whole range of numbers, design it for the largest range possible.

Do you have any idea how to tackle it?

EDIT: I removed "Real number" from the title, since it just confused readers, but it was meant just to stress that complex numbers are not allowed.

share|improve this question
5  
Isn't this more of a programming question than a math question? –  Seth Apr 28 at 12:31
2  
Aren't the domain and codomain integers in the interval [$-2^{16}, 2^{16}$] ? –  Tom Collinge Apr 28 at 12:49
2  
Because they are interviewers and they are allowed to ask all sorts of dumb questions. –  Tom Collinge Apr 28 at 13:01
1  
I don't know exactly how 32 bit signed integers are stored, presumably 32 bits give the binary expansion and one extra bit gives the sign. Use the last of the 32 bits to be a special indicator 0 if "$f$ hasn't been applied" and $1$ if "f has been applied". So if $n$ has special bit $0$ then $f$ changes the bit to $1$. If $n$ has special bit $1$ then $f$ changes the special bit to $0$ and changes the sign. The disadvantage is that obviously this halves the range on which the function gives the correct answer, and it's also in some sense "the same" as using complex number multiplication. –  Seth Apr 28 at 13:12
3  
@TomCollinge: I think you mean $[-2^{31}, 2^{31})$. The lowest representable number in 32-bit twos complement is -$2^{31}$ and the highest is $2^{31}-1$. –  Jack Aidley Apr 28 at 15:30

12 Answers 12

up vote 19 down vote accepted

I'd try to exploit even and odd numbers. You somehow need a two-stage mapping and thus two subsets of integers. For instance, $f$ could map odd numbers to even numbers, and even numbers to odd numbers with opposite sign. Like this:

$$\color{gray}{f(n)=\begin{cases}0 & n= 0\\ 2n & n\in\text{odd}\\ -n/2 & n\in\text{even} \end{cases}}$$

EDIT: A major brain leak from my part, $n/2$ can stay even, so this doesn't work. However, the idea is sound, and the next one is actually valid.

You can construct a function that doesn't have this problem. Instead of messing up the entire range, you can select the smallest possible subset that has the property $f^2(n)=-n$. The smallest subset is $4$ numbers, because $f^4(n)=n$. You can for instance do something like this

$$f: n_{odd}\mapsto (n+1)_{even} \mapsto (-n)_{odd} \mapsto {-(n+1)}_{even}\mapsto n_{odd}$$

So if you start with even, start at the second stage. Test:

0 -> 0
1 -> 2 -> -1 -> -2
2 -> -1 -> -2 -> 1
3 -> 4 -> -3 -> -4
4 -> -3 -> -4 -> 3

and so on.

Or as a function $$f(n)=\begin{cases}0 & n= 0\\ n+1 & n\in\text{odd}^+\\ -n+1 & n\in\text{even}^+\\ n-1 & n\in\text{odd}^-\\ -n-1 & n\in\text{even}^- \end{cases}$$

This procedure does overflow, but only for the very last number in the range. However, at the end of the range you have bigger problem ($-2^{31}$ exists but $2^{31}-1$ is the top of the range so there's a number without its negative). There are $3$ problematic numbers: $-2^{31}$ without its negative, and $\pm(2^{31}-1)$ that can't be a part of a cycle of $4$ numbers, because $0$ is already taken.

There's actually no way of fixing this last issue, because the problem comes from the size of the set not being a multiple of $4$ after you exclude the zero for its special property $0=-0$. The solution I give is therefore optimal.

share|improve this answer
2  
Does this work ? $f(4) = -2; f(-2) = 1$ –  Tom Collinge Apr 28 at 12:57
    
Oops. The second one seems to be better. –  orion Apr 28 at 12:58
    
@TomCollinge Fixed. –  orion Apr 28 at 13:15
2  
@orion, I like your approach - stressing/outlining ideas, not particular solutions. –  VividD Apr 28 at 13:56
2  
This is THE correct answer, with the key being the last paragraph. It is not possible because the set size is not a multiple of 4 (ignoring 0 and actually -2^31 as well, which has no positive counterpart). At least two numbers have to fail the f(f(n))==-n test. –  Dan Bliss Apr 28 at 20:14

I'm reminded of a math puzzle that goes thusly:

Two mathematicians find themselves in that terrible kingdom where the king kills them unless they perform some mundane logical task. Don't move there, it's awful.

Our heroes must flip a coin each day, and at least one of them must guess correctly the other guy's coin or they both die. Naturally, they are able to live forever using one little trick (executioners hate them!)

What do they do? Well, they have one guy always guess whatever he flips, and the other guy always guess what he didn't flip. So if they end up flipping the same thing, the guy who guesses same will be correct. If they end up flipping different, the other guy will be correct.

I'm going to employ the logic used to solve this puzzle to solve our puzzle here.

Basically, we're going to use the most significant bit in the integer to store whether or not we need to flip signs. It's possible that any bit would do, but the MSB is the least damaging to the number of we end up having to sacrifice it. I'm pretty sure we don't, but I can't rule it out.

Let us say that A is our most significant bit, and S is our sign bit. The remaining bits determine the magnitude of N (As I said, I have not yet concluded if the A bit can be included in the magnitude, or if we have to sacrifice that bit's "usefulness" towards the magnitude in order to serve as data storage about the stage of the operation).

This gives 4 kinds of numbers:

S A
0 0 : N is a "small" positive number, perhaps 0.
0 1 : N is a "large" positive number
1 1 : N is a "small" negative number, perhaps -1
1 0 : N is a "large" negative number

For any number x (positive or negative), negating that number generally flips both the S bit and the A bit -- except for the special values 0 and "the weird number".

We can do this with any number of bits, so for this example we'll use 8 bit numbers.

Our 8 bit number will be 53, or 0b 0011 0101. Our mission will be to turn this into -53, or 1100 1011

Now since we're using 1 bit for sign, and 1 bit for our own purposes, the range this function holds for is only 6 bits (unless it actually DOES hold for all 7 bits, I just haven't tested that condition).

The function operates thusly:

if A == S, flip A.

else flip A and then multiply by the value negative 1.

So F(0b 0011 0101) = 0b 0111 0101. When we pass this through the function again, A will no longer equal S. So it hits the else clause, flipping the A bit (back to 53) and multiplying by negative 1.

Another example, starting with -53 == 0b 1100 1011:

F(0b 1100 1011) == 0b 1000 1011

Then F(0b 1000 1011) hits the else clause, flipping the A bit to get 0b 1100 1011 == -53, and then negating the number to get +53 == 0b 0011 0101.

So the idea is that we're sacrificing the A bit for the purposes of F(x) because it should get reversed when we run the result through F again. Note that F(x) by itself is not a particularly useful function. Also that this may not work for edge cases (I haven't tested much. 0, MAX_VALUE, MIN_VALUE, and -1 all come to mind as cases to test.)

share|improve this answer
    
Let's just look at the S and A bits and assume that the sign bit is on the left. For 53 they are 00 and the transformation is 00 -> 01 -> 10: works fine. For -53, we have 10 -> 01 -> 10. You work for Microsoft ? –  Tom Collinge Apr 28 at 14:35
1  
Signed integers are not actually stored with a sign bit on any modern computer. Instead the MSB is treated as a negative value (a method called Two's complement). This gives much easier implementation of basic arithmetic and has only one representation of zero. –  Jack Aidley Apr 28 at 16:11
    
@JackAidley: You are technically correct, but many people (apparently including corsiKa) still call the leftmost bit in signed 32-bit integers in practically all modern computers "the sign bit", even though it acts differently than the "real" sign bit in early Cray mainframes. –  David Cary Apr 28 at 16:33
    
@TomCollinge No, it works for negative numbers as well. It looks like David took the time to clean up my terribly formatted answer, and included -53 as an additional example while doing so. –  corsiKa Apr 28 at 17:05
    
OK. Looks like things have changed a bit since our computers had valves ! –  Tom Collinge Apr 28 at 18:29

First off, from a programming perspective, you need to clarify what function means. A pure function (which is also the mathemtical sense) has no side effects; non-functional languages can have functions with side effects, and for those languages, something like:

state = -1
def f(n):
   global state
   state = state * -1
   return n * state

will meet the requirement. Otherwise, you need a way to encode state in the intermediate return. Given a 32 bit input (and assuming range is -2^31 to 2^31-1), you need to actually support 33 bits for the intermediate (i.e. first call to f). This is for two reasons... one is to store the state (whether this is the first or 2nd call to f), and the second is to handle n=-2^31 (which can't be expressed in 32 bits using the standard 2's complement signed coding). Rather than confusing things by treating the MSB or another bit as the state flag, I find it easier to use a struct (if I was coding in C and really concerned about space, I could try using bitfields but this would be overkill and probably not useful because of padding). Anyways: struct mystruct { unsigned int state:1; signed int value; } For f, if the state is 1, this indicates this is the second time this has been called, so return -value; if state state is 0, this is the first time, so return state=1, value

(Question I realized I should have asked... does f(f(f(f(n)))) need to return n?

share|improve this answer
    
You can just use the state as a toggle and then f(f(f(f(n)))) will return n. –  Tom Collinge Apr 28 at 17:00

This answer to a related question supplies the relevant analysis.

Assuming that a "signed 32-bit integer" means that you are considering the domain and range of $f$ to be the integers in the interval $[-2^{31}, 2^{31})$, a simple counting argument shows that the largest domain on which the identity $f(f(x))=-x$ can hold must be missing at least three points.

(aside: $-2^{31}$ must be excluded, because it is outside of the domain of unary negation. The interesting part is that we must exclude two other points too)

The sample function from that answer can be used:

$$ f(x) = \begin{cases} 0 & x == 0 \\ x+1 & x>0 \wedge \text{$x$ is odd} \\ 1-x & x>0 \wedge \text{$x$ is even} \\ x-1 & x<0 \wedge \text{$x$ is odd} \\ -1-x & x<0 \wedge \text{$x$ is even} \end{cases} $$

which has the desired property on $[-2^{31} + 2, 2^{31} - 2]$.

I won't discuss implementing a solution with bit twiddling: such a topic is beyond the scope of this forum.


EDIT: if we instead want the domain of $f$ to be the entire interval, we can make the identity hold for one more point. If we take a function $f$ given as above, and let the three points that are excluded be $a$, $-a$, and $2^{-31}$, then we can extend $f$ by setting

  • $f(a) = 2^{-31}$
  • $f(2^{-31}) = -a$
  • $f(-a) = $ anything

and thus with this extension, $f(f(a)) = -a$ as well.

share|improve this answer

If $n$ can admit any real number, then we could define $f(n)$ as:

$$f(n)=\begin{cases} \sqrt2n & n\in\mathbb{Q}\\ -n/\sqrt{2} & n\not\in\mathbb{Q} \end{cases}$$

Then then $f(f(n)) = -n$ for all rational numbers $n$, including $0$.


If $n$ admits only 32-bit signed arguments and floating point numbers were allowed, then:

$$f(n)=\begin{cases} n + 0.5 & \lfloor{n}\rfloor = n\\ -n - 0.5 & \lfloor{n}\rfloor \not= n \end{cases}$$

share|improve this answer
    
While a good answer to the correpsonding "mathematical" question, this doesn't address the OP's question. (Note that the title doesn't match the actual question asked.) –  mrf Apr 28 at 12:43
    
"real" means one can't involve complex numbers. –  VividD Apr 28 at 12:47
    
I think I understand what you mean. However, from a mathematical perspective, it could also mean that the domain of $f$ is a subset of $\mathbb{R}$, or that the range of $f$ is a subset of $\mathbb{R}$. –  Yiyuan Lee Apr 28 at 12:52

I have a simple answer, which depends on the argument and the return value being known to be 32-bit integers. It can be extended to any known integer type. It will not, however, work with "bignum" types (arbitrary precision).

Imagine a wheel, with integers written around the edge. Put each integer opposite its negative. Two integers won't fit properly: 0 is its own opposite, and the smallest possible negative number is unpaired. The best we can do is to accept that INT32_MIN == fn(fn(0)) and 0 == fn(fn(INT32_MIN)).

Now, we can just spin the wheel by half a rotation to find its negative. And thus we can write fn() as a function that spins the wheel by one-quarter a rotation.

Sadly, we can't just add 0x80000000 to a number to get its negative, as two's complement integers are not actually a wheel. So we can't just add 0x40000000 to get a one-quarter rotation. The code to correctly compute the rotation is a little bit tricky, but not really difficult. It's just a matter of being careful.

Here's my code:

#include <assert.h>
#include <stdio.h>
#include <stdint.h>

int32_t fn(int32_t n)
{
    static const int32_t Q = 0x40000000;  // one-quarter of a rotation

    if (0 <= n && n <= Q)
        return n + Q;
    else if (Q < n && n <= INT32_MAX)
        return -(n - Q);
    else if (INT32_MIN < n && n <= -Q)
        return -(n + Q);
    else if (-Q < n && n <= -1)
        return n - Q;
    else
    {
        assert(n == INT32_MIN);
        return -Q;
    }
}

int32_t neg(int32_t n)
{
    if (0 == n)
        return INT32_MIN;
    if (INT32_MIN == n)
        return 0;
    return -n;
}

int main(int argc, char**argv)
{
    int64_t i;

    for (i = INT32_MIN; i <= INT32_MAX; ++i)
    {
        int32_t n = (int32_t)i;
        assert(neg(n) == fn(fn(n)));
    }
}

I tested this code and it works correctly.

share|improve this answer

Here's a quirky solution (I believe that it's what Hurkyl meant by "bit-tiwddling"): The fact that we are working with 32-bit signed integers means that $x+2^{32}=-x$. This is because the number is represented by the computer in binary, the "most significant" bit is used to determine its sign, and overflow is discarded. Explicitly, if $x\geq 0$ then the $32^\text{nd}$ binary digit is a zero and so adding $2^{32}$ flips it to a one. If $x<0$ then the $32^\text{nd}$ binary digit is a one, so adding $2^{32}$ flips it to zero, and the carry-over one is ignored.

Therefore, we can consider the function $$f(n)=n+2^{31}.$$ Applying this twice clearly gives $f(f(n))=n+2^{32}$, which is the same thing as $-n$.

(Actually, there is one edge case: the number $"\!\!-0\!\!"\,=0+2^{32}$ is actually interpreted as $-2^{31}$. So if $n=-2^{31}$, then $n+2^{32}=0$, and indeed $-x=2^{31}$ is not expressible in the 32-bit signed format, so we'll have to let this one go. In fact, it seems likely to me that this this was the "point" of the question from the interviewer's perspective: not that you could build some random function, but that you could recognize the inherent limitations of the architecture.)

share|improve this answer
    
And apparently this is not how signed integers work anymore? :( I just asked someone I trusted with computers if this would work, and offhand he thought so. But it's possible we're both mistaken…. –  Eric Stucky Apr 29 at 14:48
    
I believe this is the answer an interviewer would be looking for. Just a basic test of "do you know how signed ints work?" –  Jeff Snider Apr 29 at 15:13
    
Ah, I've figured out how to reconcile this answer with Hurkyl's: zero is also taken to the wrong place: $-2^{31}$ instead of $0$. –  Eric Stucky Apr 30 at 2:33

First you should identify that your sequences have the following pattern (using the arrow to indicate successive applications of f):

$$\begin{align} 0 \rightarrow f(0) \rightarrow 0 \\ 1 \rightarrow f(1) \rightarrow -1 \rightarrow f(-1) \rightarrow 1 \\ 2 \rightarrow f(2) \rightarrow -2 \rightarrow f(-2) \rightarrow 2 \\ 3 \rightarrow f(3) \rightarrow -3 \rightarrow f(-3) \rightarrow 3 \\ 4 \rightarrow f(4) \rightarrow -4 \rightarrow f(-4) \rightarrow 4 \\ \vdots \\ 2^{31} \rightarrow f(2^{31}) \rightarrow -2^{31}=2^{31} \\ \end{align}$$

Ignore the special case of $0$ and $2^{31}$ for the moment.

Suppose we choose $f(x) = y$, knowing that $y \not \in \{0, 2^{31}, x, -x\}$. Then we know $f(f(x)) = -x = f(y)$, and likewise $f(-x) = -y$, and $f(-y) =x$. So this one choice uniquely determines the four values of $f(x), f(-x), f(y),$ and $f(-y)$: $$\begin{align} x \rightarrow y \rightarrow -x \rightarrow -y \rightarrow x \\ y \rightarrow -x \rightarrow -y \rightarrow x \rightarrow y \\ \end{align}$$

For the special cases, we can choose $f(0) = 0 {\huge {\land}} f(2^{31}) = 2^{31}$ or we can choose $f(0) = 2^{31} {\huge {\land}} f(2^{31}) = 0$.

For $w$ bits, the 2 special cases give us 2 choices, and any pairing of the remaining rows (cycles) give us the remaining characterization of $f$.

...but how many remaining cycles are there?

Well their starting value ranges from $1$ to $2^{w - 1} - 1$, or there is an odd total number of cycles. Since there is an odd number of cycles, it is actually impossible to construct $f$ because you must leave one cycle out of the pairings. So there will always be one pair $\{x, -x\}$ that will not satisfy the constraints on $f$.

share|improve this answer
    
This is a good answer, but I think you mean $2^{31}$, not $2^{16}$. –  Jeff Snider Apr 29 at 15:17
    
Thanks! I'll fix it now. I even got it right in the last paragraph, what an oversight. –  DanielV Apr 29 at 21:08

If domein is $\mathbb{Q}$:

$$f(x)= \begin{cases} x.3&; x > 0 \land x\in \mathbb{Z}\\ -y&; x\; \text{ is of form }\; y.3\; \text{ for } y\in \mathbb{Z} \end{cases} $$

share|improve this answer

If the number is odd, then subtract one. If the number is even, then add one and then multiply by negative 1.

(Similarly, you could just flip the first, or the last, or any number of the 32 bits, and multiply by -1 if the flipped bit is a $0$.)

share|improve this answer

Apologies for my earlier pessimistic outburst, I think I've found a way with a bit of a limited range.

$$f(x)=(-√x^2 )$$ $$f(f(x))= -√(-√(x^2 ))^2$$ $${x∈ R ,x ≥0}$$

share|improve this answer
    
This throws away half of the domain (remember that the original question posits signed); also, notably, this is somewhat more easily written as $f(x) = -|x|$, the negative of the absolute value of $x$. –  Steven Stadnicki Apr 28 at 22:16

impossible$$ f( f(x) ) = f^2(x)= n $$ $$f(x)= √n$$ $${n ∈ R ,n ≥0} $$ $$∴n ≠ -ve $$

share|improve this answer
    
In fact, $x^2 = a$ does not ONLY mean that $x = \sqrt{a}$. x can also be $- \sqrt{a}$ –  Brendan Rius Apr 28 at 21:36
    
@BrendanRius That's true, but hardly the issue here...the problem is $f(f(x)) \ne (f(x))^2$. –  Goos Apr 29 at 12:33

protected by Community Apr 28 at 21:48

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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