MOAB: Mesh Oriented datABase  (version 5.4.1)
Bits.hpp
Go to the documentation of this file.
00001 /* *****************************************************************
00002     MESQUITE -- The Mesh Quality Improvement Toolkit
00003 
00004     Copyright 2007 Sandia National Laboratories.  Developed at the
00005     University of Wisconsin--Madison under SNL contract number
00006     624796.  The U.S. Government and the University of Wisconsin
00007     retain certain rights to this software.
00008 
00009     This library is free software; you can redistribute it and/or
00010     modify it under the terms of the GNU Lesser General Public
00011     License as published by the Free Software Foundation; either
00012     version 2.1 of the License, or (at your option) any later version.
00013 
00014     This library is distributed in the hope that it will be useful,
00015     but WITHOUT ANY WARRANTY; without even the implied warranty of
00016     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017     Lesser General Public License for more details.
00018 
00019     You should have received a copy of the GNU Lesser General Public License
00020     (lgpl.txt) along with this library; if not, write to the Free Software
00021     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00022 
00023     (2009) [email protected]
00024 
00025   ***************************************************************** */
00026 
00027 /** \file Bits.hpp
00028  *  \brief Functions implementing misc. bit-wise algorithms
00029  *  \author Jason Kraftcheck
00030  */
00031 
00032 #ifndef MSQ_BITS_HPP
00033 #define MSQ_BITS_HPP
00034 
00035 #include "Mesquite.hpp"
00036 
00037 namespace MBMesquite
00038 {
00039 
00040 /**\brief Count number of 1-bits in an unsigned integer
00041  *
00042  * This operation is typically referred to as 'popcount' (short for
00043  * "population count".)  For example the GCC builtin "__builtin_popcount".
00044  * It is also sometimes referred to as "sideways addition" (e.g. Knuth
00045  * volume 4.)
00046  */
00047 inline int popcount( unsigned int x )
00048 {
00049 #if 0  // April '08 bug report says gcc builtin not so good unless Intel SSE4
00050 //#ifdef __GNUC__
00051   return __builtin_popcount( x );
00052 #else
00053     // Use "parallel" algorithm
00054     //  if (sizeof(x) == 4) {
00055     x = ( x & 0x55555555u ) + ( ( x >> 1 ) & 0x55555555u );
00056     x = ( x & 0x33333333u ) + ( ( x >> 2 ) & 0x33333333u );
00057     x = ( x & 0x0f0f0f0fu ) + ( ( x >> 4 ) & 0x0f0f0f0fu );
00058     return ( x * 0x1010101u ) >> 24;  // x % 255
00059                                       //  }
00060                                       //  else {
00061                                       //    x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);
00062                                       //    x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
00063                                       //    x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x >> 4) & 0x0F0F0F0F0F0F0F0FULL);
00064                                       //    return (x * 0x0101010101010101ULL) >> 56;
00065                                       //  }
00066 #endif
00067 }
00068 
00069 }  // namespace MBMesquite
00070 
00071 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines