1 /* count-one-bits.h -- counts the number of 1-bits in a word.
2 Copyright (C) 2007 Free Software Foundation, Inc.
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)
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.
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. */
18 /* Written by Ben Pfaff. */
20 #ifndef COUNT_ONE_BITS_H
21 # define COUNT_ONE_BITS_H 1
27 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR >= 4)
28 #define COUNT_ONE_BITS(BUILTIN, TYPE) \
31 #define COUNT_ONE_BITS(BUILTIN, TYPE) \
32 int count = count_one_bits_32 (x); \
33 if (CHAR_BIT * sizeof (TYPE) > 32) \
34 count += count_one_bits_32 (x >> 31 >> 1); \
35 (void) verify_true (CHAR_BIT * sizeof (TYPE) <= 64); \
38 /* Compute and return the the number of 1-bits set in the least
39 significant 32 bits of X. */
41 count_one_bits_32 (unsigned int x)
43 x = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U);
44 x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U);
45 x = (x >> 16) + (x & 0xffff);
46 x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f);
47 return (x >> 8) + (x & 0x00ff);
51 /* Compute and return the number of 1-bits set in X. */
53 count_one_bits (unsigned int x)
55 COUNT_ONE_BITS (__builtin_popcount, unsigned int);
58 /* Compute and return the number of 1-bits set in X. */
60 count_one_bits_l (unsigned long int x)
62 COUNT_ONE_BITS (__builtin_popcountl, unsigned long int);
65 #if HAVE_UNSIGNED_LONG_LONG_INT
66 /* Compute and return the number of 1-bits set in X. */
68 count_one_bits_ll (unsigned long long int x)
70 COUNT_ONE_BITS (__builtin_popcountll, unsigned long long int);
74 #endif /* COUNT_ONE_BITS_H */