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

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

有什么想法吗?


当前回答

适用于n=[0..2^31-1]

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}

其他回答

本质上,函数必须将可用范围划分为大小为4的循环,其中-n位于n循环的另一端。但是,0必须是大小为1的循环的一部分,否则0->x->0->x!=-x.因为0是单独的,所以在我们的范围内必须有3个其他值(其大小是4的倍数)不在具有4个元素的正确循环中。

我选择这些额外的奇怪值为MIN_INT、MAX_INT和MIN_INT+1。此外,MIN_INT+1将正确映射到MAX_INT,但会被卡在那里而不能映射回来。我认为这是最好的妥协,因为它有一个很好的特性,即只有极端值不能正常工作。此外,这意味着它将适用于所有BigInt。

int f(int n):
    if n == 0 or n == MIN_INT or n == MAX_INT: return n
    return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)

C++中的另一个作弊解决方案是运算符重载。

struct func {
    int n;
    func operator()(int k) { n = -k; return *this; }
    int operator()(const func &inst) { return inst.n; }
} f;

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}

在Python中

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

另一种利用短路的Javascript解决方案。

​function f(n) {return n.inv || {inv:-n}}

f(f(1)) => -1
f(f(-1)) => 1