libreria - sort algorithm c++

¿Puede XOR de dos enteros salir de límites? (10)

Había estado estudiando el algoritmo para encontrar enteros solitarios en una matriz, y aquí está la implementación:

int arr[] = {10, 20, 30, 5, 20, 10, 30}; int LonelyInteger = 0; for(int i=0; i< 7; i++) { LonelyInteger = LonelyInteger ^ arr[i]; }

El resultado es 5 .

Mi pregunta es: supuestamente los enteros (generados por la operación XOR ) son demasiado grandes debido a esta operación:

LonelyInteger ^ arr[i]

Lo que conduce a un entero potencialmente grande que no puede ser representado por el tipo de datos, digamos int en este caso. Mis preguntas son:

¿Es posible que XOR genere un valor entero tan grande que no pueda almacenarse en el tipo int ?
Si no es posible que esto pueda suceder, ¿hay alguna prueba de ello?

¿Es posible que XOR genere un valor entero tan grande que no pueda almacenarse en el tipo int?

Si los operandos son int , entonces no.

Si no es posible que esto pueda suceder, ¿hay alguna prueba de ello?

Bueno, es trivial desde la definición. Esto no es una prueba matemáticamente rigurosa, pero podría considerar que un bit en la salida de XOR solo será 1 si uno de los operandos tiene 1 en esa posición. Como un bit fuera de rango no puede ser 1 en los operandos, no hay un bit de salida con valor 1 que esté fuera de rango.

¿Es posible que XOR genere un valor entero tan grande que no pueda almacenarse en el tipo int?

Data-Type3 = Data-Type1 operator Data-Type2

Si no es posible que esto pueda suceder, ¿hay alguna prueba de ello?

Tenemos Data-Type3 en el caso de Integers, es uno de Data-Type1 y Data-Type2 que tiene un tamaño más grande, incluso en caso de suma o multiplicación.

SIZE(Data-Type3) = MAX(SIZE(Data-Type1), SIZE(Data-Type2))

Entonces, si Data-Type1 = Data-Type2 , ese también es el tipo de retorno.

Short + Short = Short Short + Integer = Integer Short + Long = Long Integer + Short = Integer Integer + Integer = Integer Integer + Long = Long Long + Short = Long Long + Integer = Long Long + Long = Long

Lo que puede suceder es un desbordamiento, que puede ocurrir cuando una operación tiene un carry. En el complemento de 2, es cuando el transporte a la columna de orden superior no es igual al rendimiento de la columna de orden superior. Lee mas

Pero la operación XOR no puede desbordarse , porque la operación XOR no genera un carry, ya que XOR es una operación de bits como NO.

(Esta publicación se aplica a C, no a C ++)

Los operadores bit a bit no pueden causar una representación de trampa debido a la configuración de bits de relleno inválidos, ver C11 6.2.6.2/1 nota al pie:

... ninguna operación aritmética en valores válidos puede generar una representación de trampa ...

(El significado de "operación aritmética" no está claro, pero el índice enlaza con 6.5.11, que es la definición de XOR).

Sin embargo, en C pueden hacer que se genere un cero negativo . En el complemento de 2 no hay cero negativo. Pero supongamos que estaba en un sistema con el complemento de 1, entonces podría generar cero negativo a través de ^ y esto podría causar una representación de trampa. 6.2.6.2/3 dice explícitamente que esto es posible:

Si la implementación admite ceros negativos, se generarán solo por:

- los operadores &, |, ^, ~, << y >> con operandos que producen dicho valor;

Finalmente 6.2.6.2/2 implica (estoy bastante seguro de todos modos) que no es posible tener una combinación de bits de valor que represente un número entero que exceda INT_MAX

Para resumir, los posibles resultados de ^ en dos int s son:

Otro valor int válido (quizás con bits de relleno diferentes pero no atrapantes a otras versiones del mismo valor)
Un cero negativo, que puede o no causar una trampa

El resultado nunca puede ser "demasiado grande" en el sentido de que su representación requiere más bits de los que proporciona int , ya que la operación se define para combinar valores de bits de sus operandos, no para producir ningún bit nuevo. Quizás una mejor pregunta podría ser, ¿puede el resultado ser algo más que una representación de valor válida de un int ?

Para enteros sin signo, no. Todos los patrones de bits, y por lo tanto el resultado de todas las operaciones a nivel de bits, son representaciones de valores válidos.

Para enteros con signo, depende de la representación definida por la implementación de valores negativos. Cada implementación que probablemente encuentres usa el complemento de 2, en el que nuevamente cada patrón de bits es válido; así que de nuevo, el resultado de cualquier operación bit a bit será una representación válida.

Sin embargo, el estándar también permite otras representaciones, en las que puede haber uno o más patrones de bits no válidos. En ese caso, es posible que una operación bit a bit, con dos operandos válidos, produzca ese patrón y, por lo tanto, produzca un resultado no válido.

En un CASO GENERAL, el algoritmo descrito realmente no puede encontrar un entero solitario en una matriz. Lo que realmente encuentra es XOR de todos los elementos que ocurren allí en números impares.

Entonces, si solo hay un elemento ''solitario'' allí, diga un elemento ''a'' , y todos los demás elementos ocurran INCLUSO varias veces en la matriz, entonces funciona ''según sea necesario'' -> encuentra este elemento solitario ''a'' .

¿Por qué?

El algoritmo realiza XOR de todos los elementos en la matriz (a ^ b ^ c ^ d ^ ...)

La operación XOR tiene las siguientes propiedades:

1) a ^ a = 0 (non-equivalence)

2) a ^ 0 = a (neutrality of 0)

3) a ^ b = b ^ a (commutative property)

4) (a ^ b) ^ c = a ^ (b ^ c) (associative property)

Supongamos, por ejemplo, una matriz con elementos: {a, b, c, a, c, b, a, c}

(elemento ''a'' - 3 veces, elemento ''b'' - dos veces, elemento ''c'' - 3 veces)

Luego, de acuerdo con las propiedades XOR mencionadas anteriormente, el resultado del algoritmo

R = (((((((a ^ b) ^ c) ^ a) ^ c) ^ b) ^ a) ^ c)

se puede reorganizar de la siguiente manera:

R = (a ^ b) ^ (c ^ a) ^ (c ^ b) ^ (a ^ c) =

= (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ (a ^ c) =

= 0 ^ 0 ^ 0 ^ (a ^ c) = (a ^ c)

es decir,

a) ... todos los elementos que ocurren un número INCLUSO resultan en cero

b) ... todos los elementos que ocurren un número ODD veces son XOR-ed y crean el resultado final

XOR es una operación inteligente , por lo que nunca puede desbordarse, por supuesto.

No, no puede. A diferencia de otras respuestas, la mía sería una prueba matemática.

XOR es un acceso directo para la disyunción exclusiva o exclusiva ( ⊕ ) y se puede definir como:

A ⊕ B = (A ∪ B)/(A ∩ B)

Tu tesis es que

∃x: x ∉ A ∧ x ∉ B ∧ x ∈ (A ⊕ B)

Entonces de la primera ecuación

x ∈ (A ∪ B)/(A ∩ B)

Lo que se puede expresar como

x ∈ (A ∪ B) ∧ x ∉ (A ∩ B)

La segunda parte se puede expresar como:

x ∉ A ∧ x ∉ B

La primera parte se puede expresar como:

x ∈ A ∨ x ∈ B

¿Qué choca con nuestra suposición de que x ∉ A ∧ x ∉ B por lo que la tesis es falsa para cualquier conjunto A y B ?

QED

Suponer

int xor = x^y; Max value of int is x = 999999999; Max value of Xor will come if y=0; and Max Xor is 999999999;

Que está en el límite. :)

XOR, AND, OR, NOT y cualquier otro operador bit a bit producen resultados bit a bit , con los bits en el resultado combinados de los bits exactamente en la misma posición en las entradas. Entonces, las entradas de n bits producen n bits sin ningún bit más alto, entonces, ¿cómo puede salir de los límites?

XOR nunca saldrá de los límites porque combina bits y no crea nuevos bits donde no se establecieron bits antes.

El resultado 5 es correcto. Mire la representación binaria de su valor y el resultado XOR

10 00001010 20 00010100 30 00011110 5 00000101 20 00010100 10 00001010 30 00011110 -------------- 00000101 => 5

Una ayuda fácil para calcular el resultado de muchos valores ed XOR es: El resultado tendrá un conjunto de bits donde se combina un número impar de bits, ningún conjunto de bits para un número par de bits.

Si no es posible que esto pueda suceder, ¿hay alguna prueba de ello?

XOR es equivalente a la suma sin llevar los bits individuales. Cuando agrega bits sin acarreo, no puede ocurrir un desbordamiento y, por lo tanto, el valor int no puede salir de los límites.

Estrictamente hablando, no puedes XOR dos enteros . Puede XOR dos bolsas de bits de tamaño entero, y puede tratar esas bolsas de bits como enteros en otros momentos. Incluso puede tratarlos como enteros en cualquier otro momento.

Pero en el momento en que realiza la operación XOR, los trata como algo bastante diferente de los enteros, o incluso números, per se : son solo dos secuencias de bits, donde se comparan los bits correspondientes. El concepto de desbordamiento no se aplica a eso, por lo que si decide tratar el resultado como un entero, tampoco puede desbordarse.