¿Cómo extraer números de un número OR en modo bit en una matriz?

Question

Tengo una matriz de números, digamos [1,2,3,4,5,6], quiero encontrar el elemento en la matriz que sea igual al OR a nivel de bits de los elementos restantes.

Actualmente, mi enfoque es encontrar OR a nivel de bits de todos los números de la matriz de la siguiente manera, es decir,$$X = 1 | 2|3|4|5|6$$ Then I am trying to just filter out one a number at a time from X and check if they are equal. For example, if I am checking for number 4, I want something like this - $$(\{X-4\} == 4)?$$ I can easily do this in case of XOR. But not sure how to achieve $ \ {X-4 \} $ in caso de bitwise o?

Answer 1

Se están haciendo las cosas demasiado duro. Más que sucesivamente sacar un elemento a la vez, y hacer un cheque, usted puede simplemente tomar un tiempo de bit a bit O de todos los elementos: Si hay un elemento que es el resultado de la operación or bit a bit sobre todos los demás, entonces ese elemento también será el bit a bit O de todos los elementos, incluyendo a sí mismo!

Aquí es por qué:

Suponiendo que no hay, de hecho, uno de esos elementos, entonces para cualquier posición de bit será cierto que el bit del elemento que está buscando es una $1$ si y sólo si al menos uno de los bits de los otros elementos es un $1$.

Así, es imposible tener un poco de ser un $1$ cuando los bits correspondientes de los otros números son todos los $0$, y también es imposible que el bit de ser un $0$ cuando hay al menos un bit correspondiente de que un $1$.

Eso significa que si nosotros O el valor de los bits del elemento que estamos buscando con todos los bits correspondientes de todos los demás elementos, podemos obtener el valor de la primera parte.

Por lo tanto, el valor de este bit es igual a el valor de la O de todos los bits para esa posición, y por lo tanto se puede tomar simplemente el O de todos los bits para esa posición para encontrar el valor de los bits que queremos.

En otras palabras, usted puede simplemente tomar el bit a bit O para todos los elementos, y luego ver cuál de los elementos es igual al resultado de que: es el elemento que está buscando.

Entonces note que con los números de $1$ a través de $6$ no hay ningún elemento que es el resultado de la operación or bit a bit sobre todos los otros elementos, debido a que para cada posición hay al menos dos $1$'s, y por lo tanto el bit a bit o de cualquier fice elementos le dará $111$, es decir,$7$.

Sin embargo, si se toman los números de $1$ a través de $7$, entonces no sólo es $7$ el bit a bit O de $1$ a través de $6$, pero también de $1$ a través de $7$, y como acabo de explicar, se tiene que ser así, de nuevo, suponiendo que hay un elemento en el primer lugar.