clase - fast factorial java
Encontrar un número entero distinto de cero x donde x==-x? (5)
En un curso sobre algoritmos y estructuras de datos en mi universidad, recibí esta pregunta:
¿Qué entero tiene el mismo patrón de bits que su valor negativo?
Significa: x == -x
Sé que el 0 funciona, pero sospecho que el instructor estaba buscando otro número x. ¿Qué x es? ¿Cómo lo encontrarías?
Integer.MIN_VALUE y Long.MIN_VALUE no tienen un valor positivo equivalente y cuando tomas el valor negativo de estos, obtienes el mismo valor.
Negativo es lo mismo que voltear todos los bits y agregar uno. es decir
-x = ~x + 1
Entonces, -0x80000000 = 0x7fffffff + 1 = 0x8000000
Nota: Math.abs (Integer.MIN_VALUE) == Integer.MIN_VALUE que es negativo. Esto se describe en el javadoc para este método.
Técnicamente hay muchas respuestas y tipos.
byte x = 0;
short x = 0;
char x = 0;
int x = 0;
int x = Integer.MIN_VALUE;
float x = 0.0f;
float x = -0.0f;
long x = 0;
long x = Long.MIN_VALUE;
double x = 0.0;
double x = -0.0;
Byte x = 0;
Short x = 0;
Character x = 0;
Integer x = 0;
Integer x = Integer.MIN_VALUE;
Float x = 0.0f;
Float x = -0.0f;
Long x = 0L;
Long x = Long.MIN_VALUE;
Double x = 0.0;
Double x = -0.0;
Un Java Puzzler similar es; cuando es true la siguiente expresión
x != x + 0
EDITAR: punto flotante tiene tanto +0.0 y -0.0 . Por ejemplo, podría considerar -0.0 un valor diferente a 0.0 aunque es el caso de que -0.0 == -(-0.0)
Nota: Double.compare(0.0, -0.0) > 0 Nota:
La pregunta, como se ha dicho, es ambigua.
0 es, por supuesto, la solución obvia, y como otros han discutido, no hay otras soluciones en Java (que es cómo se etiqueta la pregunta).
En C, para cualquier tipo de entero con signo, el valor mínimo del tipo dado puede ser una solución para algunas implementaciones. Por ejemplo, dada una representación de complemento a 2, la evaluación de -INT_MIN probablemente le dará -INT_MIN . Pero, de hecho, el comportamiento de evaluar esa expresión es indefinido debido al desbordamiento, incluso si se asume 2-complemento. (La semántica envolvente es muy común, pero no está garantizada). Además, el estándar C no requiere una representación de complemento a 2; también permite 1-complemento y signo-y-magnitud, ninguno de los cuales tiene ese valor negativo adicional.
Este programa:
#include <stdio.h>
#include <limits.h>
int main(void) {
int n = INT_MIN;
printf("%d/n%d/n", n, -n); /* Warning: Undefined behavior for -n */
}
produce esta salida en mi sistema:
-2147483648
-2147483648
Las operaciones en tipos sin firma C tienen un comportamiento más estrictamente definido. Este programa:
#include <stdio.h>
#include <limits.h>
int main(void) {
unsigned int n = UINT_MAX / 2 + 1;
printf("%u/n%u/n", n, -n);
}
proporciona esta salida en un sistema con int 32 bits (y sin bits de relleno):
2147483648
2147483648
e imprimirá dos líneas de salida idénticas en cualquier implementación conforme.
C ++ tiene el mismo comportamiento (o comportamiento indefinido) que C en esta área.
En Perl, un entero grande caerá sobre una representación de punto flotante si es demasiado grande para ser representado como un entero, pero los escalares de Perl son complicados y pueden almacenar simultáneamente más de una representación. En mi sistema de 64 bits, este programa Perl:
#!/usr/bin/perl
use strict;
use warnings;
my $n = -2.0**63;
print $n, "/n", -$n, "/n";
printf "%d/n%d/n", $n, -$n;
da esta salida:
-9.22337203685478e+18
9.22337203685478e+18
-9223372036854775808
-9223372036854775808
lo cual no estoy del todo seguro de poder explicarme.
Python parece recurrir a algún tipo de enteros de precisión extendida, por lo que no surge el problema del desbordamiento, por lo que no hay un valor numérico que sea su propia negación. Un número de otros idiomas (incluyendo, creo, la mayoría de los dialectos Lisp) hacen lo mismo.
En Ada, un desbordamiento de enteros no tiene un comportamiento indefinido; se requiere para levantar una excepción. Este programa:
with Ada.Text_IO; use Ada.Text_IO;
procedure Foo is
N: Integer := Integer''First;
begin
Put_Line(Integer''Image(N));
Put_Line(Integer''Image(-N));
end Foo;
produce una sola línea de salida:
-2147483648
y luego muere con una excepción Constraint_Error .
Y así sucesivamente, y así sucesivamente, y ...
Entonces, a menos que el instructor solo busque el cero como respuesta, depende mucho del contexto.
Y mirando la pregunta, ¿por qué asume que 0 (lo que es una respuesta perfectamente correcta y obvia a la pregunta como está escrita, y aparentemente es la única respuesta correcta en Java) no es lo que buscaba el instructor?
Para un entero de 8 bits: 1000 0000 firmado, esto es -128 mientras que sin signo, esto es 128
Para ver esto de otra manera: todos los tipos de enteros primitivos con signo representan enteros en el rango
-2 N-1 a 2 N-1 -1
(inclusive), donde N es el número de bits. Siempre que se realice una operación de enteros matemáticos, si el resultado matemático es un número Z que está fuera de ese rango ("desbordamiento"), el resultado real será R = Z + 2 N * k, donde k es un entero positivo o negativo elegido para que R esté en el rango -2 N-1 a 2 N-1 - 1. Entonces digamos x = -2 N-1 , y calculamos -x. El resultado matemático es Z = 2 N-1 , pero está fuera de rango porque Z> 2 N-1 -1. Así que para lograrlo, necesitamos agregar 2 N * k para algunos k, y k debe ser -1. Por lo tanto, el resultado real es R = 2 N-1 + (2 N ) * (- 1) = 2 N-1 - 2 N = -2 N-1 , que es el valor original de x. Entonces ese es un valor que hace que x == -x.
Java solo tiene tipos enteros firmados, pero en los idiomas que tienen tipos no firmados, el rango para los tipos no firmados es de 0 a 2 N -1, inclusive. Pero todo lo demás se aplica de la misma manera.
Supongamos que toma el número representable más bajo posible en formato de complemento de dos firmado. Digamos que este número (llámelo x) tiene un patrón de bits 100000...0 , por ejemplo. Para calcular -x, primero debes voltear todos los bits para obtener 01111...1 , y luego agregarle uno. Esto causa un gran arrastre que resulta en el número 1000....0 otra vez, que es el número con el que comenzó. Así tendrías que x == -x . En el caso de los ints de Java, este valor es Integer.MIN_VALUE , que es -2 31 .
Realmente puedes resolver esto matemáticamente. Dado que todos los números en formato de complemento de dos firmados se representan modulo con una potencia de dos (por ejemplo, 2 d ), entonces la declaración
x == -x
Realmente significa
x == -x (mod 2 d )
Esto significa que
2x == 0 (mod 2 d )
Por lo tanto, las soluciones a este problema son el conjunto de todos los números x donde 2x es 0 mod 2 d . Estos son números de la forma k × 2 d para cualquier entero k. Solo dos de estos valores se pueden representar en formato de complemento de dos con signo con d + 1 bits, a saber, 0 y -2 d . Por lo tanto, el número negativo mínimo posible siempre se comparará igual a su valor negativo.
¡Espero que esto ayude!