Branch data     Line data    Source code

       1                 :            : /* *****************************************************************
       2                 :            :     MESQUITE -- The Mesh Quality Improvement Toolkit
       3                 :            : 
       4                 :            :     Copyright 2007 Sandia National Laboratories.  Developed at the
       5                 :            :     University of Wisconsin--Madison under SNL contract number
       6                 :            :     624796.  The U.S. Government and the University of Wisconsin
       7                 :            :     retain certain rights to this software.
       8                 :            : 
       9                 :            :     This library is free software; you can redistribute it and/or
      10                 :            :     modify it under the terms of the GNU Lesser General Public
      11                 :            :     License as published by the Free Software Foundation; either
      12                 :            :     version 2.1 of the License, or (at your option) any later version.
      13                 :            : 
      14                 :            :     This library is distributed in the hope that it will be useful,
      15                 :            :     but WITHOUT ANY WARRANTY; without even the implied warranty of
      16                 :            :     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      17                 :            :     Lesser General Public License for more details.
      18                 :            : 
      19                 :            :     You should have received a copy of the GNU Lesser General Public License
      20                 :            :     (lgpl.txt) along with this library; if not, write to the Free Software
      21                 :            :     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      22                 :            : 
      23                 :            :     (2009) [email protected]
      24                 :            : 
      25                 :            :   ***************************************************************** */
      26                 :            : 
      27                 :            : /** \file Bits.hpp
      28                 :            :  *  \brief Functions implementing misc. bit-wise algorithms
      29                 :            :  *  \author Jason Kraftcheck
      30                 :            :  */
      31                 :            : 
      32                 :            : #ifndef MSQ_BITS_HPP
      33                 :            : #define MSQ_BITS_HPP
      34                 :            : 
      35                 :            : #include "Mesquite.hpp"
      36                 :            : 
      37                 :            : namespace MBMesquite
      38                 :            : {
      39                 :            : 
      40                 :            : /**\brief Count number of 1-bits in an unsigned integer
      41                 :            :  *
      42                 :            :  * This operation is typically referred to as 'popcount' (short for
      43                 :            :  * "population count".)  For example the GCC builtin "__builtin_popcount".
      44                 :            :  * It is also sometimes referred to as "sideways addition" (e.g. Knuth
      45                 :            :  * volume 4.)
      46                 :            :  */
      47                 :    8990576 : inline int popcount( unsigned int x )
      48                 :            : {
      49                 :            : #if 0  // April '08 bug report says gcc builtin not so good unless Intel SSE4
      50                 :            : //#ifdef __GNUC__
      51                 :            :   return __builtin_popcount( x );
      52                 :            : #else
      53                 :            :     // Use "parallel" algorithm
      54                 :            :     //  if (sizeof(x) == 4) {
      55                 :    8990576 :     x = ( x & 0x55555555u ) + ( ( x >> 1 ) & 0x55555555u );
      56                 :    8990576 :     x = ( x & 0x33333333u ) + ( ( x >> 2 ) & 0x33333333u );
      57                 :    8990576 :     x = ( x & 0x0f0f0f0fu ) + ( ( x >> 4 ) & 0x0f0f0f0fu );
      58                 :    8990576 :     return ( x * 0x1010101u ) >> 24;  // x % 255
      59                 :            :                                       //  }
      60                 :            :                                       //  else {
      61                 :            :                                       //    x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);
      62                 :            :                                       //    x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
      63                 :            :                                       //    x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL);
      64                 :            :                                       //    return (x * 0x0101010101010101ULL) >> 56;
      65                 :            :                                       //  }
      66                 :            : #endif
      67                 :            : }
      68                 :            : 
      69                 :            : }  // namespace MBMesquite
      70                 :            : 
      71                 :            : #endif