lib/popcount.h

   1 /* popcount.h -- population count
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  17
  18 /* Written by Ben Pfaff.  */
  19
  20 #ifndef POPCOUNT_H
  21 # define POPCOUNT_H 1
  22
  23 #include <limits.h>
  24 #include <stdlib.h>
  25
  26 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR >= 4)
  27 #define POPCOUNT_CALCULATION(NAME, TYPE)        \
  28         return __builtin_##NAME (x);
  29 #else
  30 #define POPCOUNT_CALCULATION(NAME, TYPE)        \
  31         int pop = popcount32 (x);               \
  32         if (CHAR_BIT * sizeof (TYPE) > 32)      \
  33           pop += popcount32 (x >> 31 >> 1);     \
  34         if (CHAR_BIT * sizeof (TYPE) > 64)      \
  35           abort ();                             \
  36         return pop;
  37
  38 /* Compute and return the population count of the low 32 bits of
  39    X, that is, the number of 1-bits set in its least significant
  40    32 bits. */
  41 static inline int
  42 popcount32 (unsigned int x)
  43 {
  44   x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555);
  45   x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333);
  46   x = ((x & 0xf0f0f0f0) >> 4) + (x & 0x0f0f0f0f);
  47   x = ((x & 0xff00ff00) >> 8) + (x & 0x00ff00ff);
  48   return (x >> 16) + (x & 0xff);
  49 }
  50 #endif
  51
  52 /* Compute and return the population count of X, that is, the
  53    number of 1-bits set in X. */
  54 static inline int
  55 popcount (unsigned int x)
  56 {
  57   POPCOUNT_CALCULATION (popcount, unsigned int);
  58 }
  59
  60 /* Compute and return the population count of X, that is, the
  61    number of 1-bits set in X. */
  62 static inline int
  63 popcountl (unsigned long int x)
  64 {
  65   POPCOUNT_CALCULATION (popcountl, unsigned long int);
  66 }
  67
  68 #if HAVE_UNSIGNED_LONG_LONG_INT
  69 /* Compute and return the population count of X, that is, the
  70    number of 1-bits set in X. */
  71 static inline int
  72 popcountll (unsigned long long int x)
  73 {
  74   POPCOUNT_CALCULATION (popcountll, unsigned long long int);
  75 }
  76 #endif
  77
  78 #endif /* POPCOUNT_H */