#对一道面试题目 f(f(n))==-n 的理解

这是一道技术面试题目，其中隐含着很多思想。

不知道大家有没有见过这道题目，一开始自己也没看明白是什么意思，后来根据他人的描述，也大体了解了一些内容了。

#题目描述

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.

大体意思就是：

能不能设计一个函数f(n)，n是int32，让f(f(n))==-n对所有n成立？ 要求不允许使用复数类的运算，不限制语言。如果不存在满足整个int的f(n)，那么尽可能让它对更多int32范围的n成立。

#题目思路

#方法1

对于支持内置状态的函数的语言，我们可以在函数的内部定义一个静态变量，然后让它根据调用次数进行变化。

// C/C++

int f(int n) {
    static int state = -1;
    state *= -1;
    return n * state;
}

这种方法能适用于除了 INT_MIN 之外的所有 32 比特整数。对于 INT_MIN，求负会导致溢出，也即 f(f(INT_MIN)) = INT_MIN。

#方法2

参考方法1的内容，我们可以设计一个全局变量保存这些参数。

private static int state = -1;
public static int f(int i) {
    state *= -1;
    return state * i;
}

这两种方法算是一种捷径了。但是如果没有捷径可以走呢？

#方法3

第三种方法就是从数字本身入手，将数字扩充来保存次数信息。我们可以拿一个 BIT 来储存这样的信息。

// C#

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

这种解法，头 32 比特用来存储 n，第 33 比特用来存储状态信息。它适用于 32 BIT的所有整数，包含了 Int32.MinValue 和 Int32.MaxValue。

#方法4

假设一定要写一个 int f(int) 的函数，那么在哪里可以存储状态信息呢？在哪里可以存储究竟 f 是被执行了奇数次还是偶数次？

可以考虑用奇偶性和正负性来保存这个状态信息。

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

证明 f(f(n)) = -n：

若是 n 是一个正奇数，那么令 n = 2k + 1。则：

f(f(n)) = f(f(2k + 1)) = f( 2 * (2k + 1) - (2k + 1) + 1) = f(2k + 2)) = f(2 * (2k + 2) * 0 - (2k + 2) + 1) = f(-2k - 1) = -n

若是 n 是一个正偶数，那么令 n = 2k。则：

f(f(n)) = f(f(2k)) = f(-2k + 1)) = f(2 * (-2k + 1) - (-2k + 1) - 1) = f(-2k) = -n

若是 n 是一个负奇数，那么令 n = 2k + 1。则：

f(f(n)) = f(f(2k + 1)) = f( 2 * (2k + 1) - (2k + 1) - 1) = f(2k)) = f(2 * (2k) * 0 - (2k) - 1) = f(-2k - 1) = -n

若是 n 是一个负偶数，那么令 n = 2k。则：

f(f(n)) = f(f(2k)) = f(-2k - 1)) = f(2 * (-2k - 1) - (-2k - 1) + 1) = f(-2k) = -n

转换成 C# 代码如下：

// C#

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

因为这里用到 2 * n 的运算，所以函数不适用于所有的 32 比特整数。了解到 2n(abs(n) % 2) - n 的目的其实是为了调整 n 的正负号，可以把代码修改成如下：

// C#

public static int f(int n) {
    if (n % 2 == 0) {
        return -n + Math.Sign(n);
    } else {
        return n + Math.Sign(n);
    }
}

这样，这个函数就能适用于除了 Int32.MinValue 和 Int32.MaxValue 之外所有的 32 比特整数了。

#参考内容

• math - Interview question: f(f(n)) == -n - Stack Overflow
• 技术面试题：f(f(n)) == -n - 百科教程网
• 挑战 f(f(n)) = -n - CSDN论坛