技术面试题：f(f(n)) == -n _求职面试_非技术区_程序员俱乐部

最近遇到的一个技术面试题，在这里分享一下。题目是设计一个函数 f，使得

 f(f(n)) = -n

这里 n 是一个 32 比特的整数。不可以使用虚数运算或者复数运算。

如果你无法设计出一个函数使得其对32比特下的所有整数都适用，那么设计此函数使得其能够适用于尽可能多的整数。

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.

 

尝试一： 

对于支持函数内置状态的语言，比如C语言来说，可以很容易的解决这个面试题。如下的代码即可：

 

// C/C++
int f(int n) {
    static int state = -1;
    state *= -1;
    
    return n * state;
}   这里定义了一个函数内置状态变量 state。第一次执行函数 f 的时候，state 等于 1，函数返回 n。第二次执行该函数的时候，state 等于 -1，函数返回 -n。这个解法能适用于除了 INT_MIN 之外的所有 32 比特整数。对于 INT_MIN，求负会导致溢出，也即 f(f(INT_MIN)) = INT_MIN。   当然，这个题目不应该是那么容易解决的。若是用不支持内置状态的语言，比如 C# 或者 Java，应该如何解决？     尝试二：   可以使用全局变量，来存储状态。比如如下的 C# 代码：   private static int state = -1;
public static int f(int i) {
    state *= -1;
    return state * i;
} 但是这个解法依然不完美，感觉题意不是如此。     尝试三：   为了解决这个问题，其实我们需要在整数 n 本身存储一个状态信息，用来存储执行 f 函数的次数。若是执行偶数次的时候，返回 -n 即可。那么，我们可以拿一个比特，来存储这个状态信息。   代码如下：   // C#
public static long f(long n) {
    return (n > Int32.MaxValue ?
                -(n - 4L * Int32.MaxValue) :
                n + 4L * Int32.MaxValue);
} 这里钻了个漏空。原题里面只是说了 n 是一个 32 比特的整数，并没有要求函数的声明必须是 int f(int)。所以这里我用到了 long f(long)。其中，头 32 比特用来存储 n，第 33 比特用来存储状态信息。这个解法适用于 32 比特的所有整数，包含了 Int32.MinValue 和 Int32.MaxValue。   测试代码如下：   // C#
static void Main(string[] args) {
    long x;

    x = -3; Console.WriteLine("{0} -> {1}", x, f(f(x)));
    x = -2; Console.WriteLine("{0} -> {1}", x, f(f(x)));
    x = -1; Console.WriteLine("{0} -> {1}", x, f(f(x)));
    x = 0; Console.WriteLine("{0} -> {1}", x, f(f(x)));
    x = 1; Console.WriteLine("{0} -> {1}", x, f(f(x)));
    x = 2; Console.WriteLine("{0} -> {1}", x, f(f(x)));
    x = 3; Console.WriteLine("{0} -> {1}", x, f(f(x)));

    x = Int32.MaxValue; Console.WriteLine("{0} -> {1}", x, f(f(x)));
    x = Int32.MinValue; Console.WriteLine("{0} -> {1}", x, f(f(x)));

    Console.ReadKey();
    
}   打印的结果是：   -3 -> 3
-2 -> 2
-1 -> 1
0 -> 0
1 -> -1
2 -> -2
3 -> -3
2147483647 -> -2147483647
-2147483648 -> 2147483648     尝试四：   假设一定要写一个 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 比特整数了。

本文来自：http://www.cnblogs.com/yinyueyouge/archive/2009/05/25/1488921.html