〖转贴〗技术面试题：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.
[解决办法]
- C# code
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 OKn = 1 f(n) = 2 f(f(n)) = -1 OKn = 2 f(n) = -1 f(f(n)) = -2 OKn = 3 f(n) = 4 f(f(n)) = -3 OKn = 4 f(n) = -3 f(f(n)) = -4 OKn = 1000 f(n) = -999 f(f(n)) = -1000 OKn = 1001 f(n) = 1002 f(f(n)) = -1001 OKn = -1 f(n) = -2 f(f(n)) = 1 OKn = -2 f(n) = 1 f(f(n)) = 2 OKn = -3 f(n) = -4 f(f(n)) = 3 OKn = -4 f(n) = 3 f(f(n)) = 4 OKn = -1000 f(n) = 999 f(f(n)) = 1000 OKn = -1001 f(n) = -1002 f(f(n)) = 1001 OKn = 2147483646 f(n) = -2147483645 f(f(n)) = -2147483646 OKn = -2147483647 f(n) = -2147483648 f(f(n)) = 2147483647 OKn = 2147483647 f(n) = 2147483648 f(f(n)) = -2147483647 OKn = -2147483648 f(n) = 2147483647 f(f(n)) = 2147483648 OK*/
[解决办法]
如果函数原形要求是：int f(int n)，也就是自变量和返回值都是int，
则有两个值是错的：int.MinValue 和 int.MaxValue，
不知能不能减少到一个值。
- C# code
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 OKn = 1 f(n) = 2 f(f(n)) = -1 OKn = 2 f(n) = -1 f(f(n)) = -2 OKn = 3 f(n) = 4 f(f(n)) = -3 OKn = 4 f(n) = -3 f(f(n)) = -4 OKn = 1000 f(n) = -999 f(f(n)) = -1000 OKn = 1001 f(n) = 1002 f(f(n)) = -1001 OKn = -1 f(n) = -2 f(f(n)) = 1 OKn = -2 f(n) = 1 f(f(n)) = 2 OKn = -3 f(n) = -4 f(f(n)) = 3 OKn = -4 f(n) = 3 f(f(n)) = 4 OKn = -1000 f(n) = 999 f(f(n)) = 1000 OKn = -1001 f(n) = -1002 f(f(n)) = 1001 OKn = 2147483646 f(n) = -2147483645 f(f(n)) = -2147483646 OKn = -2147483647 f(n) = -2147483648 f(f(n)) = 2147483647 OKn = 2147483647 f(n) = -2147483648 f(f(n)) = 2147483647 ERRORn = -2147483648 f(n) = 2147483647 f(f(n)) = -2147483648 ERROR*/
[解决办法]
写了一个，貌似可以实现，大家试试：
- C# code
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;}
[解决办法]
这样，还是两个值ERROR:
- C# code
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 ERRORn = 0 f(n) = -2147483647 f(f(n)) = -2147483648 ERRORn = 1 f(n) = 2 f(f(n)) = -1 OKn = 2 f(n) = -1 f(f(n)) = -2 OKn = 3 f(n) = 4 f(f(n)) = -3 OKn = 2147483646 f(n) = -2147483645 f(f(n)) = -2147483646 OKn = 2147483647 f(n) = 0 f(f(n)) = -2147483647 OKn = -1 f(n) = -2 f(f(n)) = 1 OKn = -2 f(n) = 1 f(f(n)) = 2 OKn = -3 f(n) = -4 f(f(n)) = 3 OKn = -2147483646 f(n) = 2147483645 f(f(n)) = 2147483646 OKn = -2147483647 f(n) = -2147483648 f(f(n)) = 2147483647 OK*/