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.
On
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}$$
On
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.)
On
If domain 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} $$
On
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?
On
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$.)
On
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}$$
On
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.
On
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$.
On
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
and thus with this extension, $f(f(a)) = -a$ as well.
On
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.)
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:
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.