Aprendiz eterno
Comprobar si un número x es distinto de cero usando los operadores legales excepto !.
Ejemplos: isNonZero(3) = 1, isNonZero(0) = 0
operaciones legales: ~ & ^ | + << >>
- Nota: Solo se deben utilizar operadores bit a bit.
if, else, foretc. no se pueden utilizar.
- Edit1: el número de operadores no debe exceder de 10.
- Edit2: Considere el tamaño de
int ser de 4 bytes.
int isNonZero(int x) {
return ???;
}
Utilizando ! esto sería trivial, pero ¿cómo lo hacemos sin usar ! ?
ruso
La versión logarítmica de la función adamk:
int isNotZero(unsigned int n){
n |= n >> 16;
n |= n >> 8;
n |= n >> 4;
n |= n >> 2;
n |= n >> 1;
return n & 1;
};
Y el más rápido, pero en montaje:
xor eax, eax
sub eax, n // carry would be set if the number was not 0
xor eax, eax
adc eax, 0 // eax was 0, and if we had carry, it will became 1
En C se puede escribir algo similar a la versión ensamblador, solo hay que jugar con el bit de signo y con algunas diferencias.
EDITAR: aquí está la versión más rápida que se me ocurre en C:
1) para números negativos: si se establece el bit de signo, el número no es 0.
2) para positivo: 0 - n será negativo, y se puede verificar como en el caso 1. No veo el - en la lista de las operaciones legales, entonces usaremos ~n + 1 en lugar de.
Lo que obtenemos:
int isNotZero(unsigned int n){ // unsigned is safer for bit operations
return ((n | (~n + 1)) >> 31) & 1;
}
usta
int isNonZero(unsigned x) {
return ~( ~x & ( x + ~0 ) ) >> 31;
}
Suponiendo que int es de 32 bits (/* EDITAR: esta parte ya no se aplica porque cambié el tipo de parámetro a sin firmar */ y los cambios con signo se comportan exactamente como los sin signo).
kriss
¿Por qué complicar las cosas?
int isNonZero(int x) {
return x;
}
Funciona porque la convención de C es que cada valor distinto de cero significa verdadero, ya que isNonZero devuelve un int que es legal.
Algunas personas argumentaron que la función isNonZero() debería devolver 1 para la entrada 3 como se muestra en el ejemplo.
Si está utilizando C ++, sigue siendo tan fácil como antes:
int isNonZero(int x) {
return (bool)x;
}
Ahora la función devuelve 1 si proporciona 3.
De acuerdo, no funciona con C que pierde un tipo booleano adecuado.
Ahora, si supones que los enteros son de 32 bits y se permite +:
int isNonZero(int x) {
return ((x|(x+0x7FFFFFFF))>>31)&1;
}
En algunas arquitecturas puede incluso evitar el final &1simplemente convirtiendo x en unsigned (que tiene un costo de tiempo de ejecución nulo), pero ese es un comportamiento indefinido, por lo tanto, depende de la implementación (depende de si la arquitectura de destino usa el cambio lógico o firmado a la derecha).
int isNonZero(int x) {
return ((unsigned)(x|(x+0x7FFFFFFF)))>>31;
}
matapatatas
int is_32bit_zero( int x ) {
return 1 ^ (unsigned) ( x + ~0 & ~x ) >> 31;
}
- Resta 1. (
~0 genera menos uno en una máquina de complemento a dos. Esto es una suposición.)
- Seleccione solo el bit volteado que volteó a uno.
- El bit más significativo solo cambia como resultado de restar uno si
x es cero
- Mueve el bit más significativo al bit menos significativo.
Cuento seis operadores. Podría usar 0xFFFFFFFF para cinco. el elenco a unsigned no cuenta con máquina de complemento a dos ;v) .
http://ideone.com/Omobw
Adán
Bit a bit O todos los bits en el número:
int isByteNonZero(int x) {
return ((x >> 7) & 1) |
((x >> 6) & 1) |
((x >> 5) & 1) |
((x >> 4) & 1) |
((x >> 3) & 1) |
((x >> 2) & 1) |
((x >> 1) & 1) |
((x >> 0) & 1);
}
int isNonZero(int x) {
return isByteNonZero( x >> 24 & 0xff ) |
isByteNonZero( x >> 16 & 0xff ) |
isByteNonZero( x >> 8 & 0xff ) |
isByteNonZero( x & 0xff );
}
básicamente lo que necesita o los bits. Por ejemplo, si sabe que su número tiene 8 bits de ancho:
int isNonZero(uint8_t x)
{
int res = 0;
res |= (x >> 0) & 1;
res |= (x >> 1) & 1;
res |= (x >> 2) & 1;
res |= (x >> 3) & 1;
res |= (x >> 4) & 1;
res |= (x >> 5) & 1;
res |= (x >> 6) & 1;
res |= (x >> 7) & 1;
return res;
}
TayyaR
Mi solución es la siguiente,
int isNonZero(int n)
{
return ~(n == 0) + 2;
}
En C, un número distinto de cero es distinto de cero. No ha requerido explícitamente que la función devuelva 1 o 0 (pero está implícito). Por favor explícitamente define lo que devolverá tu función. Todo lo que has dado son 2 ejemplos.
– PP.
12 de octubre de 2010 a las 7:51
Al menos haz que la función devuelva un bool para evitar respuestas como
return x;(sí lo hice). Un poco de contexto también sería interesante, ¿por qué usted (cualquiera) necesitaría escribir una función de este tipo con tales restricciones?– kriss
12 de octubre de 2010 a las 8:07
desde cuando es
+un operador bit a bit?–Oliver Charlesworth
15/10/2010 a las 23:17
¿La gente realmente hace preguntas tontas como esta en las entrevistas? Su total BS (disculpe el uso de jerga demasiado técnica)
– pm100
15 de octubre de 2010 a las 23:18
La respuesta correcta a esta pregunta de la entrevista es: ¿Qué pretende hacer con el resultado? ¿comparación? Entonces, ¿por qué no puedo hacer la comparación en primer lugar? Tengo mejores cosas que hacer con mi tiempo, no has podido ser seleccionado para convertirte en mi jefe.
– Mouviciel
16 de octubre de 2010 a las 7:24