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

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

有什么想法吗?


当前回答

我试着打高尔夫,这是罗德里克·查普曼的回答。

无分支:74个字符

int f(int i){return(-((i&1)<<1)|1)*i-(-((i>>>31)<<1)|1)*(((i|-i)>>31)&1);}

带有分支,Java风格:58个字符

int f(int i){return i==0?0:(((i&1)==0?i:-i)+(i>0?-1:1));}

带分支,C样式:52个字符

int f(int i){return i?(((i&1)?-i:i)+(i>0?-1:1)):0;}

经过快速但有效的基准测试后,分支版本在我的机器上的速度提高了33%。(正数和负数的随机数据集,足够的重复,并防止编译器在预热时优化代码。)考虑到非分支版本中的操作数量以及可能的良好分支预测,这并不奇怪,因为函数被调用了两次:f(f(i))。当我将基准更改为度量:f(I)时,分支版本只快28%。我认为这证明了分支预测在第一种情况下确实有一些好处。更多证明:当使用f(f(f)(f(i)))进行测试时,分支版本的速度会快42%。

其他回答

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

def f(x):
    if random.randrange(0, 2):
        return -x
    return x
number f( number n)
{
  static count(0);
  if(count > 0) return -n;
  return n;
}

f(n) = n

f(f(n)) = f(n) = -n

Java脚本

function f(n)  { 
        return typeof n === "number" ? 
        function() {return -n} : 
        n();
}

类似于python中的函数重载解决方案:

def f(number):
 if type(number) != type([]):
  return [].append(number)
 else:
  return -1*number[0]

备选方案:静态数据成员

下面是一个简短的Python答案:

def f(n):
  m = -n if n % 2 == 0 else n
  return m + sign(n)

一般情况

稍微调整一下上面的内容就可以处理我们希望k个自调用否定输入的情况——例如,如果k=3,这意味着g(g(g)n))=-n:

def g(n):
  if n % k: return n + sign(n)
  return -n + (k - 1) * sign(n)

这是通过将0保留在适当位置并创建长度为2*k的循环来实现的,因此,在任何循环中,n和-n之间的距离为k。具体来说,每个周期如下:

N * k + 1, N * k + 2, ... , N * k + (k - 1), - N * k - 1, ... , - N * k - (k - 1)

或者,为了更容易理解,这里是k=3的示例循环:

1, 2, 3, -1, -2, -3
4, 5, 6, -4, -5, -6

这组循环最大化了在任何以零为中心的机器类型(如有符号int32或有符号int64类型)内工作的输入范围。

兼容范围分析

映射x->f(x)实际上必须形成长度为2*k的循环,其中x=0是特殊情况下的1-长度循环,因为-0=0。因此,一般k的问题是可解的,当且仅当输入-1(补偿0)的范围是2*k的倍数,并且正负范围是相反的。

对于有符号整数表示,我们总是有一个最小的负数,在该范围内没有正的对应项,因此该问题在整个范围内变得不可解决。例如,有符号字符的范围为[-128127],因此在给定范围内f(f(-128))=128是不可能的。