devise函数f（f（n））== -n
我在上次访谈中遇到了一个问题：
devise一个函数
f，使得：f(f(n)) == -n其中
n是一个32位有符号整数 ; 你不能使用复数算术。如果你不能为整个数字范围devise这样的function，那么可以devise一个最大的范围。
有任何想法吗？
怎么样：
f（n）= sign（n） - （ - 1） n * n
在Python中：
def f(n): if n == 0: return 0 if n >= 0: if n % 2 == 1: return n + 1 else: return -1 * (n - 1) else: if n % 2 == 1: return n - 1 else: return -1 * (n + 1)
Python会自动将整数提升为任意长度。 在其他语言中，最大的正整数会溢出，所以除了那个之外，它将适用于所有整数。
要使它适用于实数， { ceiling(n) if n>0; floor(n) if n<0 }需要用{ ceiling(n) if n>0; floor(n) if n<0 }replace（-1） n中的 { ceiling(n) if n>0; floor(n) if n<0 } { ceiling(n) if n>0; floor(n) if n<0 } 。
在C＃（适用于任何双重，除溢出情况下）：
static double F(double n) { if (n == 0) return 0; if (n < 0) return ((long)Math.Ceiling(n) % 2 == 0) ? (n + 1) : (-1 * (n - 1)); else return ((long)Math.Floor(n) % 2 == 0) ? (n - 1) : (-1 * (n + 1)); }
你没有说他们期望什么样的语言…这是一个静态解决scheme（Haskell）。 它基本上与最重要的两个位相混淆：
f :: Int -> Int fx | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30 | otherwise = complementBit x 30
dynamic语言（Python）更容易。 只要检查参数是否为数字X并返回一个返回-X的lambda：
def f(x): if isinstance(x,int): return (lambda: -x) else: return x()
这里有一个certificate，为什么这样的函数不能存在，所有的数字，如果它不使用额外的信息（除32位int）：
（certificate：假设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); } }
当然，另外一个select就是不遵守0，并把我们移除的2个数字作为奖金。 （但是，这只是一个愚蠢的。）
感谢在C ++中重载：
double f(int var) { return double(var); } int f(double var) { return -int(var); } int main(){ int n(42); std::cout<<f(f(n)); }
或者，你可能会滥用预处理器：
#define f(n) (f##n) #define ff(n) -n int main() { int n = -42; cout << "f(f(" << n << ")) = " << f(f(n)) << endl; }
所有负数都是如此。
f（n）= abs（n）
因为还有一个负数比二进制补码整数的正数要多，所以f(n) = abs(n)对于比f(n) = n > 0 ? -n : n多一个情况是有效的f(n) = n > 0 ? -n : n f(n) = n > 0 ? -n : n解决scheme与f(n) = -abs(n) 。 你有一个…：D
UPDATE
不，这是无效的一个更多的事情，因为我刚刚认识到莱布的评论… abs(Int.Min)只会溢出…
我也想过使用mod 2的信息，但是结论是，它并没有起作用。 如果正确的话，它将适用于除Int.Min之外的所有数字，因为这会溢出。
UPDATE
我玩了一段时间，寻找一个很好的操作技巧，但我找不到一个很好的单线，而模2解决scheme适合于一个。
f（n）= 2n（abs（n）％2） - n + sgn（n）
在C＃中，这成为以下内容：
public static Int32 f(Int32 n) { return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n); }
为了使它适用于所有的值，你必须用(n > 0) ? +n : -nreplaceMath.Abs() (n > 0) ? +n : -n (n > 0) ? +n : -n并将计算包括在unchecked块中。 然后你甚至得到Int.Min映射到自己作为unchecked否定做。
UPDATE
受到另一个答案的启发，我将解释这个函数是如何工作的，以及如何构造这样一个函数。
让我们从一开始就开始。 函数f被重复应用到一个给定值n产生一系列值。
（f（n））=> f（f（n））=> f（f（n））=> ...
这个问题要求f(f(n)) = -n ，这是f两个连续应用否定论证。 f – 四的另外两个应用 – 再次否定了这个论点再次产生n 。
n => f（n）=> -n => f（f（f（n）））=> n => f（n）=> ...
现在有一个明显的周期长度四。 代入x = f(n)并注意到所得到的方程f(f(f(n))) = f(f(x)) = -x成立。
n => x => -n => -x => n => ...
所以我们得到一个长度为四的两个数字的循环，并且这两个数字被否定。 如果将周期想象成一个矩形，否定值位于对angular处。
构build这样一个循环的许多解决scheme之一是从n开始的。
n =>否定和减去一个 -n - 1 = - （n + 1）=>加一个 -n =>否定并添加一个 n + 1 =>减1 ñ
一个具体的例子是这样一个循环是+1 => -2 => -1 => +2 => +1 。 我们差不多完成了。 注意到所构造的循环包含一个奇数的正数，它的偶数的后继数，并且两个数都是否定的，我们可以很容易地将整数分成许多这样的循环（ 2^32是四的倍数），并且find了一个满足条件的函数。
但是我们有一个零的问题。 循环必须包含0 => x => 0因为零自身是否定的。 并且因为循环状态已经是0 => x所以0 => x => 0 => x 。 这只是一个长度为2的循环，在两个应用程序之后x变成自己，而不是变成-x 。 幸运的是有一个案例解决了这个问题。 如果X等于零，我们得到一个只包含零的长度的周期，我们解决了这个问题，得出结论：零是f一个固定点。
完成了吗？ 几乎。 我们有2^32数字，零是一个固定的点，剩下2^32 - 1数字，我们必须把这个数字分成四个数字的循环。 不好的， 2^32 - 1不是4的倍数 – 在任何长度为4的周期内都会有三个数字。
我将使用范围从-4到+3的较小的一组3位有符号迭代器来解释解决scheme的其余部分。 我们完成了零。 我们有一个完整的周期+1 => -2 => -1 => +2 => +1 。 现在我们来构build从+3开始的循环。
+3 => -4 => -3 => +4 => +3
出现的问题是+4不能表示为3位整数。 我们通过将-3减去-3得到+4 – 仍然是有效的3比特整数 – 但是然后将+1加到+3 （二进制011 ）产生100二进制。 解释为无符号整数是+4但我们必须解释为有符号整数-4 。 所以实际上-4这个例子或Int.MinValue在一般情况下是整数运算否定的第二个不动点 – 0和Int.MinValue映射到themselve。 所以周期实际上如下。
+3 => -4 => -3 => -4 => -3
它是一个长度为2的循环，另外+3通过-4进入循环。 结果-4在两个函数应用之后被正确地映射到自身，在两个函数应用之后+3被正确地映射到-3 ，但是在两个函数应用之后-3被错误地映射到自身。
所以我们构造了一个适用于所有整数的函数。 我们可以做得更好吗？ 不，我们不可以。 为什么？ 我们必须构造长度为四的周期，并且能够覆盖整个整数范围最多四个值。 剩下的值是两个必须映射到自身的固定点0和Int.MinValue以及必须由两个函数应用程序相互映射的两个任意整数x和-x 。
要将x映射到-x ，反之亦然，它们必须形成一个四周期，并且它们必须位于该周期的对angular。 结果0和Int.MinValue也必须在相反的angular落。 这将正确映射x和-x但在两个函数应用程序之后交换两个固定点0和Int.MinValue ，并给我们留下两个失败的input。 所以不可能构build一个适用于所有值的函数，但是除了一个值之外，我们有一个适用于所有值的函数，这是我们可以实现的最好的。
使用复数，可以有效地将否定数字的任务分成两步：
- 把n乘以i，得到n * i，逆时针旋转90°
- 再乘以我，你会得到-n
最棒的是你不需要任何特殊的处理代码。 只要乘以我做的工作。
但是你不能使用复数。 所以你必须以某种方式创build你自己的虚轴，使用你的数据范围的一部分。 由于您需要与初始值完全相同的虚数（中间值），因此只剩下一半的数据范围。
我试图在下图中看到它，假设有8位数据。 你将不得不按比例缩放32位整数。 初始n的允许范围是-64到+63。 这是函数为正值n所做的：
- 如果n在0..63（初始范围）内，则函数调用将添加64，将n映射到范围64..127（中间范围）
- 如果n在64..127（中间范围）中，则函数从64中减去n，将n映射到范围0 ..- 63
对于负数n，该函数使用中间范围-65 ..- 128。
除了int.MaxValue和int.MinValue
public static int f(int x) { if (x == 0) return 0; if ((x % 2) != 0) return x * -1 + (-1 *x) / (Math.Abs(x)); else return x - x / (Math.Abs(x)); }
这个问题没有说什么函数f的inputtypes和返回值必须是什么 （至less不是你提供的方式）…
…只是当n是一个32位整数，那么f(f(n)) = -n
那么，怎么样？
Int64 f(Int64 n) { return(n > Int32.MaxValue ? -(n - 4L * Int32.MaxValue): n + 4L * Int32.MaxValue); }
如果n是一个32位整数，那么语句f(f(n)) == -n将为真。
显然，这种方法可以扩展到更广泛的数字范围。
对于JavaScript（或其他dynamictypes的语言），您可以让该函数接受一个int或一个对象，并返回另一个。 即
function f(n) { if (n.passed) { return -n.val; } else { return {val:n, passed:1}; } }
给
js> f(f(10)) -10 js> f(f(-10)) 10
或者你可以使用强types语言重载，尽pipe这可能会违反规则
int f(long n) { return n; } long f(int n) { return -n; }
取决于你的平台，一些语言允许你保持状态的function。 VB.Net，例如：
Function f(ByVal n As Integer) As Integer Static flag As Integer = -1 flag *= -1 Return n * flag End Function
IIRC，C ++也允许这样做。 我怀疑他们正在寻找一个不同的解决scheme。
另一个想法是，因为他们没有定义第一次调用函数的结果，你可以使用奇数/偶数来控制是否反转符号：
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，从所有奇数的数量中减1。 两次通话的结果有相同的幅度，但是我们换了标志的那个叫。 有些情况下，这将不起作用（-1，最大或最小诠释），但它比迄今为止build议的任何其他更好。
利用JavaScriptexception。
function f(n) { try { return n(); } catch(e) { return function() { return -n; }; } }
f(f(0)) => 0
f(f(1)) => -1
对于所有的32位值（注意-0是-2147483648）
int rotate(int x) { static const int split = INT_MAX / 2 + 1; static const int negativeSplit = INT_MIN / 2 + 1; if (x == INT_MAX) return INT_MIN; if (x == INT_MIN) return x + 1; if (x >= split) return x + 1 - INT_MIN; if (x >= 0) return INT_MAX - x; if (x >= negativeSplit) return INT_MIN - x + 1; return split -(negativeSplit - x); }
你基本上需要将每个-x => x => -x循环与ay => -y => y循环配对。 所以我配对了split对面。
例如对于4位整数：
0 => 7 => -8 => -7 => 0 1 => 6 => -1 => -6 => 1 2 => 5 => -2 => -5 => 2 3 => 4 => -3 => -4 => 3
一个C ++版本，可能会在一定程度上弯曲规则，但适用于所有数值types（浮点数，整数，双精度），甚至超过一元减去的类types：
template <class T> struct f_result { T value; }; template <class T> f_result <T> f (T n) { f_result <T> result = {n}; return result; } template <class T> T f (f_result <T> n) { return -n.value; } void main (void) { int n = 45; cout << "f(f(" << n << ")) = " << f(f(n)) << endl; float p = 3.14f; cout << "f(f(" << p << ")) = " << f(f(p)) << endl; }
x86 asm（AT＆T风格）：
; input %edi ; output %eax ; clobbered regs: %ecx, %edx f: testl %edi, %edi je .zero movl %edi, %eax movl $1, %ecx movl %edi, %edx andl $1, %eax addl %eax, %eax subl %eax, %ecx xorl %eax, %eax testl %edi, %edi setg %al shrl $31, %edx subl %edx, %eax imull %ecx, %eax subl %eax, %edi movl %edi, %eax imull %ecx, %eax .zero: xorl %eax, %eax ret
代码检查，所有可能的32位整数通过，错误-2147483647（下溢）。
使用全局variables…但是呢？
bool done = false f(int n) { int out = n; if(!done) { out = n * -1; done = true; } return out; }
这个Perl解决scheme适用于整数，浮点数和string 。
sub f { my $n = shift; return ref($n) ? -$$n : \$n; }
尝试一些testing数据。
print $_, ' ', f(f($_)), "\n" for -2, 0, 1, 1.1, -3.3, 'foo' '-bar';
输出：
-2 2 0 0 1 -1 1.1 -1.1 -3.3 3.3 foo -foo -bar +bar
没有人说f（x）必须是相同的types。
def f(x): if type(x) == list: return -x[0] return [x] f(2) => [2] f(f(2)) => -2
我会改变2个最重要的位。
00.... => 01.... => 10..... 01.... => 10.... => 11..... 10.... => 11.... => 00..... 11.... => 00.... => 01.....
正如你所看到的，这只是一个补充，省略了进位。
我怎么得到答案？ 我的第一个想法只是对称的需要。 4转回到我开始的地方。 起初我想，这是2位格雷码。 然后我认为其实标准二进制就足够了。
I'm not actually trying to give a solution to the problem itself, but do have a couple of comments, as the question states this problem was posed was part of a (job?) interview:
- I would first ask "Why would such a function be needed? What is the bigger problem this is part of?" instead of trying to solve the actual posed problem on the spot. This shows how I think and how I tackle problems like this. Who know? That might even be the actual reason the question is asked in an interview in the first place. If the answer is "Never you mind, assume it's needed, and show me how you would design this function." I would then continue to do so.
- Then, I would write the C# test case code I would use (the obvious: loop from
int.MinValuetoint.MaxValue, and for eachnin that range callf(f(n))and checking the result is-n), telling I would then use Test Driven Development to get to such a function. - Only if the interviewer continues asking for me to solve the posed problem would I actually start to try and scribble pseudocode during the interview itself to try and get to some sort of an answer. However, I don't really think I would be jumping to take the job if the interviewer would be any indication of what the company is like…
Oh, this answer assumes the interview was for a C# programming related position. Would of course be a silly answer if the interview was for a math related position. 😉
Here is a solution that is inspired by the requirement or claim that complex numbers can not be used to solve this problem.
Multiplying by the square root of -1 is an idea, that only seems to fail because -1 does not have a square root over the integers. But playing around with a program like mathematica gives for example the equation
(1849436465 2 +1) mod (2 32 -3) = 0.
and this is almost as good as having a square root of -1. The result of the function needs to be a signed integer. Hence I'm going to use a modified modulo operation mods(x,n) that returns the integer y congruent to x modulo n that is closest to 0. Only very few programming languages have suc a modulo operation, but it can easily be defined. Eg in python it is:
def mods(x, n): y = x % n if y > n/2: y-= n return y
Using the equation above, the problem can now be solved as
def f(x): return mods(x*1849436465, 2**32-3)
This satisfies f(f(x)) = -x for all integers in the range [-2 31 -2, 2 31 -2] . The results of f(x) are also in this range, but of course the computation would need 64-bit integers.
C# for a range of 2^32 – 1 numbers, all int32 numbers except (Int32.MinValue)
Func<int, int> f = n => n < 0 ? (n & (1 << 30)) == (1 << 30) ? (n ^ (1 << 30)) : - (n | (1 << 30)) : (n & (1 << 30)) == (1 << 30) ? -(n ^ (1 << 30)) : (n | (1 << 30)); Console.WriteLine(f(f(Int32.MinValue + 1))); // -2147483648 + 1 for (int i = -3; i <= 3 ; i++) Console.WriteLine(f(f(i))); Console.WriteLine(f(f(Int32.MaxValue))); // 2147483647
prints:
2147483647 3 2 1 0 -1 -2 -3 -2147483647
Essentially the function has to divide the available range into cycles of size 4, with -n at the opposite end of n's cycle. However, 0 must be part of a cycle of size 1, because otherwise 0->x->0->x != -x . Because of 0 being alone, there must be 3 other values in our range (whose size is a multiple of 4) not in a proper cycle with 4 elements.
I chose these extra weird values to be MIN_INT , MAX_INT , and MIN_INT+1 . Furthermore, MIN_INT+1 will map to MAX_INT correctly, but get stuck there and not map back. I think this is the best compromise, because it has the nice property of only the extreme values not working correctly. Also, it means it would work for all BigInts.
int f(int n): if n == 0 or n == MIN_INT or n == MAX_INT: return n return ((Math.abs(n) mod 2) * 2 - 1) * n + Math.sign(n)
Nobody said it had to be stateless.
int32 f(int32 x) { static bool idempotent = false; if (!idempotent) { idempotent = true; return -x; } else { return x; } }
Cheating, but not as much as a lot of the examples. Even more evil would be to peek up the stack to see if your caller's address is &f, but this is going to be more portable (although not thread safe… the thread-safe version would use TLS). Even more evil:
int32 f (int32 x) { static int32 answer = -x; return answer; }
Of course, neither of these works too well for the case of MIN_INT32, but there is precious little you can do about that unless you are allowed to return a wider type.
I could imagine using the 31st bit as an imaginary ( i ) bit would be an approach that would support half the total range.
works for n= [0 .. 2^31-1]
int f(int n) { if (n & (1 << 31)) // highest bit set? return -(n & ~(1 << 31)); // return negative of original n else return n | (1 << 31); // return n with highest bit set }
The problem states "32-bit signed integers" but doesn't specify whether they are twos-complement or ones-complement .
If you use ones-complement then all 2^32 values occur in cycles of length four – you don't need a special case for zero, and you also don't need conditionals.
In C:
int32_t f(int32_t x) { return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU; }
This works by
- Exchanging the high and low 16-bit blocks
- Inverting one of the blocks
After two passes we have the bitwise inverse of the original value. Which in ones-complement representation is equivalent to negation.
例子：
Pass | x -----+------------------- 0 | 00000001 (+1) 1 | 0001FFFF (+131071) 2 | FFFFFFFE (-1) 3 | FFFE0000 (-131071) 4 | 00000001 (+1) Pass | x -----+------------------- 0 | 00000000 (+0) 1 | 0000FFFF (+65535) 2 | FFFFFFFF (-0) 3 | FFFF0000 (-65535) 4 | 00000000 (+0)
：d
boolean inner = true; int f(int input) { if(inner) { inner = false; return input; } else { inner = true; return -input; } }
return x ^ ((x%2) ? 1 : -INT_MAX);
I'd like to share my point of view on this interesting problem as a mathematician. I think I have the most efficient solution.
If I remember correctly, you negate a signed 32-bit integer by just flipping the first bit. For example, if n = 1001 1101 1110 1011 1110 0000 1110 1010, then -n = 0001 1101 1110 1011 1110 0000 1110 1010.
So how do we define a function f that takes a signed 32-bit integer and returns another signed 32-bit integer with the property that taking f twice is the same as flipping the first bit?
Let me rephrase the question without mentioning arithmetic concepts like integers.
How do we define a function f that takes a sequence of zeros and ones of length 32 and returns a sequence of zeros and ones of the same length, with the property that taking f twice is the same as flipping the first bit?
Observation: If you can answer the above question for 32 bit case, then you can also answer for 64 bit case, 100 bit case, etc. You just apply f to the first 32 bit.
Now if you can answer the question for 2 bit case, Voila!
And yes it turns out that changing the first 2 bits is enough.
Here's the pseudo-code
1. take n, which is a signed 32-bit integer. 2. swap the first bit and the second bit. 3. flip the first bit. 4. return the result.
Remark: The step 2 and the step 3 together can be summerised as (a,b) –> (-b, a). Looks familiar? That should remind you of the 90 degree rotation of the plane and the multiplication by the squar root of -1.
If I just presented the pseudo-code alone without the long prelude, it would seem like a rabbit out of the hat, I wanted to explain how I got the solution.
