1 /* count-leading-zeros.h -- counts the number of leading 0 bits in a word.
2 Copyright (C) 2012 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 3 of the License, or
7 (at your option) any later version.
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, see <http://www.gnu.org/licenses/>. */
17 /* Written by Eric Blake. */
19 #ifndef COUNT_LEADING_ZEROS_H
20 # define COUNT_LEADING_ZEROS_H 1
26 /* Expand the code which computes the number of leading zeros of the local
27 variable 'x' of type TYPE (an unsigned integer type) and returns it
28 from the current function. */
29 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
30 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE) \
31 return x ? BUILTIN (x) : CHAR_BIT * sizeof x;
33 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE) \
34 /* This condition is written so as to avoid shifting by more than \
35 31 bits at once, and also avoids a random HP-UX cc bug. */ \
36 verify (((TYPE) -1 >> 31 >> 31 >> 2) == 0); /* TYPE has at most 64 bits */ \
38 if (1 < (TYPE) -1 >> 31) { /* TYPE has more than 32 bits? */ \
39 count = count_leading_zeros_32 (x >> 31 >> 1); \
43 return count + count_leading_zeros_32 (x);
45 /* Compute and return the number of leading zeros in the least
46 significant 32 bits of X. */
48 count_leading_zeros_32 (unsigned int x)
50 /* http://graphics.stanford.edu/~seander/bithacks.html */
51 static const char deBruijnLookup[32] = {
52 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
53 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
64 return 31 - deBruijnLookup[(x * 0x07c4acddU) >> 27];
68 /* Compute and return the number of leading zeros in X. */
70 count_leading_zeros (unsigned int x)
72 COUNT_LEADING_ZEROS (__builtin_clz, unsigned int);
75 /* Compute and return the number of leading zeros in X. */
77 count_leading_zeros_l (unsigned long int x)
79 COUNT_LEADING_ZEROS (__builtin_clzl, unsigned long int);
82 #if HAVE_UNSIGNED_LONG_LONG_INT
83 /* Compute and return the number of leading zeros in X. */
85 count_leading_zeros_ll (unsigned long long int x)
87 COUNT_LEADING_ZEROS (__builtin_clzll, unsigned long long int);
91 #endif /* COUNT_LEADING_ZEROS_H */