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

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

有什么想法吗?


当前回答

C函数:

int f(int n) /* Treats numbers in the range 0XC0000000 to 0X3FFFFFFF as valid to
                generate f(f(x)) equal to -x. If n is within this range, it will
                project n outside the range. If n is outside the range, it will
                return the opposite of the number whose image is n. */
{
    return n ? n > 0 ? n <= 0X3FFFFFFF ? 0X3FFFFFFF + n : 0X3FFFFFFF - n :\
           n >= 0XC0000000 ? 0XC0000000 + n : 0XC0000000 - n : 0;
}

Ideone测试和下载链接

其他回答

const unsigned long Magic = 0x8000000;

unsigned long f(unsigned long n)
{    
    if(n > Magic )
    {
        return Magic - n;
    }

    return n + Magic;
} 

0~2^31

int f(int n)
{
   static int x = 0;
   result = -x;
   x = n;
   return result;
}

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

int func(int a)  
{   
    static int p = 0;  
    int ret = a;  

    if ( p ) ret *= -1;  
    p ^= 1;  

    return ret;  
}  

使用问题中给出的信息,您可以

从2-完成转换为符号位表示如果设置了最后一位,则翻转符号位和最后一位;否则,只翻转最后一位转换回2-完成。

所以你基本上是奇数->偶数->奇数或偶数->奇数->偶数,只对偶数更改符号。唯一不适用的数字是-2^31

代码:

function f(x) {
  var neg = x < 0;
  x = Math.abs(x) ^ 1;
  if (x & 1) {
    neg = !neg;
  }
  return neg ? -x : x;
}

C#重载:

string f(int i) {
  return i.ToString();
}

int f(string s) {
  return Int32.Parse(s) * -1;
}

Or

object f(object o) {
  if (o.ToString.StartsWith("s"))
    return Int32.Parse(s.Substring(1)) * -1;
  return "s" + i.ToString();
}