halfwaytopfinder.cpp

折半法查找数据最高位

#include <climits>

template <typename T>
class HBPWrapper
{
  template <size_t byte_count>
  static size_t _highest_bit_pos(const T& t) throw ()
  {
    const size_t half_byte_count = byte_count >> 1;
    const size_t half_bit_count = half_byte_count * CHAR_BIT;
    const T high_mask = T(-1 << half_bit_count);

    T high_half = T((t & high_mask) >> half_bit_count);

    size_t sz = high_half ?
      (half_bit_count + _highest_bit_pos<half_byte_count>(high_half))
       : _highest_bit_pos<half_byte_count>(t);

    return sz;
  }
  // 请替代这个特化为更高效的版本
  template <>
  static size_t _highest_bit_pos<1>(const T& t) throw ()
  {
    size_t i = CHAR_BIT;
    for (; i > 0;)
    {
      if (t & T(1 << --i))
      {
        break;
      }
    }
    return i;
  }
public:
  static size_t highest_bit_pos(const T& t) throw ()
  {
    return _highest_bit_pos<sizeof(T)>(t);
  }
};

template <typename T>
inline T highest_bit(const T& t) throw ()
{
  return T(t ? (1 << HBPWrapper<T>::highest_bit_pos(t)) : 0);
}