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

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

有什么想法吗?


当前回答

它通过保存状态来作弊,但它有效,将操作分成两部分:-n=(~n+1)对于整数

int f(int n) {
    static int a = 1;
    a = !a;
    if (a) {
        return (~n);
    } else {
        return (n+1);
    }
}

其他回答

或者,您可以滥用预处理器:

#define f(n) (f##n)
#define ff(n) -n

int main()
{
  int n = -42;
  cout << "f(f(" << n << ")) = " << f(f(n)) << endl;
}

这里有一个证明,如果不使用额外信息(除了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个数字作为奖励。(但这只是一个愚蠢的假设。)

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}
int f(int n)
{
   static int x = 0;
   result = -x;
   x = n;
   return result;
}

这是一个带有否定的单条目FIFO。当然,它不适用于最大负数。

这是rossfabricant答案的C实现。注意,由于我始终使用32位整数,f(f(2147483647))==2147483648,而不是-2147483647。

int32_t f( int32_t n )
{
    if( n == 0 ) return 0;
    switch( n & 0x80000001 ) {
        case 0x00000000:
            return -1 * ( n - 1 );
        case 0x00000001:
            return n + 1;
        case 0x80000000:
            return -1 * ( n + 1 );
        default:
            return n - 1;
    }
}

如果您将问题定义为允许f()接受并返回int64_t,则会涉及2147483647。当然,switch语句中使用的文字必须更改。