Giff said:
Gianni Mariani ha scritto:
Yes, I do it.
You can use a data structure that records the last N states of the value
and then count the states when you want to know the answer. If you only
need 32 or less of the last samples, (or 64 if you have a 64 bit
machine), then you can use simple bit manipulation.
This below is a basic flag class that records history. This brute
forces the count of the number of set bits. You could keep a separate
count of the number of set bits and avoid the computation, however, the
computation only takes 20 cycles and on a modern superscalar CPU,
probably more like 12, so it depends on how often you need to count bits
as to which one is faster. I would go with the smaller class and bet
that you don't need this count very often but that's a design decision
for you.
---------------------------------------------------------------------
// Fast routine for counting number of set bits
// ... lifted from
//
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
template <typename T>
int CountBits( T v )
{
enum { bits_in_char = 8 };
v = v - ((v >> 1) & (T)~(T)0/3); // temp
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15; // temp
return (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * bits_in_char;
}
// ======== FlagWithHistory ===========================================
/**
* Special flag that stores the flag state for the last 32 (for 32 bit
* word systems).
*
*/
class FlagWithHistory
{
// change to unsigned long long for 64 bits on platform that support
// long long - and if you need 64 history values.
typedef unsigned int t_FlagValue;
t_FlagValue m_value;
public:
FlagWithHistory( bool i_state = false )
: m_value( i_state ? 1 : 0 )
{
}
bool Set( bool i_state )
{
m_value <<= 1;
m_value |= i_state ? 1 : 0;
return i_state;
}
bool Get()
{
return m_value & 1;
}
bool operator=( bool i_state )
{
return Set( i_state );
}
operator bool()
{
return Get();
}
static const unsigned bits_in_word = 8 * sizeof( t_FlagValue );
// GetHistoryCount gets the number of times the flag was
// set over the last "i_event_history" modifications of the
// flag.
unsigned GetHistoryCount( unsigned i_event_history = bits_in_word )
{
if ( i_event_history <= bits_in_word )
{
t_FlagValue l_mask = ~ t_FlagValue();
if ( i_event_history < bits_in_word )
{
l_mask = ( 1 << ( i_event_history ) ) -1;
}
return CountBits( m_value & l_mask );
}
throw "out of range";
}
};
#include <iostream>
int main()
{
FlagWithHistory flag( true );
std::cout << "Flag state is " << flag << "\n";
std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";
flag = true;
std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";
flag = false;
std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";
flag = true;
std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";
flag = false;
std::cout << "Flag count is " << flag.GetHistoryCount() << "\n";
std::cout << "Flag state is " << flag << "\n";
std::cout << "Flag count(3) is " << flag.GetHistoryCount(3) << "\n";
}