bit_fiddling.hpp

Go to the documentation of this file.

/******************************************************************************
** Copyright © 2016 by J.M.McGuiness, coder@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
#include "config.h"
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE { namespace mpl {
 
/// Create a bitmask of a contiguous block of zeros, then ones, starting at the compile-time constant, input number.
/**
   Because the operator>>() is poorly defined this only works for unsigned types. This is because there may be a sign bit or two's complement representation of the negative number. Then shifting might cause the sign bit to be shifted into  the number itself, possibly causing an infinite loop.
 
   Complexity: compile-time: O(n) where n is at most the number of bits used to represent the input type.
   run-time: O(1)
   Space: O(1)
*/
template<
   unsigned long long MSetBit ///< The all-ones bitmask will start from the non-zero msb.
>
struct lsb_bitmask {
   typedef unsigned long long element_type;
 
   constexpr static element_type number=MSetBit;
 
   enum : element_type {
      value=MSetBit|(lsb_bitmask<(MSetBit>>1u)>::value)
   };
};
/**
   We can exit early if the number is shifted to zero.
*/
template<>
struct lsb_bitmask<0u> {
   typedef unsigned long long element_type;
 
   constexpr static element_type number=0;
 
   enum : element_type {
      value=element_type()
   };
};
 
/// Compute the bit position of the set bit, starting at the compile-time constant, input number.
/**
   Because the operator>>() is poorly defined this only works for unsigned types. This is because there may be a sign bit or two's complement representation of the negative number. Then shifting might cause the sign bit to be shifted into  the number itself, possibly causing an infinite loop.
 
   Complexity: compile-time: O(n) where n is at most the number of bits used to represent the input type.
   run-time: O(1)
   Space: O(1)
*/
template<
   unsigned long long SetBit  ///< The set bit in the field.
>
struct bit_position {
   typedef unsigned long long element_type;
 
   constexpr static element_type number=SetBit;
 
   enum : element_type {
      value=bit_position<(SetBit>>1u)>::value+1
   };
};
template<>
struct bit_position<0ULL> {
   typedef unsigned long long element_type;
 
   constexpr static element_type number=0ULL;
 
   enum : element_type {
      value=0ULL
   };
};
 
} } }