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

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

有什么想法吗?


当前回答

return x ^ ((x%2) ? 1 : -INT_MAX);

其他回答

int f(int n)
{
  static long counter=0;
  counter++;
  if(counter%2==0)
    return -n;
  else
    return n;
}

使用复数,您可以有效地将否定数字的任务分为两个步骤:

将n乘以i,得到n*i,n逆时针旋转90°再乘以i,得到-n

最棒的是,您不需要任何特殊的处理代码。只要乘以i就可以了。

但不允许使用复数。因此,您必须使用部分数据范围创建自己的虚拟轴。由于需要的虚(中间)值与初始值一样多,因此只剩下一半的数据范围。

我试图在下图中显示这一点,假设有符号的8位数据。您必须将其缩放为32位整数。初始n的允许范围为-64到+63。下面是函数对正n的作用:

如果n在0..63(初始范围)内,函数调用将添加64,将n映射到范围64..127(中间范围)如果n在64..127(中间范围)内,则函数从64中减去n,将n映射到范围0..-63

对于负n,函数使用中间范围-65..-128。

根据您的平台,某些语言允许您在函数中保持状态。VB.Net,例如:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

IIRC、C++也允许这样做。我怀疑他们正在寻找不同的解决方案。

另一个想法是,由于它们没有定义函数第一次调用的结果,因此可以使用奇数/均匀度来控制是否反转符号:

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

所有偶数的幅度加一,所有奇数的幅度减一。两次调用的结果大小相同,但在一次调用中,我们甚至交换了符号。在某些情况下,这不会起作用(-1,max或min int),但它的效果比迄今为止任何其他建议都要好得多。

对于javascript(或其他动态类型语言),可以让函数接受int或对象,并返回另一个。即

function f(n) {
    if (n.passed) {
        return -n.val;
    } else {
        return {val:n, passed:1};
    }
}

js> f(f(10))  
-10
js> f(f(-10))
10

或者,您可以在强类型语言中使用重载,尽管这可能会破坏规则

int f(long n) {
    return n;
}

long f(int n) {
    return -n;
}

这个怎么样(C语言):

int f(int n)
{
    static int t = 1;
    return (t = t ? 0 : 1) ? -n : n;
}

刚刚试过,而且

f(f(1000)) 

回报-1000

f(f(-1000)) 

返回1000

这是正确的还是我没有抓住重点?