我在上次面试中遇到的一个问题是:

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

在Python中

f=lambda n:n[0]if type(n)is list else[-n]

其他回答

我可以想象,使用第31位作为虚(I)位将是一种支持一半总范围的方法。

我有另一个解决方案,它可以在一半时间内工作:

def f(x):
    if random.randrange(0, 2):
        return -x
    return x

Wolfram语言的解决方案:

f[f[n_]] := -n

应用程序:

In[2]:= f[f[10]]                                                                                                                                                                                                                                                                              
Out[2]= -10
In[3]:= f[10]                                                                                                                                                                                                                                                                                 
Out[3]= f[10]

因为这个问题没有说明f(n)的值,所以f[n]仍然没有赋值。

这将在非常广泛的数字范围内发挥作用:

    static int f(int n)
    {
        int lastBit = int.MaxValue;
        lastBit++;
        int secondLastBit = lastBit >> 1;
        int tuple = lastBit | secondLastBit;
        if ((n & tuple) == tuple)
            return n + lastBit;
        if ((n & tuple) == 0)
            return n + lastBit;
        return -(n + lastBit);
    }

我最初的方法是使用最后一位作为检查位,以了解我们在第一次或第二次调用中的位置。基本上,我会在第一次调用后将此位设置为1,以向第二次调用发出第一次调用已经通过的信号。但是,这种方法被负数所击败,负数的最后一位在第一次调用期间已经到达1。

同样的理论适用于大多数负数的倒数第二位。但是,通常发生的情况是,大多数情况下,最后一位和第二位是相同的。它们要么都是负数的1,要么都是正数的0。

所以我的最后一个方法是检查它们是否都是1或都是0,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。

int func(int a)  
{   
    static int p = 0;  
    int ret = a;  

    if ( p ) ret *= -1;  
    p ^= 1;  

    return ret;  
}