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

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

有什么想法吗?


当前回答

我相信这符合所有要求。没有什么规定参数必须是32位有符号整数,只有你传入的值“n”是。

long long f(long long n)
{
    int high_int = n >> 32;
    int low_int  = n & 0xFFFFFFFF;

    if (high_int == 0) {
        return 0x100000000LL + low_int;
    } else {
        return -low_int;
    }
}

其他回答

从来没有人说过f(x)必须是同一类型。

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]


f(2) => [2]
f(f(2)) => -2

f#中的简单解决方案(不使用“技巧”)

let rec f n =
    if n = 0 then 0
    elif n > 0 then
        if (f (n - 1) <> n) then n + 1
        else -(n - 1)
    else
        if (f (-(n - 1)) = n) then n - 1
        else -(n + 1) 

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

-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正常)

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

无分支: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(n):
    if isinstance(n,int):
        return str(n)
    else:
        return -int(n)