Una función tal que $f(f(n)) = -n$?

Question

Esta pregunta de alguien de la entrevista de trabajo me hizo perplejo:

Diseño de una función f, tal que:

$f(f(n)) = -n$ ,

donde n es un entero con signo de 32 bits, usted no puede utilizar los números complejos de la aritmética. Si usted no puede diseñar una función para toda la gama de números, el diseño para la gama más amplia posible.

¿Tiene usted alguna idea de cómo hacer frente a?

EDIT: he quitado "número Real" en el título, ya que sólo se confunde a los lectores, pero que estaba destinado sólo para el estrés que los números complejos no están permitidos.

Answer 1

Me gustaría probar a explotar números pares e impares. De alguna manera, la necesidad de dos etapas de asignación y por lo tanto dos subconjuntos de los números enteros. Por ejemplo, $f$ mapa de los números impares a los números, y los números pares a impares números con signo opuesto. Como este:

$$\color{color gris}{f(n)=\begin{cases}0 & n= 0\\ 2n & n\in\text{odd}\\ -n/2 & n\in\text{even} \end{casos}}$$

EDIT: A major brain leak from my part, $n/a 2$ can stay even, so this doesn't work. However, the idea is sound, and the next one is actually valid.

You can construct a function that doesn't have this problem. Instead of messing up the entire range, you can select the smallest possible subset that has the property $f^2(n)=-n$. The smallest subset is $4$ numbers, because $f^4(n)=n$. You can for instance do something like this

$$f: n_{odd}\mapsto (n+1)_{even} \mapsto (-n)_{odd} \mapsto {-(n+1)}_{even}\mapsto n_{odd}$$

Así que si usted comienza con, incluso, de inicio en la segunda etapa. Prueba:

0 -> 0
1 -> 2 -> -1 -> -2
2 -> -1 -> -2 -> 1
3 -> 4 -> -3 -> -4
4 -> -3 -> -4 -> 3

y así sucesivamente.

O como una función $$f(n)=\begin{cases}0 & n= 0\\ n+1 & n\in\text{odd}^+\\ -n+1 & n\in\text{even}^+\\ n-1 & n\in\text{odd}^-\\ -n-1 & n\in\text{even}^- \end{cases}$$

This procedure does overflow, but only for the very last number in the range. However, at the end of the range you have bigger problem ($-2^{31}$ exists but $2^{31}-1$ is the top of the range so there's a number without its negative). There are $3$ problematic numbers: $-2^{31}$ without its negative, and $\pm(2^{31}-1)$ that can't be a part of a cycle of $4$ numbers, because $0$ is already taken.

There's actually no way of fixing this last issue, because the problem comes from the size of the set not being a multiple of $4$ after you exclude the zero for its special property $0=-0$. La solución que me dan es por lo tanto la óptima.

Answer 2

Me recuerda un rompecabezas de la matemáticas que va así:

Dos matemáticos se encuentren en esa terrible reino donde el rey mata a menos que se realice algún mundano lógica de la tarea. No te muevas de ahí, es horrible.

Nuestros héroes deben voltear una moneda cada día, y al menos uno de ellos debe adivinar correctamente la del otro tipo de moneda o que ambos mueren. Naturalmente, ellos son capaces de vivir para siempre el uso de un pequeño truco (verdugos odio!)

¿Qué hacen ellos? Además, tienen una chico de adivinar lo que él le da, y el otro siempre adivinar lo que él no voltear. Así que si terminan volteando la misma cosa, el hombre que adivina mismo será correcta. Si terminan volteando el diferente, el otro chico va a ser la correcta.

Voy a emplear la lógica que se utiliza para resolver este rompecabezas para resolver nuestros rompecabezas de aquí.

Básicamente, vamos a usar el bit más significativo en la entero para almacenar si necesitamos o no para voltear signos. Es posible que cualquier bit iba a hacer, pero el MSB es el menos perjudicial para el número de que llegar a tener para el sacrificio. Estoy bastante seguro de que no, pero no puedo descartar.

Digamos que A es nuestra bit más significativo, y S es nuestra bit de signo. El resto de los bits de determinar la magnitud de N (Como ya he dicho, todavía no han concluido si el A bits puede ser incluido en la magnitud, o si tenemos que sacrificar un poco de la "utilidad" de cara a la magnitud con el fin de servir como almacenamiento de datos sobre la etapa de la operación).

Esto le da 4 tipos de números:

S A
0 0 : N is a "small" positive number, perhaps 0.
0 1 : N is a "large" positive number
1 1 : N is a "small" negative number, perhaps -1
1 0 : N is a "large" negative number

Para cualquier número x (positivo o negativo), negando que la serie en general invierte tanto el bit S y el Un poco, a excepción de los especiales valores 0 y "el extraño número".

Podemos hacer esto con cualquier número de bits, por lo que para este ejemplo vamos a utilizar 8 bits de los números.

Nuestros 8 bits número será de 53, o 0b 0011 0101. Nuestra misión será la de convertir esto en -53, o 1100 1011

Ahora ya estamos usando 1 bit para el signo, y 1 bit para nuestros propios fines, el rango de esta función tiene es de sólo 6 bits (a menos que realmente se mantiene para todos los 7 bits, no he probado esa condición).

La función opera de esta manera:

si A == S, flip A.

otra cosa voltear Una y luego se multiplica por el valor negativo 1.

Por lo F(0b 0011 0101) = 0b 0111 0101. Cuando nos pasa esto a través de la función de nuevo, A ya no igual S. Así llega a la cláusula else, darle la vuelta a la A bits (de vuelta a 53) y multiplicando por negativo 1.

Otro ejemplo, comenzando con -53 == 0b 1100 1011:

F(0b 1100 1011) == 0b 1000 1011

A continuación, F(0b 1000 1011) de aciertos de la cláusula else, orientando el Un poco para conseguir 0b 1100 1011 == -53, y, a continuación, negando el número para obtener +53 == 0b 0011 0101.

Así que la idea es que nos estamos sacrificando la A bits para los fines de F(x) porque se debe obtener invierte cuando se ejecute el resultado a través de F de nuevo. Tenga en cuenta que F(x) por sí mismo no es particularmente útil función. También que esto puede no funcionar para los casos extremos (yo no lo he probado mucho. 0, MAX_VALUE, MIN_VALUE, y de -1 a todos los que vienen a la mente como casos de prueba.)

Answer 3

Esta respuesta a una pregunta relacionada con los suministros de los análisis pertinentes.

Suponiendo que un "firmado entero de 32 bits" significa que usted está considerando el dominio y el rango de $f$ a los enteros en el intervalo de $[-2^{31}, 2^{31})$, una cuenta simple argumento muestra que la mayor dominio en el que la identidad de $f(f(x))=-x$ puede sostener debe faltar al menos tres puntos.

(aparte: $-2^{31}$ debe ser excluido, porque está fuera del dominio de unario de negación. La parte interesante es que debemos excluir otros dos puntos también)

La función de ejemplo de que la respuesta puede ser utilizado:

$$ f(x) = \begin{cases} 0 & x == 0 \\ x+1 & x>0 \wedge \text{%#%#% is odd} \\ 1-x & x>0 \wedge \text{%#%#% is even} \\ x-1 & x<0 \wedge \text{%#%#% is odd} \\ -1-x & x<0 \wedge \text{%#%#% is even} \end{casos} $$

que tiene la propiedad deseada en $x$.

No voy a discutir la implementación de una solución con poco cambiando: este tema está más allá del alcance de este foro.

---

EDIT: si por el contrario nos desea que el dominio de $x$ a ser el todo el intervalo, podemos hacer que la identidad de sostener para un punto más. Si tenemos una función de $x$ da como arriba, y dejar los tres puntos que están excluidos de ser $x$, $[-2^{31} + 2, 2^{31} - 2]$, y $f$, entonces podemos extender $f$ mediante el establecimiento de

• $a$
• $-a$
• $2^{-31}$ nada

y así, con esta extensión, $f$.

Answer 4

En primer lugar, desde una perspectiva de programación, usted debe aclarar cuál es la función de los medios. Una función pura (que es también el mathemtical sentido) no tiene efectos secundarios; no de los lenguajes funcionales pueden tener funciones con efectos secundarios, y para los idiomas, algo como:

state = -1
def f(n):
   global state
   state = state * -1
   return n * state

se cumple con el requisito. De lo contrario, usted necesita una manera de codificar el estado en el intermedio de retorno. Dado un valor de 32 bits de entrada (y suponiendo que el rango es de -2^31 2^31-1), necesitamos el apoyo de 33 bits para el intermedio (es decir, la primera llamada a f). Esto es por dos razones... una de ellas es almacenar el estado (si esta es la primera o la 2ª convocatoria a f), y el segundo es para manejar n=-2^31 (que no puede ser expresado en 32 bits usando el estándar de complemento a 2 firmado codificación). En lugar de confundir las cosas por el tratamiento de la MSB o otro poco como el estado de la bandera, me parece que es más fácil usar una estructura (si se me fue la codificación en C y realmente preocupado por el espacio, yo podría tratar de usar los campos de bits, pero esta sería una exageración y que probablemente no sea útil, porque de relleno). De todos modos: struct mystruct { unsigned int estado:1; signed int valor; } Para f, si el estado es 1, esto indica que esta es la segunda vez que esto ha sido llamado, así que el regreso de valor; si el estado el estado es 0, esta es la primera vez, así que el regreso de estado=1, valor

(Pregunta me di cuenta de que debería haber preguntado... ¿f(f(f(f(n)))) necesidad de volver n?

Answer 5

Si $n$ puede admitir cualquier número real, entonces podríamos definir $f(n)$ como:

$$f(n)=\begin{cases} \sqrt2n & n\in\mathbb{Q}\\ -n/\sqrt{2} & n\not\in\mathbb{Q} \end{casos}$$

Luego, a continuación, $f(f(n)) = -n$ para todos los números racionales $n$, incluyendo a $0$.

---

Si $n$ admite sólo de 32 bits con signo de argumentos y números de punto flotante se permite, entonces:

$$f(n)=\begin{cases} n + 0.5 & \lfloor{n}\rfloor = n\\ -n - 0.5 & \lfloor{n}\rfloor \not= n \end{casos}$$