Boost logo

Boost :

From: Daniel James (daniel_james_at_[hidden])
Date: 2006-03-20 17:59:22

Daniel James wrote:

> Actually, it does for positive number. Sorry I misread it. What you were
> doing clicked a couple of seconds after I clicked on 'send'. But I'm not
> sure it works for negative numbers.

Okay, probably not perfect, but here's a mostly working version:

template <class T>
size_t integer_hash_value(T val)
     const int size_t_bits = std::numeric_limits<size_t>::digits;

     size_t seed = val;

     // Two's complement for negative numbers but only after using
     // the initial value so that: hash_value(-2) != hash_value(1)
     val = val < 0 ? -1 - val : val;

     while( val >>= size_t_bits )
         hash_combine(seed, (size_t) val);

     return seed;

My idea was something roughly like this:

template <class T>
size_t hash_value2(T val)
     const int size_t_bits = std::numeric_limits<size_t>::digits;
     // ceiling(std::numeric_limits<T>::digits / size_t_bits) - 1
     const int length = (std::numeric_limits<T>::digits - 1)
         / size_t_bits;

     size_t seed = 0;
     T positive = val < 0 ? -1 - val : val;

     // Hopefully, this loop can be unrolled.
     for(unsigned int i = length * size_t_bits; i > 0; i -= size_t_bits)
         seed ^= (size_t) (positive >> i) + (seed<<6) + (seed>>2);
     seed ^= (size_t) val + (seed<<6) + (seed>>2);

     return seed;

Which looks more complicated, but if the compiler optimizes it well (or
I optimize the code), it could be faster (as there are less
comparisons). Although, maybe this is a premature optimization, since
long long is unlikely to have more than twice the number of bits than

I'm not suggesting the specification should spell out an algorithm, but
could describe requirements that both those algorithms would meet. This
would give library authors some latitude to deal with the strengths of
the processor they're targeting and their own imagination.


Boost list run by bdawes at, gregod at, cpdaniel at, john at