Ensamblador MIPS (SPIM), operaciones en binario

Tema en 'GNU / Linux' iniciado por Jorge S. de Lis, 25 Mar 2006.

Estado del tema:
Cerrado para nuevas respuestas
  1. Buenas lista,

    Tengo un ejercicio entre manos, se trata de averiguar si un número en
    binario es capicúa.

    En el enunciado del ejercicio se deja caer que hay que darle la vuelta al
    número (desechando los ceros a la izquierda claro), y luego comparar el
    original con éste.

    La pregunta es, ¿cómo? No soy muy diestro con los números y no sé si hay
    alguna forma de hacerlo con operaciones aritméticas.

    Que conste que lo he intentado, pero me supera.

    Gracias.
     
  2. Hola "Jorge S. de Lis" <gentakojima.antispam.quitar@gmail.com>
    el Sun, 26 Mar 2006 03:25:50 +0200 escribiste:

    > Buenas lista,
    >
    > Tengo un ejercicio entre manos, se trata de averiguar si un número en
    > binario es capicúa.
    >
    > En el enunciado del ejercicio se deja caer que hay que darle la vuelta al
    > número (desechando los ceros a la izquierda claro), y luego comparar el
    > original con éste.
    >
    > La pregunta es, ¿cómo? No soy muy diestro con los números y no sési hay
    > alguna forma de hacerlo con operaciones aritméticas.


    para *darle la vuelta* a un número vas sacando los bits del número original,
    uno a uno, *estirando* desde la derecha y los vas metiendo en el resultado
    empujando de derecha a izquierda.

    para leer el bit menos significativo normalmente puede usarse un Y lógico:

    x AND 1

    o la función módulo:

    x MOD 2

    en ambos casos el resultado será el valor del bit menos significativo.

    Para desplazar todos los bits hacia la derecha si no hay disponibles
    instrucciones shift puede hacerse dividiendo por dos:

    x DIV 2

    Para desplazar a la izquierda multiplica por dos:

    x MUL 2

    o lo que es lo mismo:

    x ADD x

    Sin una definición precisa de *capicúa* puede haber varias soluciones.
    Si quieres un ejemplo de una de ellas en C dímelo y lo posteo.

    --
    Gonzalo Pérez de Olaguer Córdoba <gpoc@iies.es>
    PGP key 2861C704 --- F206 5671 6789 425D 111C 1302 214F 1934 2861 C704
     
  3. "Jorge S. de Lis" <gentakojima.antispam.quitar@gmail.com> writes:

    > Buenas lista,
    >
    > Tengo un ejercicio entre manos, se trata de averiguar si un número en
    > binario es capicúa.
    >
    > En el enunciado del ejercicio se deja caer que hay que darle la vuelta al
    > número (desechando los ceros a la izquierda claro), y luego comparar el
    > original con éste.
    >
    > La pregunta es, ¿cómo? No soy muy diestro con los números y no sé si hay
    > alguna forma de hacerlo con operaciones aritméticas.


    Aritmeticamente:

    in:=numero;
    out:=0;
    while (in<>0) do
    out:=out*2+(in mod 2);
    in :=(in div 2);
    end;


    > Que conste que lo he intentado, pero me supera.


    Se debe usar las instructiones SHIFT en lugar de multiplicar por 2 y
    dividir por 2.

    --
    __Pascal Bourguignon__ http://www.informatimago.com/
    Our enemies are innovative and resourceful, and so are we. They never
    stop thinking about new ways to harm our country and our people, and
    neither do we. -- Georges W. Bush
     
  4. gamo

    gamo Guest

    On Sun, 26 Mar 2006, Jorge S. de Lis wrote:

    > Buenas lista,
    >
    > Tengo un ejercicio entre manos, se trata de averiguar si un número en
    > binario es capicúa.
    >
    > En el enunciado del ejercicio se deja caer que hay que darle la vuelta al
    > número (desechando los ceros a la izquierda claro), y luego comparar el
    > original con éste.
    >
    > La pregunta es, ¿cómo? No soy muy diestro con los números y no sési hay
    > alguna forma de hacerlo con operaciones aritméticas.
    >
    > Que conste que lo he intentado, pero me supera.
    >
    > Gracias.
    >


    Fácil:

    1. Vas a mi página web
    2. trincas el script perl conversor de base tobin o toany
    3. lo editas y ejecutas sobre el número y
    4. finalmente añades algo así como

    if ($num eq reverse $num) {
    print "$num es capícua\n";
    }

    Salvo error u omisión, espero sirva de ayuda.
    Saludos,

    --
    http://www.telecable.es/personales/gamo/
    Sólo hay 10 tipos de personas, las que saben binario y las que no
    perl -e 'print 111_111_111**2,"\n";'
     
  5. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Pascal Bourguignon wrote:

    > in:=numero;
    > out:=0;
    > while (in<>0) do
    > out:=out*2+(in mod 2);
    > in :=(in div 2);
    > end;


    En pseudo-C:

    in = numero;
    out = 0;
    bucle:
    out = out<<1; // Shift
    bit = in & 1; // And lógico
    out = out | bit; // Or lógico
    in = in>>1; // Shift lógico, SIN ACARREO
    if (in) goto bucle;

    return (numero==out);


    ¿Porqué estoy usando un goto? Pues porque en ensamblador no se usan bucles,
    sino saltos condicionales, principalmente...

    Pregunta para nota: ¿Porqué el shift sobre "in" tiene que ser sin acarreo?

    Pregunta para nota: ¿Cómo habría que hacerlo para "darle la vuelta" no al
    número, sino al registro completo?

    - --
    - ----------------------------------
    Iván Sánchez Ortega -i-punto-sanchez--arroba-mirame-punto-net

    http://acm.asoc.fi.upm.es/~mr/
    Proudly running Debian Linux with 2.6.15-1-686 kernel, KDE3.5.0, and PHP
    5.1.2-1+b1 generating this signature.
    Uptime: 04:52:59 up 1 day, 6:24, 2 users, load average: 0.45, 0.37, 0.40

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2.2 (GNU/Linux)

    iD8DBQFEJgSQ3jcQ2mg3Pc8RApK6AJ4x4ytEl+36nETOO4IFs3s9Ff/SogCfWWs9
    sKSFU9dXqYutcSUGKcmII0c=
    =9Gpd
    -----END PGP SIGNATURE-----
     
  6. Pedro Maicas

    Pedro Maicas Guest

    On Sun, 26 Mar 2006 03:25:50 +0200, "Jorge S. de Lis"
    <gentakojima.antispam.quitar@gmail.com> wrote:

    >La pregunta es, ¿cómo? No soy muy diestro con los números y no sé si hay
    >alguna forma de hacerlo con operaciones aritméticas.


    ayudaría bastante saber si es ensamblador (mips ?) o
    es que el subject no tiene nada que ver con la pregunta.

    si es en ensamblador, es facil darle la vuelta a un
    numero haciendo desplazamientos a través del carry,
    sería algo así:

    es_capicua(original)
    {
    temporal = original;
    while(temporal != 0){
    temporal >>= 1; //shr del asm, usando CY
    volteado <<= 1; //shl del asm, usando cy
    }
    return (valor ^ volteado) == 0; //xor
    }

    Saludos :) -Pedro-

    http://www.maicas.net/

    e-mail en www.maicas.net
     
  7. Jorge S. de Lis en es.ciencia.matematicas escribió:

    > [sobre el ejercicio]


    Muchas gracias a todos. No caía en la cuenta de que el AND con un 1 me
    devolvía el bit menos significativo. Lo de desplazar... sabía que por ahí
    debían ir los tiros pero como no conseguía sacar el último bit jeje...

    Bueno, al final el código quedó así (llamada desde main):


    capicua:
    add $t0, $a0, $0 # recuperamos el numero
    add $t1, $a0, $0 # otra vez, este lo modificaremos

    bucle:

    andi $t3, $t1, 1 # sacamos el ultimo bit
    bne $t3, $0, esunUno # si es un uno esunUno copia el bit

    volver1:

    srl $t1, $t1, 1 # desplaza a la derecha
    beq $t1, $0, terminado # si no quedan bits significativos esto se acaba
    sll $t2, $t2, 1 # desplaza a la izquierda

    j bucle


    esunUno:
    addi $t2, $t2, 1 # copia el bit
    j volver1

    terminado:


    beq $t2, $t0, esCapicua #
    addi $v0, $0, 0 # si son iguales
    # pone un 1
    volver2: # sino pone un 0

    jr $ra #

    esCapicua: #
    addi $v0, $0, 1 # aqui es donde pone el 1
    j volver2 #


    ¡Muchísimas gracias a todos!
     
  8. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Jorge S. de Lis wrote:

    [...]
    > bne $t3, $0, esunUno # si es un uno esunUno copia el bit

    [...]
    > esunUno:
    > addi $t2, $t2, 1 # copia el bit
    > j volver1
    >


    ¡¡No!! ¡¡Sumas directamente $t2 y $t3, y te ahorras dos bifurcaciones!! Si
    $t3 (el bit menos significativo) es cero, la operación de suma dejará $t2
    tal y como estaba.

    Ten en cuenta que dos saltos son más costosos que una operación aritmética
    simple, y que un salto condicional puede ser *muy* costoso en caso de
    procesadores con pipeline. Intenta evitar este comportamiento siempre que
    puedas.

    De cualquier manera, seguro que ya te darán la tabarra con esto del pipeline
    más tarde en otra asignatura...

    - --
    - ----------------------------------
    Iván Sánchez Ortega -i-punto-sanchez--arroba-mirame-punto-net

    El juicio, la valoración, la pretensión, no son experiencias vacías que
    la conciencia tiene... sino experiencias compuestas de una corriente
    intencional.
    -- Edmund Husserl. (1859-1938).
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2.2 (GNU/Linux)

    iD8DBQFEJpbJ3jcQ2mg3Pc8RAhmQAJ4q10bZxWRCxJt7vTLveAEOCuRoBQCfea2Z
    9ODAQpJ8CU6jMK4lET/mal0=
    =mFbv
    -----END PGP SIGNATURE-----
     
  9. Nolo Pongo

    Nolo Pongo Guest

    On Sun, 26 Mar 2006 05:03:41 +0200, Iván Sánchez Ortega
    <i.punto.sanchez--@rroba--mirame.punto.net> wrote:

    >Pregunta para nota: ¿Porqué el shift sobre "in" tiene que ser sin acarreo?


    yo habría hecho los dos sifts con acarreo, pero
    pondría el carry a cero antes del shift sobre in.

    a tu pregunta ¿porque ? pues porque detectaremos
    que hemos acabado de invertir el numero cuando in
    sea cero, si le metes basura en el bit mas alto
    la has cagao.

    claro que out inicialmente es cero, por lo tanto
    tampoco va a meter nada en el carry distinto de cero,
    así que solo hay que estar seguro de que carry=0
    antes de entrar en el bucle.
     
  10. Iván Sánchez Ortega en es.ciencia.matematicas escribió:

    > ¡¡No!! ¡¡Sumas directamente $t2 y $t3, y te ahorras dos bifurcaciones!! Si
    > $t3 (el bit menos significativo) es cero, la operación de suma dejará $t2
    > tal y como estaba.


    ¡Vaya! Creo que minimizar no es lo mío, al menos de momento .-)

    >
    > Ten en cuenta que dos saltos son más costosos que una operación aritmética
    > simple, y que un salto condicional puede ser *muy* costoso en caso de
    > procesadores con pipeline. Intenta evitar este comportamiento siempre que
    > puedas.


    Muchas gracias por el consejo, estaré más al tanto a partir de ahora.
    Además, queda un código mucho más legible. Lo de los saltos continuos me
    mata.

    Aún estamos empezando, y tengo mucho (todo) que aprender sobre el
    funcionamiento de un procesador todavía la verdad :D.

    >
    > De cualquier manera, seguro que ya te darán la tabarra con esto del
    > pipeline más tarde en otra asignatura...


    Puede ser, de momento no nos dijeron nada :X.

    Muchas gracias Iván.
     
  11. Iván Sánchez Ortega en es.ciencia.matematicas escribió:

    > ¡¡No!! ¡¡Sumas directamente $t2 y $t3, y te ahorras dos bifurcaciones!! Si
    > $t3 (el bit menos significativo) es cero, la operación de suma dejará $t2
    > tal y como estaba.


    ¡Vaya! Creo que minimizar no es lo mío, al menos de momento .-)

    >
    > Ten en cuenta que dos saltos son más costosos que una operación aritmética
    > simple, y que un salto condicional puede ser *muy* costoso en caso de
    > procesadores con pipeline. Intenta evitar este comportamiento siempre que
    > puedas.


    Muchas gracias por el consejo, estaré más al tanto a partir de ahora.
    Además, queda un código mucho más legible. Lo de los saltos continuos me
    mata.

    Aún estamos empezando, y tengo mucho (todo) que aprender sobre el
    funcionamiento de un procesador todavía la verdad :D.

    >
    > De cualquier manera, seguro que ya te darán la tabarra con esto del
    > pipeline más tarde en otra asignatura...


    Puede ser, de momento no nos dijeron nada :X.

    Muchas gracias Iván.
     
  12. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Jorge S. de Lis wrote:
    [...]
    > Muchas gracias por el consejo, estaré más al tanto a partir de ahora.
    > Además, queda un código mucho más legible. Lo de los saltos continuos me
    > mata.


    En ensamblador no buscas la legibilidad del código, buscas que sea rápido.
    Rápido de la ostia. La legibilidad va en los comentarios y en la
    documentación adjunta.

    Lo dicho: cuando te enseñen toda la leche del pipeline del procesador verás
    porqué con ensamblador es posible optimizar mucho las cosas.

    Ah, se me olvidaba: de nada ;-)

    - --
    - ----------------------------------
    Iván Sánchez Ortega -i-punto-sanchez--arroba-mirame-punto-net

    Un ordenador no es un televisor ni un microondas, es una herramienta
    compleja.
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2.2 (GNU/Linux)

    iD8DBQFEJtrS3jcQ2mg3Pc8RAsAPAJ9msAJAz2E1il+D+JYayCJgeXa1WgCaAyrB
    9ztwXtladp34dtqSVhnGQgA=
    =orE9
    -----END PGP SIGNATURE-----
     
Estado del tema:
Cerrado para nuevas respuestas

Compartir esta página