1 /* integer_length - find most significant bit in an 'unsigned int'.
2 Copyright (C) 2011 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 Bruno Haible <bruno@clisp.org>, 2011. */
22 #include "integer_length.h"
28 #define NBITS (sizeof (unsigned int) * CHAR_BIT)
31 integer_length (unsigned int x)
33 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
37 return NBITS - __builtin_clz (x);
39 # if defined DBL_EXPBIT0_WORD && defined DBL_EXPBIT0_BIT
40 if (NBITS <= DBL_MANT_BIT)
42 /* Use 'double' operations.
43 Assumes an IEEE 754 'double' implementation. */
44 # define DBL_EXP_MASK ((DBL_MAX_EXP - DBL_MIN_EXP) | 7)
45 # define DBL_EXP_BIAS (DBL_EXP_MASK / 2 - 1)
47 ((sizeof (double) + sizeof (unsigned int) - 1) / sizeof (unsigned int))
48 typedef union { double value; unsigned int word[NWORDS]; }
56 unsigned int exponent;
60 /* Use a single integer to floating-point conversion. */
65 /* Use a single floating-point subtraction. */
66 /* 2^(DBL_MANT_DIG-1). */
67 static const double TWO_DBL_MANT_DIG =
68 /* Assume DBL_MANT_DIG <= 5 * 31.
70 n = floor(n/5) + floor((n+1)/5) + ... + floor((n+4)/5). */
71 (double) (1U << ((DBL_MANT_DIG - 1) / 5))
72 * (double) (1U << ((DBL_MANT_DIG - 1 + 1) / 5))
73 * (double) (1U << ((DBL_MANT_DIG - 1 + 2) / 5))
74 * (double) (1U << ((DBL_MANT_DIG - 1 + 3) / 5))
75 * (double) (1U << ((DBL_MANT_DIG - 1 + 4) / 5));
77 /* Construct 2^(DBL_MANT_DIG-1) + x by hand. */
78 m.word[DBL_EXPBIT0_WORD] =
79 (DBL_MANT_DIG + DBL_EXP_BIAS) << DBL_EXPBIT0_BIT;
80 m.word[1 - DBL_EXPBIT0_WORD] = x;
82 /* Subtract 2^(DBL_MANT_DIG-1). */
83 m.value = m.value - TWO_DBL_MANT_DIG;
87 (m.word[DBL_EXPBIT0_WORD] >> DBL_EXPBIT0_BIT) & DBL_EXP_MASK;
88 return exponent - DBL_EXP_BIAS;
132 Works for any value of NBITS. */
135 for (j = NBITS - 1; j >= 0; j--)