Verifique si un número no es cero usando operadores bit a bit en C

9 minutos de lectura

avatar de usuario
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 ! ?

  • 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

avatar de usuario
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;
}

  • Está utilizando 11 operadores bit a bit aquí. (5x|, 5x>>, 1x&).

    – Haylem

    12 de octubre de 2010 a las 7:02

  • “sub” no es una operación bit a bit; una solución en C++ sería más fácil si se nos permitiera -1

    – MSalters

    12 de octubre de 2010 a las 7:18

  • ¿Por qué no usas simplemente neg? xor eax, eax; neg ecx; adc eax, 0;

    – wj32

    12 de octubre de 2010 a las 7:58

  • isNotZero explicación… n y -n solo pueden ser números no negativos SI n = 0. (n | (~n + 1)) es esencialmente “o” n con -n. Luego cambia el bit más significativo (que es el bit de signo) a la derecha en 31 para colocarlo en la posición del bit menos significativo. Luego corte cualquier signo extendido haciendo “y” con 1.

    – CamHart

    16 de enero de 2014 a las 17:25


  • Hay una solución de ensamblador más corta que no modifica la variable de entrada (que suele ser mejor): xor eax, eax; cmp eax, n; adc eax, 0;

    – amichair

    20 de febrero de 2015 a las 20:35

avatar de usuario
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).

  • Supongo que esto supone la representación del segundo complemento (x + ~0 == x-1)

    – Suma

    12 de octubre de 2010 a las 7:50


  • En mi máquina Intel Linux de 32 bits, esta función regresa 0 o -1. Si resta la respuesta de cero, tendría una función de trabajo (en Intel de 32 bits con gcc).

    – PP.

    12 de octubre de 2010 a las 7:58

  • @PP: Es por eso que escribí “Suponiendo que … los turnos firmados se comporten exactamente como los no firmados”. Esto muestra que en Intel de 32 bits con gcc no se comportan igual, lo cual está perfectamente bien. De hecho, hay más problemas con esta solución cuando x es de tipo firmado. Me extenderé sobre eso en breve…

    -usta

    12 de octubre de 2010 a las 8:12

  • Cambié el tipo de parámetro a sin firmar no solo porque los resultados de las operaciones bit a bit en tipos firmados están definidos por la implementación cuando los argumentos tienen valores negativos, sino también porque sumar y restar una constante distinta de cero tampoco se puede usar de manera confiable, ya que entonces habrá al menos un valor de x con el que + o - dará como resultado un desbordamiento y, por lo tanto, un comportamiento indefinido.

    -usta

    12 de octubre de 2010 a las 8:25


avatar de usuario
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;
}

  • porque ese no es el requisito. el requisito es devolver 1 para distinto de cero

    – Matt Elena

    12 de octubre de 2010 a las 8:06

  • @Matt Ellen: deja que el OP lo escriba, ¿quieres? Cuando escribió su pregunta dijo Example: isNonZero(3) = 1y el ejemplo no es un requisito, nunca lo ha sido.

    – kriss

    12 de octubre de 2010 a las 8:17

  • Ok, pero tu función tampoco cumple con el ejemplo.

    – Matt Elena

    12 de octubre de 2010 a las 8:26

avatar de usuario
matapatatas

int is_32bit_zero( int x ) {
    return 1 ^ (unsigned) ( x + ~0 & ~x ) >> 31;
}
  1. Resta 1. (~0 genera menos uno en una máquina de complemento a dos. Esto es una suposición.)
  2. Seleccione solo el bit volteado que volteó a uno.
  3. El bit más significativo solo cambia como resultado de restar uno si x es cero
  4. 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

avatar de usuario
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 );
}

  • No estoy seguro de si crear una segunda función cuenta como un operador bit a bit 🙂

    – JoshD

    12 de octubre de 2010 a las 6:30

  • No soy una persona C y me pregunto por qué return x|(x&0); no funcionaria? Pon eso en tu respuesta y votaré a favor.

    –Spencer Ruport

    12 de octubre de 2010 a las 6:34

  • @Spencer Ruport: No, eso no funcionará. Esa es una identidad trivial; simplemente devolverá x. El resultado debe ser 1 o 0.

    – JoshD

    12 de octubre de 2010 a las 6:38

  • @JoshD: ¿Por qué el resultado debería ser 1 o 0, en C todos los valores distintos de cero significan verdadero? La identidad funciona perfectamente 🙂 Prueba está en un si no lo crees.

    – kriss

    12 de octubre de 2010 a las 8:05

  • @kriss: Sí, tiene razón, pero la pregunta pide devolver un número entero con valor 0 o 1, como puede ver en la función de la pregunta. De lo contrario, simplemente devolvería x y sería un problema trivial.

    – JoshD

    12 de octubre de 2010 a las 8:15

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

  • No estoy seguro de si crear una segunda función cuenta como un operador bit a bit 🙂

    – JoshD

    12 de octubre de 2010 a las 6:30

  • No soy una persona C y me pregunto por qué return x|(x&0); no funcionaria? Pon eso en tu respuesta y votaré a favor.

    –Spencer Ruport

    12 de octubre de 2010 a las 6:34

  • @Spencer Ruport: No, eso no funcionará. Esa es una identidad trivial; simplemente devolverá x. El resultado debe ser 1 o 0.

    – JoshD

    12 de octubre de 2010 a las 6:38

  • @JoshD: ¿Por qué el resultado debería ser 1 o 0, en C todos los valores distintos de cero significan verdadero? La identidad funciona perfectamente 🙂 Prueba está en un si no lo crees.

    – kriss

    12 de octubre de 2010 a las 8:05

  • @kriss: Sí, tiene razón, pero la pregunta pide devolver un número entero con valor 0 o 1, como puede ver en la función de la pregunta. De lo contrario, simplemente devolvería x y sería un problema trivial.

    – JoshD

    12 de octubre de 2010 a las 8:15

avatar de usuario
TayyaR

Mi solución es la siguiente,

int isNonZero(int n)
{
    return ~(n == 0) + 2;
}

  • == no está incluido en la lista de operadores legales.

    – Martín Baulig

    13 de diciembre de 2012 a las 18:49

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad