lib/integer_length.c

   1 /* integer_length - find most significant bit in an 'unsigned int'.
   2    Copyright (C) 2011-2012 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 3 of the License, or
   7    (at your option) 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, see <http://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Bruno Haible <bruno@clisp.org>, 2011.  */
  18
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include "integer_length.h"
  23
  24 #include <limits.h>
  25
  26 #include "float+.h"
  27
  28 #define NBITS (sizeof (unsigned int) * CHAR_BIT)
  29
  30 int
  31 integer_length (unsigned int x)
  32 {
  33 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
  34   if (x == 0)
  35     return 0;
  36   else
  37     return NBITS - __builtin_clz (x);
  38 #else
  39 # if defined DBL_EXPBIT0_WORD && defined DBL_EXPBIT0_BIT
  40   if (NBITS <= DBL_MANT_BIT)
  41     {
  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)
  46 #  define NWORDS \
  47     ((sizeof (double) + sizeof (unsigned int) - 1) / sizeof (unsigned int))
  48       typedef union { double value; unsigned int word[NWORDS]; }
  49               memory_double;
  50
  51       if (x == 0)
  52         return 0;
  53       else
  54         {
  55           memory_double m;
  56           unsigned int exponent;
  57
  58           if (1)
  59             {
  60               /* Use a single integer to floating-point conversion.  */
  61               m.value = x;
  62             }
  63           else
  64             {
  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.
  69                    Use the identity
  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));
  76
  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;
  81
  82               /* Subtract 2^(DBL_MANT_DIG-1).  */
  83               m.value = m.value - TWO_DBL_MANT_DIG;
  84             }
  85
  86           exponent =
  87             (m.word[DBL_EXPBIT0_WORD] >> DBL_EXPBIT0_BIT) & DBL_EXP_MASK;
  88           return exponent - DBL_EXP_BIAS;
  89         }
  90     }
  91   else
  92 # endif
  93     if (NBITS == 32)
  94       {
  95         /* 6 comparisons.  */
  96         if (x != 0)
  97           {
  98             int result = 1;
  99             if (x >= 0x10000)
 100               {
 101                 x = x >> 16;
 102                 result += 16;
 103               }
 104             if (x >= 0x100)
 105               {
 106                 x = x >> 8;
 107                 result += 8;
 108               }
 109             if (x >= 0x10)
 110               {
 111                 x = x >> 4;
 112                 result += 4;
 113               }
 114             if (x >= 0x4)
 115               {
 116                 x = x >> 2;
 117                 result += 2;
 118               }
 119             if (x >= 0x2)
 120               {
 121                 x = x >> 1;
 122                 result += 1;
 123               }
 124             return result;
 125           }
 126         else
 127           return 0;
 128       }
 129     else
 130       {
 131         /* Naive loop.
 132            Works for any value of NBITS.  */
 133         int j;
 134
 135         for (j = NBITS - 1; j >= 0; j--)
 136           if (x & (1U << j))
 137             return j + 1;
 138         return 0;
 139       }
 140 #endif
 141 }