boost/pending/integer_log2.hpp

   1 // -----------------------------------------------------------
   2 // integer_log2.hpp
   3 //
   4 //   Gives the integer part of the logarithm, in base 2, of a
   5 // given number. Behavior is undefined if the argument is <= 0.
   6 //
   7 //         Copyright (c) 2003-2004, 2008 Gennaro Prota
   8 //
   9 // Distributed under the Boost Software License, Version 1.0.
  10 //    (See accompanying file LICENSE_1_0.txt or copy at
  11 //          http://www.boost.org/LICENSE_1_0.txt)
  12 //
  13 // -----------------------------------------------------------
  14
  15 #ifndef BOOST_INTEGER_LOG2_HPP_GP_20030301
  16 #define BOOST_INTEGER_LOG2_HPP_GP_20030301
  17
  18 #include <assert.h>
  19 #ifdef __BORLANDC__
  20 #include <climits>
  21 #endif
  22 #include "boost/limits.hpp"
  23 #include "boost/config.hpp"
  24
  25
  26 namespace boost {
  27  namespace detail {
  28
  29   template <typename T>
  30   int integer_log2_impl(T x, int n) {
  31
  32       int result = 0;
  33
  34       while (x != 1) {
  35
  36           const T t = static_cast<T>(x >> n);
  37           if (t) {
  38               result += n;
  39               x = t;
  40           }
  41           n /= 2;
  42
  43       }
  44
  45       return result;
  46   }
  47
  48
  49
  50   // helper to find the maximum power of two
  51   // less than p (more involved than necessary,
  52   // to avoid PTS)
  53   //
  54   template <int p, int n>
  55   struct max_pow2_less {
  56
  57       enum { c = 2*n < p };
  58
  59       BOOST_STATIC_CONSTANT(int, value =
  60           c ? (max_pow2_less< c*p, 2*c*n>::value) : n);
  61
  62   };
  63
  64   template <>
  65   struct max_pow2_less<0, 0> {
  66
  67       BOOST_STATIC_CONSTANT(int, value = 0);
  68   };
  69
  70   // this template is here just for Borland :(
  71   // we could simply rely on numeric_limits but sometimes
  72   // Borland tries to use numeric_limits<const T>, because
  73   // of its usual const-related problems in argument deduction
  74   // - gps
  75   template <typename T>
  76   struct width {
  77
  78 #ifdef __BORLANDC__
  79       BOOST_STATIC_CONSTANT(int, value = sizeof(T) * CHAR_BIT);
  80 #else
  81       BOOST_STATIC_CONSTANT(int, value = (std::numeric_limits<T>::digits));
  82 #endif
  83
  84   };
  85
  86  } // detail
  87
  88
  89  // ---------
  90  // integer_log2
  91  // ---------------
  92  //
  93  template <typename T>
  94  int integer_log2(T x) {
  95
  96      assert(x > 0);
  97
  98      const int n = detail::max_pow2_less<
  99                      detail::width<T> :: value, 4
 100                    > :: value;
 101
 102      return detail::integer_log2_impl(x, n);
 103
 104  }
 105
 106
 107
 108 }
 109
 110
 111
 112 #endif // include guard