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

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

有什么想法吗?


当前回答

在C中,

int 
f(int n) {
     static int r = 0;
     if (r == 1) {r--; return -1 * n; };
     r++;
     return n;
}

知道这是为了什么语言会有帮助。我错过了什么吗?许多“解决方案”似乎过于复杂,坦率地说,并非如此工作(当我读到问题时)。

其他回答

也许是作弊?(python)

def f(n):    
    if isinstance(n, list):
        return -n[0]
    else:
        return [n,0]    
n = 4
print f(f(n))

--output--
-4

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

…只是当n是32位整数时,f(f(n))=-n

那么,怎么样

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

如果n是32位整数,则语句f(f(n))==-n将为真。

显然,这种方法可以扩展到更大范围的数字。。。

F#

let f n =
    match n with
    | n when n % 2 = 0 -> -n + System.Math.Sign n
    | _ -> n - System.Math.Sign -n

其中n使得System.Int32.MinValue<n<System.Int32.MaxValue。

Python 2.6:

f = lambda n: (n % 2 * n or -n) + (n > 0) - (n < 0)

我意识到这对讨论毫无帮助,但我无法抗拒。

根据微软/谷歌的面试官通常在面试中提出的问题,我认为提问者指的是一种创新、轻量级、简单的解决方案,它将使用按位操作,而不是那些复杂的高级答案。

灵感来自@eipipuz的回答,我编写了这个C++函数(但没有运行它):

int32_t f(int32_t n){
    int32_t temp = n & 00111111111111111111111111111111;
    x = n >> 30;
    x++;
    x = x << 30;
    return x | temp;
}

它将n的最左边的两位存储在x中,将x加1,然后再次将其替换为n的最左侧的两位。

如果我们继续以另一个f(n)作为参数n运行f(n,则最左边的两个位将如下旋转:

00 --> 01 --> 10 --> 11 --> 00 ...

请注意,最右边的30位不变。8位整数示例:

示例1:

>f(00001111)=01001111>f(01001111)=10001111[这是原始值的负值,00001111]

示例2:

>f(11101010)=00101010>f(00101010)=01101010[这是原始值11101010的负值]