Estuve pensando un poquito en el tema de no iterar sobre los bits en 0
Por ejemplo, si tenemos n=6 = 00000000110
Puedo ver dos problemas,
I- podemos intentar evitar iterar sobre los primeros 0, lo cual seria bueno porque si un tipo tiene 32 bits, nos evitamos 29 iteraciones al vicio.
II- podemos evitar iterar sobre el ultimo cero.

Como el punto II me parecio mas duro que el I, comence por el primero.

Aquí va mi solución:

#include <iostream>
#include <limits>
using namespace std;

template<typename T, T Idx>
struct BitMask
{
  static const T value = ( static_cast<T>(1) << Idx ) ;
} ;
 
template<class T>
struct BitsQtty{
   static const int SIZE = sizeof(T)* numeric_limits<unsigned char>::digits -1 ;
};

template<typename T, int Idx>
struct CountBitsHelper
{
  static int count ( T n )
  {
    static const T pos = BitsQtty<T>::SIZE - Idx;
    return ( BitMask<T,  pos >::value - n ) > 0? 0 : static_cast<bool>( ( n & BitMask<T, pos>::value ) ) + CountBitsHelper<T,Idx-1>::count(n);
  }
} ;

 
template<typename T> struct CountBitsHelper<T,-1>
{
  static int count ( T n ) { return 0 ; }
} ;

template<typename T>
struct BitsCounter{
    static int count ( T n){
        return CountBitsHelper<T, BitsQtty<T>::SIZE>::count(n);
    }
};

int main(int argc, char *argv[])
{

    long i;
    cin >> i;
    while( i != -1){
        cout <<   BitsCounter<long>::count(i) << endl;
        cin >> i;
    }
}


Preguntas:
1- Porqué en BitsQtty se resta uno? Esto no estaba funcionando en los ejemplos del thread anterior, es mas no compilaban por este temita :)
2- Porqué pos es de tipo "static const T" en CountBitsHelper::count?, explicar los dos el static y el const!
3- Para qué pos = BitsQtty<T>::SIZE - Idx;


Este código puede ser mas lindo :) quien se anima a simplificarlo?

Espero que les guste!

Saluditos
Sole


------------------ Daniel dijo: -----------------------
Bueno, en suma, va queriendo.... :D

Ta bien la versión combinada...  y con ésto doy por cerrado la parte de C++

Ahora, la parte matemática. Se pueden evitar iterar sobre los bits en 0 ??   (Vamos, los q saben C contesten!!)

  Daniel.

Laburando en el backend de MIPS, tuve en particular q tocar algunas cosas y les cuento algo interesante:

    Gcc soporta una opción de matemática ´veloz´, -ffast-math, que, si el procesador para el q compila lo permite, usa algunas instrucciones un poco locas.
En particular, habilita esta otra opción:
       -funsafe-math-operations

Sí, hay q ser un cacho temerario, pero entre otras cosas, usa el método de ´recíprocos´ como cálculo aproximado de 1/x y 1/sqrt(x). La precisión no está garantizada para todos los procesadores, así q hay q ver. Pero si lo que tiene q hacer es algo rápido y no necesariamente muy preciso, lo recomiendo.

Comunmente, las instrucciones se llaman ´recip´ y ´rsqrt´ respectivamente (en rsqrt, si bien calcula 1/sqrt, la ´r´ es por reciprocal, no por reverse).

El método lo pueden ver explicado acá:
    http://www.derekroconnor.net/NA/Notes/RecSqRoot.pdf


 Daniel.


pd: no, esto no es lo q prometí si resolvían lo del conteo de bits. Lo voy a escribir cdo termine este laburito en MIPS y después de leer el mail de Sole.

errata:

   -funsafe-math-optimizations

no -operations.

    if ( movida->makeMove ( this ) )
    {
        Move *copia =  movida->copy();
        history.push_back ( copia );          //Guarda una copia del movimiento en el historial.
        return true;
    }
    return false;

El código para pedir copias a las movidas, es dependiente del movimiento, por ejemplo "MoveDOWN":

Move* MoveDOWN::copy()
{
    return new MoveDOWN(*this);
}

Y tengo el constructor Sobrecargado para poder recibir movimientos.

Move::Move( Move &movimiento)
{
    this->_pieza = movimiento.getPieza();
    this->_puzzle = movimiento.getPuzzle();
    this->_origen = movimiento.getOrigenPieza();
}

LA pregunta acá es que cuando yo le haga un delete a "Movimiento" el fue el que creo al movimiento copia, entonces siguiendo la regla "El que crea destruye" se me rompe todo, o sea, no puedo hacerle despues un delete a "copia" porque me va a decir que ya lo hice cuando deletie al movimiento original.

¿¿ Tienen alguna idea de como puedo arreglar esto ??

Hola Cristian,

 

A ver, vamos paso por paso. Creo que tenemos un error de concepto previo a tu problema.

Me gustaria que vos contestes lo siguiente: siguiendo un poco la organizacion de memoria de una corrida tenemos que ciertas cosas se guardan en la pila de ejecucion y otras se guardan en el heap, verdad? (si no tenes claros esos conceptos fijate en http://www.linuxjournal.com/article/6390)

Bueno, comentame que es lo que sucede en este codigo 

    if ( movida->makeMove ( this ) )
    {
        Move *copia =  movida->copy();
        history.push_back ( copia );          //Guarda una copia del movimiento en el historial.
        return true;
    }
 

(que es tuyo). Fijate por favor que en el if existe un bloque. Me podrias decir que pasa con cada una de las sentencias en el heap y en el stack y cuando comienza y termina el bloque?

 

David
 

On 9/5/08, Cristian Wilgenhoff <cristian.wil88-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:

Hola, ante todo! disculpen que no seguí comentando nada del programita que estaba haciendo. Me dieron mas tiempo y ya voy a comentar. Pero tengo el siguiente problema:

Cuando yo le digo al puzzle que haga un movimiento desde el main, seria algo así:

 

    Move *movida = new MoveDOWN(g,puzzle);
    puzzle->makeMove(movida).

y makeMove hace esto:

 

    if ( movida->makeMove ( this ) )
    {
        Move *copia =  movida->copy();
        history.push_back ( copia );          //Guarda una copia del movimiento en el historial.
        return true;
    }
    return false;

El código para pedir copias a las movidas, es dependiente del movimiento, por ejemplo "MoveDOWN":

Move* MoveDOWN::copy()
{
    return new MoveDOWN(*this);
}

Y tengo el constructor Sobrecargado para poder recibir movimientos.

Move::Move( Move &movimiento)
{
    this->_pieza = movimiento.getPieza();
    this->_puzzle = movimiento.getPuzzle();
    this->_origen = movimiento.getOrigenPieza();
}

LA pregunta acá es que cuando yo le haga un delete a "Movimiento" el fue el que creo al movimiento copia, entonces siguiendo la regla "El que crea destruye" se me rompe todo, o sea, no puedo hacerle despues un delete a "copia" porque me va a decir que ya lo hice cuando deletie al movimiento original.

¿¿ Tienen alguna idea de como puedo arreglar esto ??