〖转贴〗技术面试题：f(f(n)) == -n

（转自博客园）最近遇到的一个技术面试题，在这里分享一下。题目是设计一个函数 f，使得 f(f(n)) = -n这里 n 是一个 32 比特的整数。不可以使用复数运算。如果你无法设计出一个函数使得其对32比特下的所有整数都适用，那么设计此函数使得其能够适用于尽可能多的整数。 Design a function f, such that: f(f(n)) == -n
Where n is a 32 bit signed integer; you can't use complex numbers arithmetic.If you can't design such a function for the whole range of numbers, design it for the largest range possible.

解决方案 »

  1.   

    int match(int i)
    {
       if(i<0)
       {
          return -i;
       }
       else
       {
          return i;
       }
    }
    所有大于0的数都好用~~思考中。
      

  2.   

    using System;class Program
    {
      static void Main()
      {
        foreach (int n in new int[] { 0, 1, 2, 3, 4, 1000, 1001, -1, -2, -3, -4, -1000, -1001, int.MaxValue - 1, int.MinValue+1, int.MaxValue, int.MinValue })
        {
          Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
          Console.Write((long)n == -(long)(f(f(n))) ? "OK" : "ERROR");
          Console.WriteLine();
        }
      }
      
      static long f(long n)
      {
        if ((n & 1) == 0) return -n + Math.Sign(n);
        return n + Math.Sign(n);
      }
    }
    /* 程序输出：
    n = 0            f(n) = 0            f(f(n)) = 0            OK
    n = 1            f(n) = 2            f(f(n)) = -1           OK
    n = 2            f(n) = -1           f(f(n)) = -2           OK
    n = 3            f(n) = 4            f(f(n)) = -3           OK
    n = 4            f(n) = -3           f(f(n)) = -4           OK
    n = 1000         f(n) = -999         f(f(n)) = -1000        OK
    n = 1001         f(n) = 1002         f(f(n)) = -1001        OK
    n = -1           f(n) = -2           f(f(n)) = 1            OK
    n = -2           f(n) = 1            f(f(n)) = 2            OK
    n = -3           f(n) = -4           f(f(n)) = 3            OK
    n = -4           f(n) = 3            f(f(n)) = 4            OK
    n = -1000        f(n) = 999          f(f(n)) = 1000         OK
    n = -1001        f(n) = -1002        f(f(n)) = 1001         OK
    n = 2147483646   f(n) = -2147483645  f(f(n)) = -2147483646  OK
    n = -2147483647  f(n) = -2147483648  f(f(n)) = 2147483647   OK
    n = 2147483647   f(n) = 2147483648   f(f(n)) = -2147483647  OK
    n = -2147483648  f(n) = 2147483647   f(f(n)) = 2147483648   OK
    */
      

  3.   

    如果函数原形要求是：int f(int n)，也就是自变量和返回值都是int，
    则有两个值是错的：int.MinValue 和 int.MaxValue，
    不知能不能减少到一个值。using System;class Program
    {
      static void Main()
      {
        foreach (int n in new int[] { 0, 1, 2, 3, 4, 1000, 1001, -1, -2, -3, -4, -1000, -1001, int.MaxValue - 1, int.MinValue+1, int.MaxValue, int.MinValue })
        {
          Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
          Console.Write((long)n == -(long)(f(f(n))) ? "OK" : "ERROR");
          Console.WriteLine();
        }
      }
      
      static int f(int n)
      {
        if ((n & 1) == 0) return -n + Math.Sign(n);
        return n + Math.Sign(n);
      }
    }
    /* 程序输出：
    n = 0            f(n) = 0            f(f(n)) = 0            OK
    n = 1            f(n) = 2            f(f(n)) = -1           OK
    n = 2            f(n) = -1           f(f(n)) = -2           OK
    n = 3            f(n) = 4            f(f(n)) = -3           OK
    n = 4            f(n) = -3           f(f(n)) = -4           OK
    n = 1000         f(n) = -999         f(f(n)) = -1000        OK
    n = 1001         f(n) = 1002         f(f(n)) = -1001        OK
    n = -1           f(n) = -2           f(f(n)) = 1            OK
    n = -2           f(n) = 1            f(f(n)) = 2            OK
    n = -3           f(n) = -4           f(f(n)) = 3            OK
    n = -4           f(n) = 3            f(f(n)) = 4            OK
    n = -1000        f(n) = 999          f(f(n)) = 1000         OK
    n = -1001        f(n) = -1002        f(f(n)) = 1001         OK
    n = 2147483646   f(n) = -2147483645  f(f(n)) = -2147483646  OK
    n = -2147483647  f(n) = -2147483648  f(f(n)) = 2147483647   OK
    n = 2147483647   f(n) = -2147483648  f(f(n)) = 2147483647   ERROR
    n = -2147483648  f(n) = 2147483647   f(f(n)) = -2147483648  ERROR
    */
      

  4.   

    写了一个，貌似可以实现，大家试试：
    public int f(int n)
    {
        if (n > 0)
        {
            if ((n & 1) == 0)
                return n - 1;
            return ~n;
        }
        if (n < 0)
        {
            if ((n & 1) == 0)
                return n + 1;
            return ~n + 2;
        }
        return 0;
    }
      

  5.   

    //这个行不行呢?
    int f(int n) {
      static int sign = 0;
      if(0 == sign%2){
        sign++;
        return n;
      }
      //else if(1 == sign%2)
      return -n;
    }
      

  6.   

    你那个，我试了一下，也是两个值ERROR：
    using System;class Program
    {
      static void Main()
      {
        foreach (int n in new int[] { int.MinValue+1, int.MinValue })
        {
          Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
          Console.Write((long)f(f(n)) == -(long)n ? "OK" : "ERROR");
          Console.WriteLine();
        }
      }
      
      static int f(int n)
      {
        if (n > 0)
        {
          if ((n & 1) == 0) return n - 1;
          return ~n;
        }
        if (n < 0)
        {
          if ((n & 1) == 0) return n + 1;
          return ~n + 2;
        }
        return 0;
      }
    }
    /* 程序输出：
    n = -2147483647  f(n) = -2147483648  f(f(n)) = -2147483647  ERROR
    n = -2147483648  f(n) = -2147483647  f(f(n)) = -2147483648  ERROR
    */
      

  7.   

    这样，还是两个值ERROR:
    using System;class Program
    {
      static void Main()
      {
        foreach (int n in new int[] { int.MinValue, 0, 1, 2, 3, int.MaxValue - 1, int.MaxValue, -1, -2, -3, int.MinValue+2, int.MinValue+1 })
        {
          Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
          Console.Write((long)f(f(n)) == -(long)n ? "OK" : "ERROR");
          Console.WriteLine();
        }
      }
      
      static int f(int n)
      {
        if (n == 0) return -int.MaxValue;
        if (n == int.MaxValue) return 0;
        if ((n & 1) == 0) return Math.Sign(n) - n;
        return Math.Sign(n) + n;
      }
    }
    /* 程序输出：
    n = -2147483648  f(n) = 2147483647   f(f(n)) = 0            ERROR
    n = 0            f(n) = -2147483647  f(f(n)) = -2147483648  ERROR
    n = 1            f(n) = 2            f(f(n)) = -1           OK
    n = 2            f(n) = -1           f(f(n)) = -2           OK
    n = 3            f(n) = 4            f(f(n)) = -3           OK
    n = 2147483646   f(n) = -2147483645  f(f(n)) = -2147483646  OK
    n = 2147483647   f(n) = 0            f(f(n)) = -2147483647  OK
    n = -1           f(n) = -2           f(f(n)) = 1            OK
    n = -2           f(n) = 1            f(f(n)) = 2            OK
    n = -3           f(n) = -4           f(f(n)) = 3            OK
    n = -2147483646  f(n) = 2147483645   f(f(n)) = 2147483646   OK
    n = -2147483647  f(n) = -2147483648  f(f(n)) = 2147483647   OK
    */不过，如果把 int.MinValue 当作“负零”来看待的话：
    n = -2147483648  f(n) = 2147483647   f(f(n)) = 0            ERROR  // -2147483648 看作 -0
    n = 0            f(n) = -2147483647  f(f(n)) = -2147483648  ERROR  // -2147483648 看作 -0
      

  8.   

    LZ的原题说：显然，当n = -2147483648时不可能返回2147483648。
    所以，应该努力使对于32位有符号整数范围内的其他n，f(f(n)) = -n。
      

  9.   

    用static int 值 就好
      

  10.   

    int f(n)
        {
         int i=-n;
         return n+i;
        }
      

  11.   

    换一种思路就能得到完美答案：
    class F
    {
        int n;    public static F f(int n)
        {
            F a = new F();
            a.n = n;
            return a;
        }    public static int f(F a)
        {
            return -a.n;
        }    public override bool Equals(object obj)
        {
            F a = obj as F;
            if (a == null) return false;
            return n.Equals(a.n);
        }    public override int GetHashCode()
        {
            return n.GetHashCode();
        }    public override string ToString()
        {
            return n.ToString();
        }    public static implicit operator int(F a)
        {
            return a.n;
        }    public static void Main()
        {
            foreach (int n in new int[] { 0, 1, 2, 3, 4, 1000, 1001, -1, -2, -3, -4, -1000, -1001, int.MaxValue - 1, int.MinValue + 1, int.MaxValue, int.MinValue })
            {
                Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
                Console.Write((long)n == (long)-(f(f(n))) ? "OK" : "ERROR");
                Console.WriteLine();
            }
        }
    }
      

  12.   

    既然是程序方面的技术题，个人想到的一个解法：
    闭包，closure，这是计算机科学中一个很通用的概念，很多编程语言都有不同程度的支持
    在C++中叫函数对象，functor，个人的理解从某种程度来说就是有状态的函数，不知道C#中有没有类似的行为
    以下是简单的示例代码，可能有语法错误，但不影响想表达的内容class foo {
      unsigned int i;
    public:
      foo(): i(0) {} // 构造函数将i置0
      int operator()(int n) // 重载()运算符，即函数对象的必要条件
      {
        if (i++ % 2) // 根据内部i的状态，调用()时一次不变，一次取相反数，最后的效果总是两次调用会取相反数
          return n;
        else
          return -n;
      }
    };foo f;
    int x;
    f(f(x)) == -x;
      

  13.   

    请注意，6楼的说法是如果自变量和返回值都是int：
    要是这样换一种思路的话：
    那还不如用5楼的 long f(long n) 的方案。
      

  14.   

    写了个比较弱的,int.MinValue处理起来会有问题,不过也在所难免了,
    另外判断用的比较多,感觉是可以通过位运算解决的!
    using System;public class program
    {
        private static void Main()
        {        foreach (int n in new int[] { 0, 1, 2, 3, 4, 1000, 1001, -1, -2, -3, -4, -1000, -1001, int.MaxValue - 1, int.MinValue + 1, int.MaxValue, int.MinValue })
            {
                Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
                Console.Write((long)n == -(long)(f(f(n))) ? "OK" : "ERROR");
                Console.WriteLine();
            }
        }    static int f(int m)
        {
            if (m < unchecked((int)0xC0000000))
                return (m + 0x40000000) * -1;
            else if (m < 0)
                return m - 0x40000000;
            else if (m < 0x40000000)
                return m + 0x40000000;
            else
                return (m - 0x40000000) * -1;
        }
    }
      

  15.   

    51楼的还是有2个值ERROR：0x40000000 和 int.MinValue 
    using System;class Program
    {
      static void Main()
      {
        foreach (int n in new int[] { 0x40000000, int.MinValue })
        {
          Console.Write("n = {0,-12} f(n) = {1,-12} f(f(n)) = {2,-12} ", n, f(n), f(f(n)));
          Console.Write((long)f(f(n)) == -(long)n ? "OK" : "ERROR");
          Console.WriteLine();
        }
      }
      
      static int f(int m)
      {
        if (m < unchecked((int)0xC0000000)) return (m + 0x40000000) * -1;
        if (m < 0) return m - 0x40000000;
        if (m < 0x40000000) return m + 0x40000000;
        return (m - 0x40000000) * -1;
      }
    }
    /* 程序输出：
    n = 1073741824   f(n) = 0            f(f(n)) = 1073741824   ERROR
    n = -2147483648  f(n) = 1073741824   f(f(n)) = 0            ERROR
    */
      

  16.   

    稍微分析了一下，总觉得会有一个数值无法实现，分析如下：
    1、按条件f(f(n))= (-n)分解，假设一个起始数值a,有f(a)可推出中间数值b，再由中间数值b带入函数f(b)推出f(f(a))的结果-a，即a->f(a)->b->f(b)->（-a）；
    2、由于b也是有效输入数值的一个，因此上式a->f(a)->b->f(b)->（-a）应可从b值按下划线所示继续向下推导得到a->f(a)->b->f(b)->（-a）->f(-a)->(-b)；
    3、同理，再由式中-a起始推导，最终得到a->f(a)->b->f(b)->（-a）->f(-a)->(-b)->f(-b)->a；
    4、这样a、b形成了一个闭环，也就是说符合如上算式的a、b组合可以符合条件f(f(n))= (-n)；
    5、2^32个数中，两两成对可有2^31对，但由于0=-0，因此0的a和b都是0，因此还会余下一个数值无法成对也无法和自己成对；
    对这类数学分析的东西不是很在行，大家看看这个分析有没有问题。。42楼说的东西看不大明白，希望能详细说说；
      

  17.   

    请大家到此继续讨论：挑战 f(f(n)) = -n
    http://topic.csdn.net/u/20090526/15/d9c9bea3-5dfb-4d72-b7cd-69d88f6430b8.html
      

  18.   


    很强，学习了。分析了一下，之所以在边界处会出现错误的情况，是因为操作中发生了溢出，把函数声明为long f(long n)就可以了，因为题目并没有给出f(n)的参数类型和返回值类型，所以是可以的。同理，int f(int n)适用于short,sbyte.顺便把位操作复习了一下
    -m = ~m + 1
    -m = ~(m - 1)
      

  19.   

    对所有负数都成立using System;
    using System.Collections.Generic;
    using System.Text;namespace ConsoleApplication1
    {
        class Program
        {
            static void Main(string[] args)
            {
                Console.WriteLine("n:-2 f(n):"+f(-2).ToString()+" f(f(n)):"+f(f(-2)).ToString());
                Console.WriteLine("n:-10 f(n):" + f(-10).ToString() + " f(f(n)):" + f(f(-10)).ToString());
                Console.WriteLine("n:-310 f(n):" + f(-310).ToString() + " f(f(n)):" + f(f(-310)).ToString());
                Console.WriteLine("n:-60 f(n):" + f(-60).ToString() + " f(f(n)):" + f(f(-60)).ToString());
                Console.WriteLine("n:-70 f(n):" + f(-70).ToString() + " f(f(n)):" + f(f(-70)).ToString());
                Console.WriteLine("n:-3 f(n):" + f(-3).ToString() + " f(f(n)):" + f(f(-3)).ToString());
                Console.Read();
            }        static int f(int n)
            {            return -n >> 16 | n << 16 ;
            }
        }
    }
      

  20.   


    对 -100000 不成立：
    n = -100000      f(n) = 2036334593   f(f(n)) = -31073       ERROR
      

  21.   

    小弟不才，这样想：
    当f奇数次作用n时，返回其本身（或其相反数）；
    当f偶数次作用n时，返回其相反数身（或其本身）；
    从而，问题转化为：
    确定f对n作用的次数的奇偶性，可以用静态变量表示。  static boolean a[4294967295];//默认值为false或赋值为true
    static tiny f(tiny n)
      {
    int m=n+2147483648;
    if(a[m]){a[m]=false;return -n;}
    else {a[m]=true;return n;}
      }
      

  22.   

    小弟不才，这样想： 
    当f奇数次作用n时，返回其本身（或其相反数）； 
    当f偶数次作用n时，返回其相反数身（或其本身）； 你是可以这样想，但程序未必会这样做。
    如果你用数学公司简单的推导下就知道错了！
    既然f(n) = n,那么
    ff(n) = -n，而f(n)= n，一替换就不行了。