Autor Tema: Bitwise Operations (Leído 10500 veces)

Noel Solw · « **en:** Sábado 29 de Mayo de 2004, 23:56 »

Problema a solucionar por medio de operaciones con bits : (&,|,^,~,>>,<<)
Dados dos numeros unsigned int a,b, determinar sin hacer la suma, si existe el peligro de overflow al realizar la operacion a + b.
Se presentan 3 casos :
[a] : la cifra mas significativa de a y b es “0”, pueden sumarse siempre.
: la cifra mas significativa de a y b es “1”, nunca pueden sumarse.
[c] : una de las cifras mas significativa es “1” y la otra “0”, este es el caso interesante y hay que programar una solucion.

Tengo el problema solucionado y si no recibo soluciones hasta el 10/6/2004,
lo publicare en este foro.
Mi intencion es encontrar soluciones diferentes a la que yo escribi.

JuanK · « **Respuesta #1 en:** Martes 1 de Junio de 2004, 07:35 »

adecua el formato del reto al formato del foro..
debes incluir un ejemplo de los datos de entrada y datos de salida

si tengo tiempo lo hare el fin de semana.

Noel Solw · « **Respuesta #2 en:** Jueves 3 de Junio de 2004, 09:40 »

Ejemplos de datos de entrada y salida:

bitwise operations : overflow check for addition of two unsigned int.

a = 30404
b = 40000
sum = 30404 + 40000 = 4868 wrong

a = 65534
b = 1
sum = 65534 + 1 = 65535 ok

a = 65534
b = 2
sum = 65534 + 2 = 0 wrong

a = 0

end of program - good bye ! ! !

Ayudaria hacer impresiones intermedias de los numeros en representacion binaria
La impresion de las sumas es indicativa solamente, no se usan en la resolucion del problema.

The Black Boy · « **Respuesta #3 en:** Jueves 3 de Junio de 2004, 21:38 »

la verdad sigo sin entender bien que es lo que hay que hacer...

Saludos

JuanK · « **Respuesta #4 en:** Jueves 3 de Junio de 2004, 21:49 »

debes decir si una suma de enteros propduce o no un desboradmiento, es decir determinar si al sumar los enteros el resultado es un tipo de dato mayor que un entero.
Hay que hacer esto sin usar la suma ('+'), solo usando opercaiones binarias..
esta refacil..
por eso digo que tal ves lo haga el fin de semana.

The Black Boy · « **Respuesta #5 en:** Jueves 3 de Junio de 2004, 21:51 »

haaa.... si esta muy facil...

Gracias por la aclaracion Juank

Nagisa

Si, realmente es muy facil. Yo ya lo tengo, lo que ocurre es que los datos que dan como prueba no producen la salida esperada. La cuestion es que el tamaño de un entero varia segun platraforma y compilador.

En mi ordenador con el gcc es de 32 bits, por lo que para producir un overflow necesitamos un numero del orden de 4.2E9 (algo mas).

Aqui posteo mi solucion, la cual considero bastante "elegante" (no habia hecho un codigo recursivo tan bonito desde mi primer factorial... snif)

(Adjunto como .txt por que como .c no me deja)

The Black Boy

te felicito Nagisa...

Amilius

ahi va uno no recursivo en ASM:

Código: Text

 
  const BitSuperior=&#036;80000000;
  function SumaDesbordada(a,b:dword):longbool;
//  var bit_A,bit_B:dword;
  begin
{    result:=true;
    repeat
      if ((a or B) and bitSuperior)=0 then break;//no
      if ((a and B) and bitSuperior)&#60;&#62;0 then exit;//si
      a:=a shl 1;//siguiente bit superior
      b:=b shl 1;
    until (a or B)=0;
    result:=false;}
{    repeat
      bit_A:=a and BitSuperior;
      bit_B:=b and BitSuperior;
      a:=a shl 1;
      b:=b shl 1;
    until bit_A=bit_B;
    result:=(bit_A&#60;&#62;0);}
    asm
      //a está en eax
      //b está en edx
      //Bitsuperior=esi
      //bit_A=ecx
      //bit_B=ebx
      push ebx// preservar!
      push esi// preservar!
      mov esi,BitSuperior
      @ciclo:
        mov ecx,eax
        and ecx,esi
        mov ebx,edx
        and ebx,esi
        shl eax,1
        shl edx,1
      xor ebx,ecx//cmp hace una resta :P
      jnz @ciclo
      pop esi
      pop ebx
      mov result,ecx//prácticamente igual a mov eax,ecx
    end;
  end;
 
 
 

Ya veo el problema:

Esto no funciona (el flag de overflow, ni el de carry) para a y b como enteros de 32bits SIN signo:

Código: Text

 
//Sólo para a y b enteros 32bits con signo
    asm
      //a está en eax
      //b está en edx
      xor ecx,ecx//ecx=false
      add eax,edx//sumar
      jno @fin//saltar si no existe overflow
      not ecx//ecx=true
      @fin:
      mov result,ecx
    end;
 
 

Noel Solw

Naqisa : la solucion recursiva que enviastes es realmente sumamente elegante, y sobre todo muy simple.
Sinceramente, te felicito ! ! ! - Noel

Nagisa

Gracias, gracias... realmente no era dificil

sés

Acabo de entrar en los foros por culpa de JuanK

Estaba mirando los retos y he visto este: Bitwise Operations

Solo quería dar mi solución:

Código: Text

int checkOverflow( unsigned n1, unsigned n2 )
{
  int mask = 0x80;
  
  while( mask & ((n1 & mask) ^ (n2 & mask)) ) {
    mask &#62;&#62;= 1;
    mask &= 0x7fffffff;
  }
  
  return mask & (n1 & mask) & (n2 & mask);
}
 
 

Esta función devuelve verdadero si hay desbordamiento al sumar los números.
Es para enteros de 4 bytes, pero es fácil modificarlo para otros tamaños.

P.D.: El hilo del reto está cerrado, así que pongo mi solución aquí (pido perdón si no es el lugar apropiado).

carlos20

Citar

Acabo de entrar en los foros por culpa de JuanK

Estaba mirando los retos y he visto este: Bitwise Operations

Solo quería dar mi solución:

CODE
int checkOverflow( unsigned n1, unsigned n2 )
{
int mask = 0x80;

while( mask & ((n1 & mask) ^ (n2 & mask)) ) {
mask >>= 1;
mask &= 0x7fffffff;
}

return mask & (n1 & mask) & (n2 & mask);
}

Esta función devuelve verdadero si hay desbordamiento al sumar los números.
Es para enteros de 4 bytes, pero es fácil modificarlo para otros tamaños.

P.D.: El hilo del reto está cerrado, así que pongo mi solución aquí (pido perdón si no es el lugar apropiado).

hay algo extraño en este mensaje pero no importa

.

Esta es mi solucion funciona con int de 4 bytes , si hay desborde al sumar dos enteros mostrara el mensaje "Error" si no hay desborde mostrara la suma de los dos enteros.

</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>XCODE </td></tr><tr><td id='XCODE'>
#include<iostream>

using namespace std;

int main(void){
   unsigned int A,B;
   cout<<"Ingrese A y B"<<endl;
   cin>>A>>B;
   (~A>=B) ? cout<<A<<"+"<<B<<"="<<A+B<<endl : cout<<A<<"+"<<B<<"="<<"Error"<<endl;
   return 1;
}
</td></tr></table><div class='postcolor'>

¿ y como funciona ?
para saber si hay desborde al sumar dos enteros solo tienes que hacer ~A>=B si esto es falso hay desborde si es verdadero no hay desborde en la suma

¿ por que funciona ?
es muy facil...

sés

Cita de: "carlos20"

hay algo extraño en este mensaje pero no importa .

No sé que tiene de extraño mi mensaje... ni sé porqué no te crees que acabe de entrar a los foros (aunque esto lo borraste). Solo tienes que mirar mi fecha de registro.

Cita de: "carlos20"

¿ y como funciona ?
para saber si hay desborde al sumar dos enteros solo tienes que hacer ~A>=B si esto es falso hay desborde si es verdadero no hay desborde en la suma

¿ por que funciona ?
es muy facil...

No sabía ese truco, me lo apunto.

Ahora tres cositas:

1º Acabo de entrar a los foros. Cuando vi el reto del desbordamiento pensé un algoritmo en 5 min. y me registré para ponerlo. Si le hubiera dedicado más tiempo probablemente hubiera dado con unomejor.

2º No sé si eres bueno... pero lo que tengas de bueno te falta en educación. No sé a qué viene dudar de mí nada más llegar, pero bueno... ya he visto otros mensajes tuyos en el foro y veo que la educación no es tu fuerte *mira a Nagisa*... simplemente te ignoraré.

3º Tu método usa una comparación, lo que significa que hace una resta. Eso me da que no sería válido para el reto.

JuanK

Cita de: "ses"

3º Tu método usa una comparación, lo que significa que hace una resta. Eso me da que no sería válido para el reto.

el >= no es una resta ya que el compilador lo convierte en un JB o en un JNAE segun sea mas conveniente, esta instruccion se realiza en un solo ciclo de procesamiento cosa que en una resta se haria en dos ciclos usando posiblemente SUB y una instruccion de transferencia como JA JB o las otras...

aunque ahora que lo pienso me queda la duda pues un JB o un JNAE se usan solo despues de realizar una operacion .. qaue posiblemente sea una resta... habra que averiguar..

sés

Cita de: "JuanK"

el >= no es una resta ya que el compilador lo convierte en un JB o en un JNAE segun sea mas conveniente, esta instruccion se realiza en un solo ciclo de procesamiento cosa que en una resta se haria en dos ciclos usando posiblemente SUB y una instruccion de transferencia como JA JB o las otras...

Efectivamente, antes del salto condicional tiene que ir algo, en este caso concreto un CMP o un TEST, que lo que hacen es una RESTA.

Amilius en su solución en ensamblador no usa CMP, usa XOR precisamente por esto.

Además:

Cita de: "Noel Solw"

Problema a solucionar por medio de operaciones con bits : (&,|,^,~,>>,<<)

Se supone que esos son los únicos operadores permitidos, ¿no?

JuanK

Hola ses..
he revisado mis apuntes y esto es lo ue tengo,
en efecto el >= se convierte habitualmente en un

CMP eax, xxxxx
JG xxxxxx

Pero el CMP no es una resta si fuese una resta seria :
SUB xxxxxxo
SBB xxxxxx
CMPxxxx xxx
JG xxxxx

Realmente no creo que la instruccion CMP use internamente una resta porque seria muy lento me late que debe hacer un XORo alguna de esas si es posible buscare documentacion al respecto aunque realmente no sipongo de mucho tiempo puesto que al dedicarme al famoso ciadrado magico he descuidado un poco lo de mi tesis de grado y tengo que compensar el tiempo.

sés

En mi viejo libro de ensamblador para el 386 dicen textualmente que CMP realiza una resta sin almacenar el resultado. Para SUB y CMP indican los mismo ciclos de reloj (por cierto, que CMP viene en la sección de ARITMÉTICAS).

Un vistazo a GameDev.net - Intel 80386 Programmer's Reference Manual verifica esto mismo:

Citar

Description

CMP subtracts the second operand from the first but, unlike the SUB instruction, does not store the result; only the flags are changed. CMP is typically used in conjunction with conditional jumps and the SETcc instruction. (Refer to Appendix D for the list of signed and unsigned flag tests provided.) If an operand greater than one byte is compared to an immediate byte, the byte value is first sign-extended.

Y esto lo pone varias veces:

Citar

...(subtraction instructions SUB, SBB, DEC, AAS, DAS, CMP, and NEG)...

JuanK

Orale, eso si es lo que necesitabamos.. entonces CMP hace una resta sin almacenar resultados... vaya vaya vaya

gracias

carlos20

Hola sés
Intente resolver este incidente por otras vías pero no fue posible y me veo en la obligación de responderte .

Citar

2º No sé si eres bueno... pero lo que tengas de bueno te falta en educación. No sé a qué viene dudar de mí nada más llegar, pero bueno... ya he visto otros mensajes tuyos en el foro y veo que la educación no es tu fuerte *mira a Nagisa*... simplemente te ignoraré.

Sés después de ese comentario queda demostrado que la educación tampoco es tu fuerte , no se porque te molestaste tanto por lo que dije pero como veo que lo interpretaste mal te lo explicare lo extraño en tu mensaje es que el programa falla , y me parece extraño que en el primer mensaje de un usuario en un foro sea para reabrir una discusión cerrada hace varios meses para enviar un programa que falla , no te lo dije en mi mensaje anterior porque creí que al decirte que el mensaje tenia algo extraño notarias el error en el programa o porque tal vez el error en el programa fue un error de redacción cuando lo escribiste en tu mensaje , pero mi comentario se presto para un mal entendido y fue por esa razón que lo modifique el mismo día .

Código: Text

 
//compilado en visual c++
#include &#60;iostream&#62;
#include &#60;math.h&#62;
 
using namespace std;
 
//es la misma funcion
int checkOverflow( unsigned n1, unsigned n2 )
{
  int mask = 0x80;
  
  while( mask & ((n1 & mask) ^ (n2 & mask)) ) {
    mask &#62;&#62;= 1;
    mask &= 0x7fffffff;
  }
  
  return mask & (n1 & mask) & (n2 & mask);
}
 
int main(){
  unsigned A = 0xFFFFFFFF;
    unsigned B = 0;
    
  int b;
    
  for(unsigned n=8&#59; n&#60;32&#59; n++){
    B = pow(2,n);
    
    b = checkOverflow(A,B);
      if(b)
       cout&#60;&#60;&#34;SI : &#34;&#60;&#60;n&#60;&#60;endl;
      else
       cout&#60;&#60;&#34;NO : &#34;&#60;&#60;n&#60;&#60;endl;
  }
    cin.get();
 
  A = 0x7fffffff;
  B = 0;
  for(n=0&#59; n&#60;1000&#59; n++){
    
    b = checkOverflow(A,B);
    B++;
      if(b)
       cout&#60;&#60;&#34;SI : &#34;&#60;&#60;n&#60;&#60;endl;
      else
       cout&#60;&#60;&#34;NO : &#34;&#60;&#60;n&#60;&#60;endl;
  }
  
  return 1;
}
 
 

sés Escrito el 23/03/2005, 03:38 PM

Código: Text

 
int checkOverflow( unsigned n1, unsigned n2 )
{
  int mask = 0x80;
  
  while( mask & ((n1 & mask) ^ (n2 & mask)) ) {
    mask &#62;&#62;= 1;
    mask &= 0x7fffffff;
  }
  
  return mask & (n1 & mask) & (n2 & mask);
}
 
 

Citar

Esta función devuelve verdadero si hay desbordamiento al sumar los números.
Es para enteros de 4 bytes, pero es fácil modificarlo para otros tamaños.

La función tal como esta en tu mensaje no detecta el desborde en todos los casos y falla al menos en los casos que demuestro en este programa , estoy asumiendo que la función debe retornar verdadero cuando hay desborde como lo dices en el mensaje , para desbordar un entero sin signo de 4 bytes es necesario un valor mayor a 0xffffffff pero si paso como argumento a la función 0xffffffff y 0x80000000 la función retorna falso ¿quiere decir que no hay overflow al sumar 0xffffffff y 0x80000000 ? el overflow es mas que evidente en este caso y en los casos que prueva el programa y la función dice que no hay overflow ,si le paso a la función 0x7fffffff y 1 por ejemplo la función retorna verdadero ¿ por que? si la suma de 0x7fffffff y 1 para enteros de 4 bytes sin signo no genera un overflow . otra cosa es que la operación mask &= 0x7fffffff no tiene ningún efecto en el valor de mask porque en la función le asignas a mask 128 (10000000 en binario ) y luego divides entre 2 ( >>1 que es equivalente ) el 128 en algunos casos 7 veces 64 , 32 , 16 , 8 , 4 , 2 , 1 y en ocasiones 8 veces hasta que el valor de mask es 0 ( la división entera de 1/2 ) el valor 0x7fffffff permanece constante y realizar la operación & entre 0x7fffffff y los números 64 , 32 , 16 , 8 , 4 , 2 , 1 y 0 da como resultado los mismos números .

Citar

3º Tu método usa una comparación, lo que significa que hace una resta. Eso me da que no sería válido para el reto.

Bueno si mi programa no es valido porque genera instrucciones equivalentes a una resta tu programa tampoco seria valido porque la operación >>1 es equivalente a dividir entre 2 no estoy diciendo que genera las mismas instrucciones en ensamblador estoy diciendo que mask >>= 1 es equivalente a mask /=2 ; en el programa que fue enviado antes por nagisa como solución a este reto se uso el operador != y aun así fue considerado como valido .

sés

Antes de nada, corregir mi código. Lo pegué mal pporque estuve probando con bytes antes de escribir el mensaje y puse mal la máscara

:
</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>XCODE </td></tr><tr><td id='XCODE'>int checkOverflow( unsigned n1, unsigned n2 )
{
  unsigned mask = 0x80000000;

  while( mask & ((n1 & mask) ^ (n2 & mask)) ) {
    mask >>= 1;
    mask &= 0x7fffffff;
  }

  return mask & (n1 & mask) & (n2 & mask);
}</td></tr></table><div class='postcolor'>

Ahora por partes.

Lo primero es que yo no te he faltado al respeto, lo único que dije es que no tenías educación por dudar de mí nada más entrar en el foro y sin ningún motivo. Cosa que mantengo.

Además veo que sigues llendo en plan prepotente al seguir queriendo salirte con la tuya aun habiendo demostrado que no tienes razón.

El código que has puesto para demostrar que mi código no funciona NO FUNCIONA. Si lo hace es por un fallo del Visual C, porque n en el segundo for no está declarada (la declaras en el primero). También me da algún error en la llamada a pow(), pero eso podría ser cosa del MingW.
Aunque a ti te funcione solo demostraría que el código que pegué mal está... pues eso, mal.

Citar

Bueno si mi programa no es valido porque genera instrucciones equivalentes a una resta tu programa tampoco seria valido porque la operación >>1 es equivalente a dividir entre 2 no estoy diciendo que genera las mismas instrucciones en ensamblador estoy diciendo que mask >>= 1 es equivalente a mask /=2 ; en el programa que fue enviado antes por nagisa como solución a este reto se uso el operador != y aun así fue considerado como valido .

Esto demuestra que no sabes cómo salirte con la tuya.

1º Un CMP realiza una resta.
2º Un desplazamiento no realiza una división, solo desplaza los bits por mucho que el resultado sea el mismo.
3º Los desplazamientos entran dentro de los operadores permitidos por el reto, los operadores aritméticos no, y eso incluye al CMP.
4º Nagisa usa el != y el == para preguntar si es igual o distinto de CERO. Todos sabemos que eso no necesita hacer una resta. ¿Por qué es así? Es muy fácil...

Deberías entender esto antes de intentar dar lecciones a los demás, no sea que te las den a ti.
Una de dos, o no tienes ni idea o no sabes a que agarrarte para intentar salirte con la tuya. En cualquier caso, allá tú.

Termino pidiendo disculpas al moderador si soy algo borde, pero no aguanto los prepotentes que intentan dar lecciones y menos aun cuando no llevan la razón.

JuanK

Si quieren pelear crucen su informacion de messenger

Esto no es sitio para eso.