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

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

有什么想法吗?


当前回答

这是一个C/C++解决方案,它不使用任何按位运算符,也不需要任何数学库,尽管这有点作弊。。。

double f(double n)
{
    if (n == (double)(int)n)
        return n + 0.5;
    else
        return -(n - 0.5);
}

这适用于所有32位整数,只有一个异常0x80000000(因为它的相反值不能存储在32位整数系统中)。f(f(n))==-n将始终为真,除非在这种情况下。

不过,我相信有一种更简单、更快的方法来实现它。这只是我第一个想到的。

其他回答

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

使用循环置换方法来实现这一点。

-b a b-a

a b-a-b

在微不足道的情况下f(0)返回0

对不起,我的电话回答很粗糙,28日后我将发布完整版本(现在正在检查…)简单地说,假设f(n)是一个循环排列,问题是如何构造它。

定义fk=f(f(f)f(…f(n))))(k fs)情况k=20.微不足道的情况f(0)返回01.分组,在情况k=2时,分组:{0} {1,2} {3,4} ... {n,n+1 |(n+1)%2=0}注意:我只使用Z+,因为结构不需要使用负数。2.构造排列:如果n%2=0,那么a=n-1 b=n如果n%2=1,则a=n b=n+1

这将产生相同的排列,因为n和f(n)在同一组中。

注意排列为P返回P(n)

对于k=2t,只做上面相同的事情,只做MOD k。对于k=2t-1,虽然该方法有效,但毫无意义,啊?(f(n)=-n正常)

int f(int n) {
    return ((n>0)? -1 : 1) * abs(n);
}

也许我错过了什么?

这不是简单的事情吗

    function f(n)
    {
        if(n ==0 || n < 0){return n;}
        return n * -1;
    }

编辑:

所以我错过了阅读问题,嗯哼,所以:

    function f(n)
    {
        if(!c(n,"z")&&!c(n,"n")){if(n==0){return "z"+n;}return "n"+n;}
        if( c(n,"z")){return 0;}return parseInt(n.replace("n",""))*-1;
    }
    function c(x,y){return x.indexOf(y) !==-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%。