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

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

有什么想法吗?


当前回答

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

其他回答

根据您的平台,某些语言允许您在函数中保持状态。VB.Net,例如:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

IIRC、C++也允许这样做。我怀疑他们正在寻找不同的解决方案。

另一个想法是,由于它们没有定义函数第一次调用的结果,因此可以使用奇数/均匀度来控制是否反转符号:

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

所有偶数的幅度加一,所有奇数的幅度减一。两次调用的结果大小相同,但在一次调用中,我们甚至交换了符号。在某些情况下,这不会起作用(-1,max或min int),但它的效果比迄今为止任何其他建议都要好得多。

Python 2.6:

f = lambda n: (n % 2 * n or -n) + (n > 0) - (n < 0)

我意识到这对讨论毫无帮助,但我无法抗拒。

另一种方法是将状态保持在一位,并在负数的情况下翻转它,注意二进制表示。。。限制为2^29

整数ffn(整数n){

    n = n ^ (1 << 30); //flip the bit
    if (n>0)// if negative then there's a two's complement
    {
        if (n & (1<<30))
        {
            return n;
        }
        else
        {
            return -n;
        }
    }
    else
    {
        if (n & (1<<30))
        {
            return -n;
        }
        else
        {
            return n;
        }
    }


}

这里有一个证明,如果不使用额外信息(除了32位的int),那么对于所有数字,这样的函数都不可能存在:

我们必须使f(0)=0。(证明:假设f(0)=x,则f(x)=f(f(0))=-0=0。现在,-x=f(f(x))=f(0)=x,这意味着x=0。)

此外,对于任何x和y,假设f(x)=y。那么我们希望f(y)=-x。并且f(f(y))=-y=>f(-x)=-y。总结一下:如果f(x)=y,那么f(-x)=-y,f(y)=-x,f(-y)=x。

因此,我们需要将除0之外的所有整数分成4个集合,但我们有奇数个这样的整数;不仅如此,如果我们去掉没有正对应的整数,我们仍然有2(mod4)个数。

如果我们去掉剩下的2个最大数(通过abs值),我们可以得到函数:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}   

当然,另一种选择是不遵守0,并获得我们删除的2个数字作为奖励。(但这只是一个愚蠢的假设。)

我认为最大的可能范围是暗示模块化算术解决方案。在一些模基M中,有一个数,当平方等于M-1(等于-1)。例如,如果M=13,5*5=25,25 mod 13=12(=-1)总之,这里有一些M=2**32-3的python代码。

def f(x):
    m=2**32-3;
    halfm=m//2;
    i_mod_m=1849436465
    if abs( x ) >halfm:
        raise "too big"
    if x<0:
        x+=m
    x=(i_mod_m*x) % m
    if (x>halfm):
        x-=m
    return x;

注意,有3个值不适用于2**31-1、-(2**31-1)和-(2*#31)