math - traduccion - whole numbers

Función de diseño f(f(n))==-n (30)

Aquí hay una prueba de por qué una función de este tipo no puede existir, para todos los números, si no usa información adicional (excepto 32 bits de int):

Debemos tener f (0) = 0. (Prueba: supongamos que f (0) = x. Luego f (x) = f (f (0)) = -0 = 0. Ahora, -x = f (f (x) )) = f (0) = x, lo que significa que x = 0.)

Además, para cualquier x e y , supongamos que f(x) = y . Queremos f(y) = -x entonces. Y f(f(y)) = -y => f(-x) = -y . Para resumir: si f(x) = y , entonces f(-x) = -y , y f(y) = -x , y f(-y) = x .

Por lo tanto, necesitamos dividir todos los enteros excepto 0 en conjuntos de 4, pero tenemos un número impar de tales enteros; no solo eso, si eliminamos el entero que no tiene una contraparte positiva, también tenemos 2 (mod4) números.

Si eliminamos los 2 números máximos restantes (por valor de abs), podemos obtener la función:

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); } }

Por supuesto, otra opción es no cumplir con 0 y obtener los 2 números que eliminamos como bonificación. (Pero eso es sólo una tontería si.)

Una pregunta que obtuve en mi última entrevista:

Diseñe una función f , tal que:
f(f(n)) == -n
Donde n es un entero con signo de 32 bits; No puedes usar aritmética de números complejos.
Si no puede diseñar una función de este tipo para toda la gama de números, diseñe para la mayor gama posible.

¿Algunas ideas?

Dependiendo de su plataforma, algunos idiomas le permiten mantener el estado en la función. VB.Net, por ejemplo:

Function f(ByVal n As Integer) As Integer Static flag As Integer = -1 flag *= -1 Return n * flag End Function

IIRC, C ++ permitió esto también. Sin embargo, sospecho que están buscando una solución diferente.

Otra idea es que, dado que no definieron el resultado de la primera llamada a la función, se podría usar impar / uniformidad para controlar si invertir el signo:

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; }

Suma uno a la magnitud de todos los números pares, resta uno de la magnitud de todos los números impares. El resultado de dos llamadas tiene la misma magnitud, pero la única llamada en la que incluso cambiamos el signo. Hay algunos casos en los que esto no funciona (-1, max o min int), pero funciona mucho mejor que cualquier otra cosa sugerida hasta ahora.

En realidad, no estoy tratando de dar una solución al problema en sí, pero tengo un par de comentarios, ya que la pregunta afirma que este problema fue parte de una entrevista (¿trabajo?):

Primero preguntaría "¿Por qué se necesitaría una función de este tipo? ¿Cuál es el problema más grande del que forma parte?" En lugar de tratar de resolver el problema planteado real en el lugar. Esto muestra cómo pienso y cómo enfrento problemas como este. ¿Quien sabe? Esa podría ser la razón real por la que se hace la pregunta en una entrevista en primer lugar. Si la respuesta es "No importa, suponga que es necesario y muéstrame cómo diseñaría esta función". Entonces continuaría haciéndolo.
Luego, escribiría el código de caso de prueba de C # que usaría (el obvio: bucle desde int.MinValue a int.MaxValue , y para cada n en ese rango, llame a f(f(n)) y verifique que el resultado sea -n ) , diciéndome que luego usaría Test Driven Development para llegar a esa función.
Solo si el entrevistador sigue pidiéndome que resuelva el problema planteado, realmente empezaría a intentar escribir pseudocódigo durante la entrevista para tratar de obtener algún tipo de respuesta. Sin embargo, realmente no creo que vaya a tomar el trabajo si el entrevistador sea un indicio de cómo es la compañía ...

Oh, esta respuesta asume que la entrevista fue para una posición relacionada con la programación de C #. Por supuesto, sería una respuesta tonta si la entrevista fuera para una posición relacionada con las matemáticas. ;-)

Esta solución de Perl funciona para enteros, flotadores y cadenas .

sub f { my $n = shift; return ref($n) ? -$$n : /$n; }

Pruebe algunos datos de prueba.

print $_, '' '', f(f($_)), "/n" for -2, 0, 1, 1.1, -3.3, ''foo'' ''-bar'';

Salida:

-2 2 0 0 1 -1 1.1 -1.1 -3.3 3.3 foo -foo -bar +bar

Esto es cierto para todos los números negativos.

f(n) = abs(n)

Debido a que hay un número negativo más que números positivos para dos enteros de complemento, f(n) = abs(n) es válido para un caso más que f(n) = n > 0 ? -n : n f(n) = n > 0 ? -n : n solución que es lo mismo que f(n) = -abs(n) . Te tengo por uno ...: d

ACTUALIZAR

No, no es válido para un caso más, como acabo de reconocer por el comentario de litb ... abs(Int.Min) simplemente se desbordará ...

Pensé en usar la información mod 2, también, pero concluí, no funciona ... demasiado pronto. Si se hace correctamente, funcionará para todos los números excepto para Int.Min porque se desbordará.

ACTUALIZAR

Jugué con él por un tiempo, buscando un buen truco de manipulación de bits, pero no pude encontrar una buena frase de una sola línea, mientras que la solución mod 2 se ajusta a una.

f(n) = 2n(abs(n) % 2) - n + sgn(n)

En C #, esto se convierte en el siguiente:

public static Int32 f(Int32 n) { return 2 * n * (Math.Abs(n) % 2) - n + Math.Sign(n); }

Para que funcione con todos los valores, debe reemplazar Math.Abs() con (n > 0) ? +n : -n (n > 0) ? +n : -n e incluye el cálculo en un bloque unchecked marcar. Entonces obtienes incluso Int.Min asignado a sí mismo como lo hace la negación no verificada.

ACTUALIZAR

Inspirado por otra respuesta, explicaré cómo funciona la función y cómo construir dicha función.

Vamos a empezar desde el principio. La función f se aplica repetidamente a un valor dado n produciendo una secuencia de valores.

n => f(n) => f(f(n)) => f(f(f(n))) => f(f(f(f(n)))) => ...

La pregunta exige f(f(n)) = -n , que son dos aplicaciones sucesivas de f niega el argumento. Dos aplicaciones adicionales de f - cuatro en total - niegan el argumento nuevamente, dando como resultado n nuevamente.

n => f(n) => -n => f(f(f(n))) => n => f(n) => ...

Ahora hay un ciclo obvio de longitud cuatro. Sustituyendo x = f(n) y observando que la ecuación obtenida f(f(f(n))) = f(f(x)) = -x cumple, se obtiene lo siguiente.

n => x => -n => -x => n => ...

Entonces obtenemos un ciclo de longitud cuatro con dos números y los dos números negados. Si imaginas el ciclo como un rectángulo, los valores negados se ubican en esquinas opuestas.

Una de las muchas soluciones para construir un ciclo de este tipo es la siguiente a partir de n.

n => negate and subtract one -n - 1 = -(n + 1) => add one -n => negate and add one n + 1 => subtract one n

Un ejemplo concreto es que dicho ciclo es +1 => -2 => -1 => +2 => +1 . Casi terminamos. Observando que el ciclo construido contiene un número impar positivo, su sucesor par, y que ambos números se niegan, podemos dividir fácilmente los enteros en muchos de esos ciclos ( 2^32 es un múltiplo de cuatro) y hemos encontrado una función que satisface las condiciones.

Pero tenemos un problema con cero. El ciclo debe contener 0 => x => 0 porque el cero se niega a sí mismo. Y como el ciclo ya indica 0 => x sigue 0 => x => 0 => x . Esto es solo un ciclo de longitud dos y x se convierte en sí mismo después de dos aplicaciones, no en -x . Por suerte hay un caso que resuelve el problema. Si X es igual a cero, obtenemos un ciclo de longitud uno que solo contiene cero y resolvimos el problema concluyendo que cero es un punto fijo de f .

¿Hecho? Casi. Tenemos 2^32 números, cero es un punto fijo que deja 2^32 - 1 números, y debemos dividir ese número en ciclos de cuatro números. Es malo que 2^32 - 1 no sea un múltiplo de cuatro; quedarán tres números que no están en ningún ciclo de longitud cuatro.

Explicaré la parte restante de la solución utilizando el conjunto más pequeño de itegers con signo de 3 bits que van de -4 a +3 . Hemos terminado con cero. Tenemos un ciclo completo +1 => -2 => -1 => +2 => +1 . Ahora construyamos el ciclo comenzando en +3 .

+3 => -4 => -3 => +4 => +3

El problema que surge es que +4 no se puede representar como un entero de 3 bits. Obtendríamos +4 negando -3 a +3 , lo que sigue siendo un entero válido de 3 bits, pero luego agregando uno a +3 ( 011 binario) se obtienen 100 binarios. Interpretado como entero sin signo es +4 pero tenemos que interpretarlo como entero con signo -4 . Entonces, en realidad -4 para este ejemplo o Int.MinValue en el caso general es un segundo punto fijo de negación aritmética de enteros: 0 y Int.MinValue se asignan a sí mismos. Así que el ciclo es en realidad como sigue.

+3 => -4 => -3 => -4 => -3

Es un ciclo de longitud dos y adicionalmente +3 ingresa al ciclo a través de -4 . En consecuencia, -4 se asigna correctamente a sí mismo después de dos aplicaciones de función, +3 se asigna correctamente a -3 después de dos aplicaciones de función, pero -3 se asigna erróneamente a sí mismo después de dos aplicaciones de función.

Entonces construimos una función que funciona para todos los enteros menos uno. ¿Podemos hacerlo mejor? No podemos. ¿Por qué? Tenemos que construir ciclos de longitud cuatro y podemos cubrir todo el rango de enteros hasta cuatro valores. Los valores restantes son los dos puntos fijos 0 y Int.MinValue que deben asignarse a sí mismos y los dos enteros arbitrarios x y -x que deben asignarse entre sí mediante dos aplicaciones de función.

Para asignar x a -x y viceversa, deben formar un ciclo de cuatro y deben ubicarse en esquinas opuestas de ese ciclo. En consecuencia, 0 y Int.MinValue deben estar en esquinas opuestas. Esto asignará correctamente x y -x pero intercambiará los dos puntos fijos 0 y Int.MinValue después de dos aplicaciones de función y nos dejará con dos entradas que fallan. Por lo tanto, no es posible construir una función que funcione para todos los valores, pero tenemos una que funciona para todos los valores excepto uno y esto es lo mejor que podemos lograr.

Explotación de excepciones de JavaScript.

function f(n) { try { return n(); } catch(e) { return function() { return -n; }; } }

f(f(0)) => 0

f(f(1)) => -1

Funciona excepto int.MaxValue y 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)); }

Gracias a la sobrecarga en 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)); }

Nadie dijo que f (x) tenía que ser del mismo tipo.

def f(x): if type(x) == list: return -x[0] return [x] f(2) => [2] f(f(2)) => -2

No dijiste qué tipo de lenguaje esperaban ... Aquí hay una solución estática (Haskell). Básicamente es un lío con los 2 bits más significativos:

f :: Int -> Int f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30 | otherwise = complementBit x 30

Es mucho más fácil en un lenguaje dinámico (Python). Solo verifica si el argumento es un número X y devuelve un lambda que devuelve -X:

def f(x): if isinstance(x,int): return (lambda: -x) else: return x()

O bien, podría abusar del preprocesador:

#define f(n) (f##n) #define ff(n) -n int main() { int n = -42; cout << "f(f(" << n << ")) = " << f(f(n)) << endl; }

Para todos los valores de 32 bits (con la advertencia de que -0 es -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); }

Básicamente necesitas emparejar cada bucle -x => x => -x con ay => -y => y bucle. Así que emparejé lados opuestos de la split .

Por ejemplo, para enteros de 4 bits:

0 => 7 => -8 => -7 => 0 1 => 6 => -1 => -6 => 1 2 => 5 => -2 => -5 => 2 3 => 4 => -3 => -4 => 3

Qué tal si:

f(n) = sign(n) - (-1)ⁿ * n

En 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 promueve automáticamente enteros a largos de longitud arbitrarios. En otros idiomas, el entero positivo más grande se desbordará, por lo que funcionará para todos los enteros excepto ese.

Para que funcione con números reales, debe reemplazar la n en (-1) ⁿ con { ceiling(n) if n>0; floor(n) if n<0 } { ceiling(n) if n>0; floor(n) if n<0 } .

En C # (funciona para cualquier doble, excepto en situaciones de desbordamiento):

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)); }

Una versión de C ++, probablemente dobla las reglas de alguna manera pero funciona para todos los tipos numéricos (flotantes, ints, dobles) e incluso tipos de clase que sobrecargan el menos unario:

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; }

Usando números complejos, puede dividir efectivamente la tarea de negar un número en dos pasos:

multiplica n por i, y obtienes n * i, que n gira 90 ° en sentido contrario a las agujas del reloj
multiplica de nuevo por i, y obtienes -n

Lo bueno es que no necesitas ningún código de manejo especial. Simplemente multiplicando por i hace el trabajo.

Pero no se te permite usar números complejos. Así que tienes que crear de alguna manera tu propio eje imaginario, utilizando parte de tu rango de datos. Como necesita exactamente tantos valores imaginarios (intermedios) como valores iniciales, solo le queda la mitad del rango de datos.

Intenté visualizar esto en la siguiente figura, asumiendo datos de 8 bits firmados. Tendría que escalar esto para enteros de 32 bits. El rango permitido para la inicial n es de -64 a +63. Esto es lo que hace la función para n positivo:

Si n está en 0..63 (rango inicial), la llamada a la función agrega 64, asignando n al rango 64..127 (rango intermedio)
Si n está en 64..127 (rango intermedio), la función resta n de 64, mapeando n al rango 0 ..- 63

Para n negativo, la función utiliza el rango intermedio -65 ..- 128.

Utiliza globales ... pero ¿y?

bool done = false f(int n) { int out = n; if(!done) { out = n * -1; done = true; } return out; }

para javascript (u otros lenguajes de tipo dinámico) puede hacer que la función acepte un int o un objeto y devuelva el otro. es decir

function f(n) { if (n.passed) { return -n.val; } else { return {val:n, passed:1}; } }

dando

js> f(f(10)) -10 js> f(f(-10)) 10

alternativamente, puede usar la sobrecarga en un lenguaje fuertemente tipado, aunque eso puede romper las reglas, es decir,

int f(long n) { return n; } long f(int n) { return -n; }

x86 asm (estilo 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

Código verificado, todos los posibles enteros de 32 bits pasados, error con -2147483647 (subdesbordamiento).

:RE

boolean inner = true; int f(int input) { if(inner) { inner = false; return input; } else { inner = true; return -input; } }

La pregunta no dice nada sobre cuál debe ser el tipo de entrada y el valor de retorno de la función f (al menos no de la forma en que lo ha presentado) ...

... solo que cuando n es un entero de 32 bits, entonces f(f(n)) = -n

Entonces, ¿qué tal algo como

Int64 f(Int64 n) { return(n > Int32.MaxValue ? -(n - 4L * Int32.MaxValue): n + 4L * Int32.MaxValue); }

Si n es un entero de 32 bits, la declaración f(f(n)) == -n será verdadera.

Obviamente, este enfoque podría extenderse para que funcione para una gama de números aún más amplia ...

Aquí hay una solución que está inspirada en el requisito o la afirmación de que los números complejos no se pueden usar para resolver este problema.

Multiplicar por la raíz cuadrada de -1 es una idea, que solo parece fallar porque -1 no tiene una raíz cuadrada sobre los enteros. Pero jugar con un programa como matemática da, por ejemplo, la ecuación.

(1849436465 ² +1) mod (2 ³² -3) = 0.

y esto es casi tan bueno como tener una raíz cuadrada de -1. El resultado de la función debe ser un entero con signo. Por lo tanto, voy a utilizar mods de operación de módulo modificados (x, n) que devuelven el entero y congruente a x módulo n más cercano a 0. Solo muy pocos lenguajes de programación tienen una operación de módulo, pero se puede definir fácilmente . Por ejemplo, en python es:

def mods(x, n): y = x % n if y > n/2: y-= n return y

Usando la ecuación anterior, el problema ahora se puede resolver como

def f(x): return mods(x*1849436465, 2**32-3)

Esto satisface f(f(x)) = -xa todos los enteros en el rango . Los resultados de también están en este rango, pero, por supuesto, el cálculo necesitaría enteros de 64 bits.[-2 ³¹ -2, 2 ³¹ -2]f(x)

C # para un rango de 2 ^ 32 - 1 números, todos los números int32 excepto (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

huellas dactilares:

2147483647 3 2 1 0 -1 -2 -3 -2147483647

Me gustaría cambiar los 2 bits más significativos.

00.... => 01.... => 10..... 01.... => 10.... => 11..... 10.... => 11.... => 00..... 11.... => 00.... => 01.....

Como puede ver, es solo una adición, dejando de lado el bit transportado.

¿Cómo llegué a la respuesta? Mi primer pensamiento fue solo una necesidad de simetría. 4 vueltas para volver a donde empecé. Al principio pensé, eso es código 2bits Gray. Entonces pensé que en realidad el binario estándar es suficiente.

Nadie dijo que tenía que ser apátrida.

int32 f(int32 x) { static bool idempotent = false; if (!idempotent) { idempotent = true; return -x; } else { return x; } }

Hacer trampa, pero no tanto como muchos de los ejemplos. Aún más malo sería echar un vistazo a la pila para ver si la dirección de la persona que llama es & f, pero esto será más portátil (aunque no seguro para subprocesos ... la versión segura para subprocesos usaría TLS). Aún más malvado:

int32 f (int32 x) { static int32 answer = -x; return answer; }

Por supuesto, ninguno de estos funciona demasiado bien para el caso de MIN_INT32, pero hay muy poco que puede hacer al respecto a menos que se le permita devolver un tipo más amplio.

trabaja para 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 }

El problema dice "enteros con signo de 32 bits" pero no especifica si son twos-complement o twos-complement ones-complement .

Si usa el complemento de ones, todos los valores de 2 ^ 32 se producen en ciclos de longitud cuatro: no necesita un caso especial para el cero y tampoco necesita condicionales.

Cía:

int32_t f(int32_t x) { return (((x & 0xFFFFU) << 16) | ((x & 0xFFFF0000U) >> 16)) ^ 0xFFFFU; }

Esto funciona por

Intercambiando los bloques alto y bajo de 16 bits.
Invirtiendo uno de los bloques.

Después de dos pasadas tenemos el inverso a nivel de bit del valor original. Lo que en una representación de complemento es equivalente a la negación.

Ejemplos:

Esencialmente, la función tiene que dividir el rango disponible en ciclos de tamaño 4, con -n en el extremo opuesto del ciclo de n. Sin embargo, 0 debe ser parte de un ciclo de tamaño 1, porque de lo contrario 0->x->0->x != -x. Debido a que 0 está solo, debe haber otros 3 valores en nuestro rango (cuyo tamaño es un múltiplo de 4) no en un ciclo adecuado con 4 elementos.

Elegí estos valores extraños adicionales a ser MIN_INT, MAX_INTy MIN_INT+1. Además, se MIN_INT+1asignará MAX_INTcorrectamente, pero se atascará allí y no se volverá a asignar. Creo que este es el mejor compromiso, porque tiene la bonita propiedad de que solo los valores extremos no funcionan correctamente. Además, significa que funcionaría para todos los 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)

Me gustaría compartir mi punto de vista sobre este interesante problema como matemático. Creo que tengo la solución más eficiente.

Si recuerdo correctamente, niega un entero de 32 bits con signo simplemente cambiando el primer bit. Por ejemplo, si n = 1001 1101 1110 1011 1110 0000 1110 1010, entonces -n = 0001 1101 1110 1011 1110 0000 1110 1010.

Entonces, ¿cómo definimos una función f que toma un entero con signo de 32 bits y devuelve otro entero con signo de 32 bits con la propiedad de que tomar f dos veces es lo mismo que voltear el primer bit?

Permítanme reformular la pregunta sin mencionar conceptos aritméticos como enteros.

¿Cómo definimos una función f que toma una secuencia de ceros y unos de longitud 32 y devuelve una secuencia de ceros y unos de la misma longitud, con la propiedad de que f dos veces es lo mismo que voltear el primer bit?

Observación: Si puede responder a la pregunta anterior para el caso de 32 bits, entonces también puede responder para el caso de 64 bits, caso de 100 bits, etc. Simplemente aplique f a los primeros 32 bits.

Ahora si puede responder la pregunta para el caso de 2 bits, ¡voila!

Y sí, resulta que cambiar los 2 primeros bits es suficiente.

Aquí está el pseudo-código

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.

Observación: El paso 2 y el paso 3 juntos se pueden resumir como (a, b) -> (-b, a). ¿Luce familiar? Eso debería recordarte la rotación de 90 grados del plano y la multiplicación por la raíz cuadrada de -1.

Si solo presentara el pseudocódigo sin el largo preludio, parecería como un conejo fuera del sombrero, quería explicar cómo obtuve la solución.

Podría imaginar que usar el bit 31 como un bit imaginario ( i ) sería un enfoque que admitiría la mitad del rango total.

return x ^ ((x%2) ? 1 : -INT_MAX);