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

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

有什么想法吗?


当前回答

Lua:

function f(n)
    if type(n) == "number" then
        return (-number) .. ""
    else
        return number + 0
    end
end

其他回答

这个是Python中的。适用于n的所有负值:

f = abs

在C中,

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

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

容易的:

function f($n) {
   if ($n%2 == 0) return ($n+1)*-1;
   else return ($n-1);
}

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

无分支: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%。

这个问题并没有说明函数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将为真。

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