Line data    Source code

       1             : // Author(s): Maurice Laveaux
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : 
      10             : #ifndef MCRL2_UTILITY_POWER_OF_TWO_H_
      11             : #define MCRL2_UTILITY_POWER_OF_TWO_H_
      12             : 
      13             : #include <cassert>
      14             : #include <cstddef>
      15             : #include <limits>
      16             : #include <type_traits>
      17             : 
      18             : namespace mcrl2
      19             : {
      20             : namespace utilities
      21             : {
      22             : 
      23             : /// \returns True when the given value is a power of two.
      24             : template<typename T,
      25             :          typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
      26       26321 : static constexpr bool is_power_of_two(T value)
      27             : {
      28             :   // It is a power of two whenever exactly a single bit is one.
      29       26321 :   return value != 0 && (value & (value - 1)) == 0;
      30             : }
      31             : 
      32             : /// \returns The smallest power of two that is larger than the given value.
      33             : template<typename T,
      34             :          typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
      35       25947 : static T round_up_to_power_of_two(T value)
      36             : {
      37       25947 :   if (is_power_of_two(value)) {
      38        2328 :     return value;
      39             :   }
      40             : 
      41       23619 :   if (value == 0) {
      42       23533 :     return 1;
      43             :   }
      44             : 
      45             :   // This for loop essentially sets all bits to the right of a bit that is equal
      46             :   // to one to all being ones, i.e. 0x0...010...0 becomes 0x0...011...1.
      47         602 :   for(T i = 1; i < sizeof(T) * std::numeric_limits<unsigned char>::digits; i *= 2) {
      48         516 :       value |= value >> i;
      49             :   }
      50             : 
      51             :   // The result will be a value with 0x00..011..1 and adding one to it will result
      52             :   // in a power of two.
      53          86 :   assert(is_power_of_two(value + 1));
      54          86 :   return value + 1;
      55             : }
      56             : 
      57             : } // namespace utilities
      58             : } // namespace mcrl2`
      59             : 
      60             : #endif // MCRL2_UTILITY_POWER_OF_TWO_H_