设计函数f(f(n)) == -n。

A question I got on my last interview:

我上次面试的问题是:

Design a function f, such that:

设计一个函数f，这样:

f(f(n)) == -n

Where n is a 32 bit signed integer; you can't use complex numbers arithmetic.

其中n为32位带符号整数;你不能用复数算术。

If you can't design such a function for the whole range of numbers, design it for the largest range possible.

如果你不能为整个数字范围设计这样一个函数，那么就尽可能地设计它。

Any ideas?

什么好主意吗?

118 个解决方案

#1

How about:

如何:

f(n) = sign(n) - (-1)n * n

In Python:

在Python中:

def f(n): 
    if n == 0: return 0
    if n >= 0:
        if n % 2 == 1: 
            return n + 1
        else: 
            return -1 * (n - 1)
    else:
        if n % 2 == 1:
            return n - 1
        else:
            return -1 * (n + 1)

Python automatically promotes integers to arbitrary length longs. In other languages the largest positive integer will overflow, so it will work for all integers except that one.

Python自动地促进整数到任意长度的长度。在其他语言中，最大的正整数将会溢出，所以除了那个整数以外，它将适用于所有整数。

---

To make it work for real numbers you need to replace the n in (-1)ⁿ with { ceiling(n) if n>0; floor(n) if n<0 }.

为了使它适用于实数，你需要把n in (-1)n替换为(n)如果n>0;地板(n)如果n < 0 }。

In C# (works for any double, except in overflow situations):

在c#中(适用于任何double，除了溢出情况):

static double F(double n)
{
    if (n == 0) return 0;

    if (n < 0)
        return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1));
    else
        return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1));
}

#2

You didn't say what kind of language they expected... Here's a static solution (Haskell). It's basically messing with the 2 most significant bits:

你没有说他们期望的是哪种语言……这是一个静态的解决方案(Haskell)。它基本上是在干扰两个最重要的部分:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

It's much easier in a dynamic language (Python). Just check if the argument is a number X and return a lambda that returns -X:

在动态语言(Python)中，它要容易得多。检查参数是否为X，然后返回-X:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

#3

Here's a proof of why such a function can't exist, for all numbers, if it doesn't use extra information(except 32bits of int):

这里有一个证明为什么这样的函数不能存在，对于所有的数字，如果它不使用额外的信息(除了32位int):

We must have f(0) = 0. (Proof: Suppose f(0) = x. Then f(x) = f(f(0)) = -0 = 0. Now, -x = f(f(x)) = f(0) = x, which means that x = 0.)

我们必须有f(0) = 0。(证据:假设f(0)= x,那么f(x)= f(f(0))= 0 = 0。现在，-x = f(f(x)) = f(0) = x，也就是说x = 0。

Further, for any x and y, suppose f(x) = y. We want f(y) = -x then. And f(f(y)) = -y => f(-x) = -y. To summarize: if f(x) = y, then f(-x) = -y, and f(y) = -x, and f(-y) = x.

进一步，对于任意x和y，假设f(x) = y，我们要求f(y) = -x。f(f(y)) = -y => f(-x) = -y。总结:如果f(x) = y，那么f(-x) = -y, f(y) = -x, f(-y) = x。

So, we need to divide all integers except 0 into sets of 4, but we have an odd number of such integers; not only that, if we remove the integer that doesn't have a positive counterpart, we still have 2(mod4) numbers.

所以，我们需要把除0以外的所有整数都除以4，但我们有奇数个这样的整数;不仅如此，如果我们去掉没有正数的整数，我们还有2(mod4)数字。

If we remove the 2 maximal numbers left (by abs value), we can get the function:

如果我们去掉剩下的2个最大的数(用abs的值)，我们就可以得到这个函数:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}   

Of course another option, is to not comply for 0, and get the 2 numbers we removed as a bonus. (But that's just a silly if.)

当然还有另一种选择，就是不遵从0，并将我们删除的2个数字作为奖励。(但这只是一个愚蠢的假设。)

#4

Thanks to overloading in C++:

由于超载，c++:

double f(int var)
{
 return double(var);
} 

int f(double var)
{
 return -int(var);
}

int main(){
int n(42);
std::cout<<f(f(n));
}

#5

Or, you could abuse the preprocessor:

或者，你可以滥用预处理器:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

#6

This is true for all negative numbers.

这对于所有负数都成立。

    f(n) = abs(n)

Because there is one more negative number than there are positive numbers for twos complement integers, f(n) = abs(n) is valid for one more case than f(n) = n > 0 ? -n : n solution that is the same same as f(n) = -abs(n). Got you by one ... :D

因为有一个负数大于两个整数的正数，所以f(n) = abs(n)比f(n) = n > 0更有效。n个解，和f(n) = -abs(n)相同。给你一个……:D

UPDATE

更新

No, it is not valid for one case more as I just recognized by litb's comment ... abs(Int.Min) will just overflow ...

不，这对一个案例来说是无效的，因为我刚刚得到了litb的评论……abs(Int.Min)将会溢出…

I thought about using mod 2 information, too, but concluded, it does not work ... to early. If done right, it will work for all numbers except Int.Min because this will overflow.

我也想过使用mod 2的信息，但结论是，它不起作用……早期。如果做对了，它将适用于所有的数字，除了Int.Min，因为这将溢出。

UPDATE

更新

I played with it for a while, looking for a nice bit manipulation trick, but I could not find a nice one-liner, while the mod 2 solution fits in one.

我玩了一段时间，寻找一个漂亮的操作技巧，但是我找不到一个好的一行程序，而mod 2的解决方案适合一个。

    f(n) = 2n(abs(n) % 2) - n + sgn(n)

In C#, this becomes the following:

在c#中，这变成了:

public static Int32 f(Int32 n)
{
    return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n);
}

To get it working for all values, you have to replace Math.Abs() with (n > 0) ? +n : -n and include the calculation in an unchecked block. Then you get even Int.Min mapped to itself as unchecked negation does.

为了让它为所有值工作，您必须用(n > 0)替换Math.Abs()。+n: -n，并将计算包含在未检查的块中。然后你甚至可以得到Int.Min映射到它自身，就像未检查的否定一样。

UPDATE

更新

Inspired by another answer I am going to explain how the function works and how to construct such a function.

在另一个答案的启发下，我将解释这个函数是如何工作的，以及如何构造这样一个函数。

Lets start at the very beginning. The function f is repeatedly applied to a given value n yielding a sequence of values.

让我们从头开始。函数f被反复应用于给定值n，从而产生一系列的值。

    n => f(n) => f(f(n)) => f(f(f(n))) => f(f(f(f(n)))) => ...

The question demands f(f(n)) = -n, that is two successive applications of f negate the argument. Two further applications of f - four in total - negate the argument again yielding n again.

这个问题要求f(f(n)) = -n，这是f否定这个论点的两个连续的应用。f - 4的两个进一步的应用，完全否定了再次产生n的论点。

    n => f(n) => -n => f(f(f(n))) => n => f(n) => ...

Now there is a obvious cycle of length four. Substituting x = f(n) and noting that the obtained equation f(f(f(n))) = f(f(x)) = -x holds, yields the following.

现在有一个明显的周期是4。代入x = f(n)，并注意到得到的方程f(f(n)) = f(f(x)) = -x，得到以下结果。

    n => x => -n => -x => n => ...

So we get a cycle of length four with two numbers and the two numbers negated. If you imagine the cycle as a rectangle, negated values are located at opposite corners.

所以我们得到一个长度为4的周期，有两个数字，这两个数字是否定的。如果你把这个循环想象成一个长方形，那么否定的值就位于相对的角上。

One of many solution to construct such a cycle is the following starting from n.

构建这样一个循环的众多解决方案之一是从n开始。

 n                 => negate and subtract one
-n - 1 = -(n + 1)  => add one
-n                 => negate and add one
 n + 1             => subtract one
 n

A concrete example is of such an cycle is +1 => -2 => -1 => +2 => +1. We are almost done. Noting that the constructed cycle contains an odd positive number, its even successor, and both numbers negate, we can easily partition the integers into many such cycles (2^32 is a multiple of four) and have found a function that satisfies the conditions.

一个具体的例子是这样一个循环是+1 => -2 => -1 => +2 => +1。我们几乎已经完成了。注意到构造的循环包含一个奇数的正数，它甚至是它的后继，并且两个数字都是负数，我们可以很容易地将整数分割成许多这样的循环(2 32是4的倍数)，并且找到了满足条件的函数。

But we have a problem with zero. The cycle must contain 0 => x => 0 because zero is negated to itself. And because the cycle states already 0 => x it follows 0 => x => 0 => x. This is only a cycle of length two and x is turned into itself after two applications, not into -x. Luckily there is one case that solves the problem. If X equals zero we obtain a cycle of length one containing only zero and we solved that problem concluding that zero is a fixed point of f.

但我们的问题是零。这个循环必须包含0 => x =>，因为0本身是否定的。因为循环状态已经0 => x => x => => x，这只是一个长度为2的周期，x在两个应用程序后变成了自己，而不是-x。幸运的是，有一个案例解决了这个问题。如果X = 0，我们得到一个长度为0的周期，我们解出了这个问题，得出0是f的一个固定点。

Done? Almost. We have 2^32 numbers, zero is a fixed point leaving 2^32 - 1 numbers, and we must partition that number into cycles of four numbers. Bad that 2^32 - 1 is not a multiple of four - there will remain three numbers not in any cycle of length four.

做了什么?几乎。我们有2 ^ 32个数字,0是一个固定的点离开2 ^ 32 - 1数字,我们必须这一数字分割成四个数字的周期。不好的是2 32 - 1不是4的倍数-在任何一个周期中都不会有3个数字。

I will explain the remaining part of the solution using the smaller set of 3 bit signed itegers ranging from -4 to +3. We are done with zero. We have one complete cycle +1 => -2 => -1 => +2 => +1. Now let us construct the cycle starting at +3.

我将使用从-4到+3的更小的3位签名的itegers来解释解决方案的剩余部分。我们完成了零。我们有一个完整的循环+1 => -2 => -1 => +2 => +1。现在让我们从+3开始构建循环。

    +3 => -4 => -3 => +4 => +3

The problem that arises is that +4 is not representable as 3 bit integer. We would obtain +4 by negating -3 to +3 - what is still a valid 3 bit integer - but then adding one to +3 (binary 011) yields 100 binary. Interpreted as unsigned integer it is +4 but we have to interpret it as signed integer -4. So actually -4 for this example or Int.MinValue in the general case is a second fixed point of integer arithmetic negation - 0 and Int.MinValue are mapped to themselve. So the cycle is actually as follows.

出现的问题是+4不能被表示为3位整数。我们可以通过否定-3到+3得到+4，这仍然是一个有效的3位整数，但是加1到+3(二进制011)会产生100个二进制数。解释为无符号整数是+4但我们必须把它解释为有符号整数-4。所以实际上-4对于这个例子或Int.MinValue在一般情况下是整数算术否定的第二个定点，0和Int.MinValue被映射到themselve。所以这个循环实际上是这样的。

    +3 =>    -4 => -3 => -4 => -3

It is a cycle of length two and additionally +3 enters the cycle via -4. In consequence -4 is correctly mapped to itself after two function applications, +3 is correctly mapped to -3 after two function applications, but -3 is erroneously mapped to itself after two function applications.

它是一个长度为2的循环，另外+3通过-4进入循环。结果-4在两个函数应用程序后正确映射到自己，+3在两个函数应用后被正确映射到-3，但是-3在两个函数应用后被错误地映射到自己。

So we constructed a function that works for all integers but one. Can we do better? No, we cannot. Why? We have to construct cycles of length four and are able to cover the whole integer range up to four values. The remaining values are the two fixed points 0 and Int.MinValue that must be mapped to themselves and two arbitrary integers x and -x that must be mapped to each other by two function applications.

所以我们构造了一个对所有整数都有效的函数。我们可以做得更好吗?不,我们不能。为什么?我们必须构建长度为4的周期，并且能够覆盖整个整数范围到4个值。剩下的值是两个固定的0和Int.MinValue，必须映射到它们自己和两个任意整数x和-x，它们必须由两个函数应用程序映射到彼此。

To map x to -x and vice versa they must form a four cycle and they must be located at opposite corners of that cycle. In consequence 0 and Int.MinValue have to be at opposite corners, too. This will correctly map x and -x but swap the two fixed points 0 and Int.MinValue after two function applications and leave us with two failing inputs. So it is not possible to construct a function that works for all values, but we have one that works for all values except one and this is the best we can achieve.

要将x映射到-x，反之亦然，它们必须形成一个4个周期，并且它们必须位于这个循环的相反的角上。结果0和Int.MinValue也必须在相反的角上。这将正确地映射x和-x，但是将两个固定的点0和Int.MinValue交换到两个函数应用程序之后，并留给我们两个失败的输入。因此，我们不可能构造一个对所有值都有效的函数，但是我们有一个对所有值都适用的函数，除了一个，这是我们能做到的最好的。

#7

Using complex numbers, you can effectively divide the task of negating a number into two steps:

使用复数，你可以有效地把否定一个数字的任务分成两个步骤:

• multiply n by i, and you get n*i, which is n rotated 90° counter-clockwise
• n乘以i，就得到n*i，也就是n旋转90。
• multiply again by i, and you get -n
• 再乘以i，得到-n。

The great thing is that you don't need any special handling code. Just multiplying by i does the job.

最重要的是，您不需要任何特殊的处理代码。只是乘以我做的工作。

But you're not allowed to use complex numbers. So you have to somehow create your own imaginary axis, using part of your data range. Since you need exactly as much imaginary (intermediate) values as initial values, you are left with only half the data range.

但是你不能使用复数。因此，你必须以某种方式创建你自己的假想轴，使用你的数据范围的一部分。由于您需要与初始值完全一样的虚构(中间)值，因此只剩下一半的数据范围。

I tried to visualize this on the following figure, assuming signed 8-bit data. You would have to scale this for 32-bit integers. The allowed range for initial n is -64 to +63. Here's what the function does for positive n:

我试着在下面的图中对这个进行可视化，假设它包含了8位数据。你需要对32位整数进行缩放。初始n的允许范围是-64到+63。这个函数的作用是:

• If n is in 0..63 (initial range), the function call adds 64, mapping n to the range 64..127 (intermediate range)
• 如果n在0。63(初始范围)，函数调用增加64，映射n到范围64..127(中间范围)
• If n is in 64..127 (intermediate range), the function subtracts n from 64, mapping n to the range 0..-63
• 如果n是64。127(中间范围)，函数将n从64减去n，映射到0。-63。

For negative n, the function uses the intermediate range -65..-128.

对于- n，函数使用中间范围-65。-128。

#8

Works except int.MaxValue and int.MinValue

工作，除了。maxvalue和int.MinValue。

    public static int f(int x)
    {

        if (x == 0) return 0;

        if ((x % 2) != 0)
            return x * -1 + (-1 *x) / (Math.Abs(x));
        else
            return x - x / (Math.Abs(x));
    }

#9

The question doesn't say anything about what the input type and return value of the function f have to be (at least not the way you've presented it)...

这个问题并没有说明函数f的输入类型和返回值是多少(至少不是你给出的方式)。

...just that when n is a 32-bit integer then f(f(n)) = -n

…当n是一个32位整数时f(f(n)) = -n。

So, how about something like

比如。

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

If n is a 32-bit integer then the statement f(f(n)) == -n will be true.

如果n是一个32位整数，那么f(f(n)) == -n为真。

Obviously, this approach could be extended to work for an even wider range of numbers...

显然，这种方法可以推广到更广泛的数字范围内。

#10

for javascript (or other dynamically typed languages) you can have the function accept either an int or an object and return the other. i.e.

对于javascript(或其他动态类型语言)，可以让函数接受int或对象，并返回另一个。即。

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

giving

给

js> f(f(10))  
-10
js> f(f(-10))
10

alternatively you could use overloading in a strongly typed language although that may break the rules ie

或者，您也可以使用强类型语言重载，尽管这可能违反规则。

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}

#11

Depending on your platform, some languages allow you to keep state in the function. VB.Net, for example:

根据您的平台，有些语言允许您在函数中保持状态。VB。净,例如:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

IIRC, C++ allowed this as well. I suspect they're looking for a different solution though.

IIRC, c++也允许这样做。我怀疑他们在寻找另一种解决方案。

Another idea is that since they didn't define the result of the first call to the function you could use odd/evenness to control whether to invert the sign:

另一个想法是，由于他们没有定义对函数的第一次调用的结果，你可以用奇/偶数来控制是否反转符号:

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

Add one to the magnitude of all even numbers, subtract one from the magnitude of all odd numbers. The result of two calls has the same magnitude, but the one call where it's even we swap the sign. There are some cases where this won't work (-1, max or min int), but it works a lot better than anything else suggested so far.

加1到所有偶数的大小，从所有奇数中减去1。两个调用的结果具有相同的大小，但是一个调用，甚至我们交换了符号。有些情况下，这是行不通的(-1，最大值或最小值)，但它比其他建议的效果要好得多。

#12

Exploiting JavaScript exceptions.

利用JavaScript的例外。

function f(n) {
    try {
        return n();
    }
    catch(e) { 
        return function() { return -n; };
    }
}

f(f(0)) => 0

f(f(0))= > 0

f(f(1)) => -1

f(f(1))= > 1

#13

For all 32-bit values (with the caveat that -0 is -2147483648)

对于所有32位值(需要注意的是-0是-2147483648)

int rotate(int x)
{
    static const int split = INT_MAX / 2 + 1;
    static const int negativeSplit = INT_MIN / 2 + 1;

    if (x == INT_MAX)
        return INT_MIN;
    if (x == INT_MIN)
        return x + 1;

    if (x >= split)
        return x + 1 - INT_MIN;
    if (x >= 0)
        return INT_MAX - x;
    if (x >= negativeSplit)
        return INT_MIN - x + 1;
    return split -(negativeSplit - x);
}

You basically need to pair each -x => x => -x loop with a y => -y => y loop. So I paired up opposite sides of the split.

你基本上需要对每一个-x => x => -x循环与y => -y => y循环。所以我把两边都分成了一组。

e.g. For 4 bit integers:

4位整数:

0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3

#14

A C++ version, probably bending the rules somewhat but works for all numeric types (floats, ints, doubles) and even class types that overload the unary minus:

一个c++版本，可能稍微弯曲了规则，但适用于所有数字类型(浮点型、int型、双级)，甚至是类类型，这些类型重载了unary -:

template <class T>
struct f_result
{
  T value;
};

template <class T>
f_result <T> f (T n)
{
  f_result <T> result = {n};
  return result;
}

template <class T>
T f (f_result <T> n)
{
  return -n.value;
}

void main (void)
{
  int n = 45;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
  float p = 3.14f;
  cout << "f(f(" << p << ")) = " << f(f(p)) << endl;
}

#15

x86 asm (AT&T style):

x86 asm(AT&T风格):

; input %edi
; output %eax
; clobbered regs: %ecx, %edx
f:
    testl   %edi, %edi
    je  .zero

    movl    %edi, %eax
    movl    $1, %ecx
    movl    %edi, %edx
    andl    $1, %eax
    addl    %eax, %eax
    subl    %eax, %ecx
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edx
    subl    %edx, %eax
    imull   %ecx, %eax
    subl    %eax, %edi
    movl    %edi, %eax
    imull   %ecx, %eax
.zero:
    xorl    %eax, %eax
    ret

Code checked, all possible 32bit integers passed, error with -2147483647 (underflow).

代码检查，所有可能的32位整数都通过了，错误为-2147483647(下流)。

#16

Uses globals...but so?

使用全局变量…但如此呢?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}

#17

This Perl solution works for integers, floats, and strings.

这个Perl解决方案适用于整数、浮点数和字符串。

sub f {
    my $n = shift;
    return ref($n) ? -$$n : \$n;
}

Try some test data.

尝试一些测试数据。

print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';

Output:

输出:

-2 2
0 0
1 -1
1.1 -1.1
-3.3 3.3
foo -foo
-bar +bar

#18

Nobody ever said f(x) had to be the same type.

没有人说过f(x)必须是相同的类型。

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]


f(2) => [2]
f(f(2)) => -2

#19

I'm not actually trying to give a solution to the problem itself, but do have a couple of comments, as the question states this problem was posed was part of a (job?) interview:

我并不是在试图给出一个解决问题的方法，但确实有一些评论，因为问题是这个问题是一个(工作?)面试的一部分:

• I would first ask "Why would such a function be needed? What is the bigger problem this is part of?" instead of trying to solve the actual posed problem on the spot. This shows how I think and how I tackle problems like this. Who know? That might even be the actual reason the question is asked in an interview in the first place. If the answer is "Never you mind, assume it's needed, and show me how you would design this function." I would then continue to do so.
• 我首先会问“为什么需要这样的功能?”这是一个更大的问题，而不是试图解决现场的实际问题。这显示了我的想法和我如何处理这样的问题。谁知道呢?这甚至可能是面试中第一个问题被问到的真正原因。如果答案是“你不介意，假设它是必要的，并告诉我你将如何设计这个功能。”我将继续这样做。
• Then, I would write the C# test case code I would use (the obvious: loop from int.MinValue to int.MaxValue, and for each n in that range call f(f(n)) and checking the result is -n), telling I would then use Test Driven Development to get to such a function.
• 然后，我将编写我将使用的c#测试用例代码(明显的:从int.MinValue到int.MaxValue的循环，对该范围内的每个n调用f(f(n))，并检查结果是-n)，告诉我将使用测试驱动开发来达到这样的功能。
• Only if the interviewer continues asking for me to solve the posed problem would I actually start to try and scribble pseudocode during the interview itself to try and get to some sort of an answer. However, I don't really think I would be jumping to take the job if the interviewer would be any indication of what the company is like...
• 只有当面试官继续要求我解决这个问题的时候，我才会在面试过程中开始尝试写伪代码，试图找到某种答案。然而，我并不认为如果面试官对公司的情况有任何的了解，我也不会贸然接受这份工作。

Oh, this answer assumes the interview was for a C# programming related position. Would of course be a silly answer if the interview was for a math related position. ;-)

哦，这个答案假定面试是为了一个c#编程相关的职位。如果面试是为了数学相关的职位，那当然是一个愚蠢的回答。:-)

#20

I would you change the 2 most significant bits.

我要你改变两个最重要的部分。

00.... => 01.... => 10.....

01.... => 10.... => 11.....

10.... => 11.... => 00.....

11.... => 00.... => 01.....

As you can see, it's just an addition, leaving out the carried bit.

正如你所看到的，它只是一个加法，省略了被携带的比特。

How did I got to the answer? My first thought was just a need for symmetry. 4 turns to get back where I started. At first I thought, that's 2bits Gray code. Then I thought actually standard binary is enough.

我是怎么得到答案的?我的第一个想法就是需要对称。4转身回到我开始的地方。一开始我想，这是2bit的灰色代码。然后我认为标准二进制就足够了。

#21

Here is a solution that is inspired by the requirement or claim that complex numbers can not be used to solve this problem.

这里有一个解决方案，它是受需求的启发，或者声称复杂的数字不能用来解决这个问题。

Multiplying by the square root of -1 is an idea, that only seems to fail because -1 does not have a square root over the integers. But playing around with a program like mathematica gives for example the equation

乘以-1的平方根是一个想法，因为-1在整数上没有平方根。但是像mathematica这样的程序，可以给出一个等式。

(1849436465²+1) mod (2³²-3) = 0.

(18494364652+1)mod(232-3) = 0。

and this is almost as good as having a square root of -1. The result of the function needs to be a signed integer. Hence I'm going to use a modified modulo operation mods(x,n) that returns the integer y congruent to x modulo n that is closest to 0. Only very few programming languages have suc a modulo operation, but it can easily be defined. E.g. in python it is:

这几乎和1的平方根一样好。函数的结果需要是一个有符号整数。因此，我将使用一个经过修改的模块操作mods(x,n)，它返回最接近于0的整数y全等。只有很少的编程语言有suc一个模块操作，但是它可以很容易地定义。在python中，它是:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n
    return y

Using the equation above, the problem can now be solved as

利用上面的方程，这个问题现在可以解决了。

def f(x):
    return mods(x*1849436465, 2**32-3)

This satisfies f(f(x)) = -x for all integers in the range [-231-2, 231-2]. The results of f(x) are also in this range, but of course the computation would need 64-bit integers.

这就满足了f(f(x)) = -x的范围内的所有整数[-231- 2,231 -2]。f(x)的结果也在这个范围内，但是当然计算需要64位整数。

#22

C# for a range of 2^32 - 1 numbers, all int32 numbers except (Int32.MinValue)

c#的2 ^ 32 - 1数字,所有int32数字除了(Int32.MinValue)

    Func<int, int> f = n =>
        n < 0
           ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30))
           : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30));

    Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1
    for (int i = -3; i <= 3  ; i++)
        Console.WriteLine(f(f(i)));
    Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647

prints:

打印:

2147483647
3
2
1
0
-1
-2
-3
-2147483647

#23

Essentially the function has to divide the available range into cycles of size 4, with -n at the opposite end of n's cycle. However, 0 must be part of a cycle of size 1, because otherwise 0->x->0->x != -x. Because of 0 being alone, there must be 3 other values in our range (whose size is a multiple of 4) not in a proper cycle with 4 elements.

本质上，函数必须将可用范围划分为4大小的周期，在n周期的另一端为-n。但是，0必须是1的循环的一部分，因为否则0->x->0->x != -x。由于0是单独的，所以在我们的范围内必须有3个其他值(其大小是4的倍数)，而不是在一个具有4个元素的适当周期中。

I chose these extra weird values to be MIN_INT, MAX_INT, and MIN_INT+1. Furthermore, MIN_INT+1 will map to MAX_INT correctly, but get stuck there and not map back. I think this is the best compromise, because it has the nice property of only the extreme values not working correctly. Also, it means it would work for all BigInts.

我选择这些额外的怪异值为MIN_INT、MAX_INT和MIN_INT+1。此外，MIN_INT+1将正确映射到MAX_INT，但是会被卡在那里，而不是映射回。我认为这是最好的折衷方案，因为它的优点是只有极端值不能正常工作。同时，这也意味着它将适用于所有的BigInts。

int f(int n):
    if n == 0 or n == MIN_INT or n == MAX_INT: return n
    return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)

#24

Nobody said it had to be stateless.

没有人说它必须是无状态的。

int32 f(int32 x) {
    static bool idempotent = false;
    if (!idempotent) {
        idempotent = true;
        return -x;
    } else {
        return x;
    }
}

Cheating, but not as much as a lot of the examples. Even more evil would be to peek up the stack to see if your caller's address is &f, but this is going to be more portable (although not thread safe... the thread-safe version would use TLS). Even more evil:

欺骗，但没有很多例子。更糟糕的是，你可以向堆栈中窥视，看看你的来电者的地址是否为f，但这将更方便携带(虽然不是线程安全的……)线程安全的版本将使用TLS。更邪恶:

int32 f (int32 x) {
    static int32 answer = -x;
    return answer;
}

Of course, neither of these works too well for the case of MIN_INT32, but there is precious little you can do about that unless you are allowed to return a wider type.

当然，对于MIN_INT32的情况，这两种方法都不是很好，但是除非您可以返回更广泛的类型，否则您可以做的很少。

#25

I could imagine using the 31st bit as an imaginary (i) bit would be an approach that would support half the total range.

我可以想象，用31比特作为一个假想的(I)位，将会是一个支持一半总范围的方法。

#26

works for n= [0 .. 2^31-1]

n= [0 ..]2 ^还有)

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}

#27

The problem states "32-bit signed integers" but doesn't specify whether they are twos-complement or ones-complement.

问题状态为“32位有符号整数”，但没有指定它们是两个-补充还是一个-补充。

If you use ones-complement then all 2^32 values occur in cycles of length four - you don't need a special case for zero, and you also don't need conditionals.

如果你使用ones-complement那么2 ^ 32值发生在周期的长度4 -你不需要一个特殊情况为零,你也不需要条件。

In C:

在C:

int32_t f(int32_t x)
{
  return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU;
}

This works by

这是通过

1. Exchanging the high and low 16-bit blocks
2. 交换高和低16位块。
3. Inverting one of the blocks
4. 把一个积木倒过来。

After two passes we have the bitwise inverse of the original value. Which in ones-complement representation is equivalent to negation.

经过两遍之后，我们得到了原始值的位逆。在一个补码表示中等于否定。

Examples:

例子:

Pass |        x
-----+-------------------
   0 | 00000001      (+1)
   1 | 0001FFFF (+131071)
   2 | FFFFFFFE      (-1)
   3 | FFFE0000 (-131071)
   4 | 00000001      (+1)

Pass |        x
-----+-------------------
   0 | 00000000      (+0)
   1 | 0000FFFF  (+65535)
   2 | FFFFFFFF      (-0)
   3 | FFFF0000  (-65535)
   4 | 00000000      (+0)

#28

:D

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}

#29

return x ^ ((x%2) ? 1 : -INT_MAX);

#30

I'd like to share my point of view on this interesting problem as a mathematician. I think I have the most efficient solution.

作为一个数学家，我想和大家分享我对这个有趣问题的看法。我想我有最有效的解决办法。

If I remember correctly, you negate a signed 32-bit integer by just flipping the first bit. For example, if n = 1001 1101 1110 1011 1110 0000 1110 1010, then -n = 0001 1101 1110 1011 1110 0000 1110 1010.

如果我没记错的话，你只需要翻转第一个比特就可以否定一个有符号的32位整数。例如，如果n = 1001 1101101 1110 1011 1110 0000 1110 1010，那么-n = 0001 11011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011011。

So how do we define a function f that takes a signed 32-bit integer and returns another signed 32-bit integer with the property that taking f twice is the same as flipping the first bit?

那么我们如何定义一个函数f，它取一个有符号的32位整数，然后返回另一个32位的整数，它的性质是，取f两次的性质和第一个比特相同?

Let me rephrase the question without mentioning arithmetic concepts like integers.

让我重新表述这个问题，而不提像整数这样的算术概念。

How do we define a function f that takes a sequence of zeros and ones of length 32 and returns a sequence of zeros and ones of the same length, with the property that taking f twice is the same as flipping the first bit?

我们如何定义一个函数f，它取一个0和一个长度为32的序列，然后返回一个0和相同长度的序列，用f两次的性质和第一个比特相同?

Observation: If you can answer the above question for 32 bit case, then you can also answer for 64 bit case, 100 bit case, etc. You just apply f to the first 32 bit.

观察:如果你能回答上面的问题32位，那么你也可以回答64位的情况，100位的情况，等等。你只要把f应用到前32位。

Now if you can answer the question for 2 bit case, Voila!

现在，如果你能回答这个问题2个小案例，瞧!

And yes it turns out that changing the first 2 bits is enough.

是的，改变前2位就足够了。

Here's the pseudo-code

这是伪代码

1. take n, which is a signed 32-bit integer.
2. swap the first bit and the second bit.
3. flip the first bit.
4. return the result.

Remark: The step 2 and the step 3 together can be summerised as (a,b) --> (-b, a). Looks familiar? That should remind you of the 90 degree rotation of the plane and the multiplication by the squar root of -1.

注:第2步和第3步一起可以作为(a,b) -> (-b, a)。看起来熟悉吗?这应该会提醒你们，平面的90度旋转和乘以-1的平方根。

If I just presented the pseudo-code alone without the long prelude, it would seem like a rabbit out of the hat, I wanted to explain how I got the solution.

如果我只是单纯地展示伪代码，而没有冗长的序曲，它看起来就像从帽子里出来的兔子，我想解释一下我是如何得到这个解决方案的。