对一道面试题目 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 比特整数了。

参考内容