7 ms·
If you want to quickly understand the answers, the key insight is here: http://stackoverflow.com/a/824878 http://stackoverflow.com/a/824878 Paraphrased: defin
by uvdiv 13y ago
If you want to quickly understand the answers, the key insight is here:
http://stackoverflow.com/a/824878 http://stackoverflow.com/a/824878
Paraphrased: defining such a function over a symmetric subset of the reals X is equivalent to partitioning the positive (>0) elements of X into disjoint pairs (a,b). This uniquely describes a satisfying function f, under whose action:
f: 0 -> 0
f: a -> (-b) -> (-a) -> b -> a
And conversely, any such function is uniquely described by such a partition. That's all there is to it!
There is no such partition on the set of int32_t's, because the # of nonzero int32_t's is odd.
For the set of all integers Z, the "obvious" partition is {(1,2), (3,4), (5,6)...}. This is what many of the answers are getting at with even/odd tests.
This also works for some subsets of the integers, such as {-2,1,0,1,2}. These are the symmetric ones with an even number of positive elements. These have 4n or 4n+1 elements total, depending on whether they include zero. [-2^31, 2^31] works (this has one more element than int32_t). As does [-2^31 + 2, 2^31 - 2] -- the largest such subset of int32_t.
This has a natural extension to the rationals, the reals, etc. Namely: (a,b) is a member of the partition iff (floor(a), floor(b)) is a member of the partition for integers, and their fractional parts are equal.
There is no such function on the reals that is (analytically) continuous. Any such f must be bijective (a != b implies f(a) != f(b)). If f : R -> R is both continuous and bijective, it is monotonic, and therefore so is (f . f), which is incompatible with the requirement that (f . f)(x) = -x.
- zura 13y agoTo say in simpler words, regarding implementation - the main trick is to "store" the flag in the argument itself. It is a quite common trick, I'd say.
- ape4 13y agoOr doing something outside the box. Some people used static variables. How about looking at the call stack. If f() is invoked by f() do one thing, if you aren't do something else.
- danbruc 13y agoThe best you can do is getting all but one number (2^n - 1) correct.
- deleted 13y ago[deleted]
- anonymous 13y agoUnfortunately no, 0 also can't be handled. The chains are 1 -> 2 -> -1 -> -2 -> 1 3 -> 4 -> -3 -> -4 -> 3 .... 2^31 - 3 -> 2^31 - 2 -> -2^31 + 3 -> -2^31 + 2 -> 2^31 - 3 And now you're left with just 2^31 - 1, -2^31, -2^31 + 1, 0. If you define f(f(0)) = 0, then you have only 3 numbers and you need 4 for a chain. Possible solutions: * f(f(0)) = -2^31 * crash on any of the 3 * crash violently * enter an endless loop (technically if the function never completes, it doesn't return a wrong value)
- colanderman 13y agoAnd now you're left with just 2^31 - 1, -2^31, -2^31 + 1, 0. If you define f(f(0)) = 0, then you have only 3 numbers and you need 4 for a chain. The parent of your post explicitly said: all but one number (2^n - 1) correct.
- danbruc 13y agoHere the example for 3 bits. 0 -> 0 +1 -> -2 -> -1 -> +2 -> +1 +3 -> -4 -> -3 -> -4 The first cycle takes care of 0, the second one of -2, -1, +1 and +2. The interesting thing is the third thing - it consists of the cycle -4 -> -3 -> -4 and the attached chain +3 -> -4 entering the cycle via -4. This one correctly maps +3 to -3 and -4 to -4 (-(2^(n - 1) is its on inverse) and only fails for -3 which is incorrectly mapped to itself, too. There you go, 7 out of 8 correct. (This is the essence of my way longer answer on Stack Overflow [1] although it is not necessarily any clearer because it evolved a lot.) [1] http://stackoverflow.com/a/731857 http://stackoverflow.com/a/731857