[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
new module 'integer_length'
From: |
Bruno Haible |
Subject: |
new module 'integer_length' |
Date: |
Fri, 14 Oct 2011 04:16:21 +0200 |
User-agent: |
KMail/1.13.6 (Linux/2.6.37.6-0.5-desktop; KDE/4.6.0; x86_64; ; ) |
Hi,
The code in vasnprintf.c around line 560, which determines the most
significant set bit in an 'unsigned int' word, is not optimally
efficient.
ffs() is a nice primitive, but integer_length() is more powerful,
because ffs(x) == integer_length(x & -x).
This primitive is usally called integer_length() (heritage from Common Lisp).
In GMP you get it through mpz_sizeinbase(x,2).
Here's a proposed module to this effect. Similar modules for the
'unsigned long' and 'unsigned long long' variants will follow.
Comments? Objections?
============================ lib/integer_length.h ============================
/* integer_length - find most significant bit in an unsigned integer.
Copyright (C) 2011 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* Written by Bruno Haible <address@hidden>, 2011. */
#ifndef _INTEGER_LENGTH_H
#define _INTEGER_LENGTH_H
#ifdef __cplusplus
extern "C" {
#endif
/* These functions return the minimum number of bits required to represent
the given unsigned integer.
For non-zero values, this is the position of the most significant bit
that is set, plus one. For zero, it is 0. */
/* Returns the integer length of x.
The result is >= 0, <= sizeof (unsigned int) * CHAR_BIT. */
extern int integer_length (unsigned int x);
/* Returns the integer length of x.
The result is >= 0, <= sizeof (unsigned long) * CHAR_BIT. */
extern int integer_length_l (unsigned long x);
#if HAVE_UNSIGNED_LONG_LONG_INT
/* Returns the integer length of x.
The result is >= 0, <= sizeof (unsigned long long) * CHAR_BIT. */
extern int integer_length_ll (unsigned long long x);
#endif
#ifdef __cplusplus
}
#endif
#endif /* _INTEGER_LENGTH_H */
============================ lib/integer_length.c ============================
/* integer_length - find most significant bit in an 'unsigned int'.
Copyright (C) 2011 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* Written by Bruno Haible <address@hidden>, 2011. */
#include <config.h>
/* Specification. */
#include "integer_length.h"
#include <limits.h>
#include "float+.h"
#define NBITS (sizeof (unsigned int) * CHAR_BIT)
int
integer_length (unsigned int x)
{
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
if (x == 0)
return 0;
else
return NBITS - __builtin_clz (x);
#else
# if defined DBL_EXPBIT0_WORD && defined DBL_EXPBIT0_BIT
if (NBITS <= DBL_MANT_BIT)
{
/* Use 'double' operations.
Assumes an IEEE 754 'double' implementation. */
# define DBL_EXP_MASK ((DBL_MAX_EXP - DBL_MIN_EXP) | 7)
# define DBL_EXP_BIAS (DBL_EXP_MASK / 2 - 1)
# define NWORDS \
((sizeof (double) + sizeof (unsigned int) - 1) / sizeof (unsigned int))
typedef union { double value; unsigned int word[NWORDS]; }
memory_double;
if (x == 0)
return 0;
else
{
memory_double m;
unsigned int exponent;
if (1)
{
/* Use a single integer to floating-point conversion. */
m.value = x;
}
else
{
/* Use a single floating-point subtraction. */
/* 2^(DBL_MANT_DIG-1). */
static const double TWO_DBL_MANT_DIG =
/* Assume DBL_MANT_DIG <= 5 * 31.
Use the identity
n = floor(n/5) + floor((n+1)/5) + ... + floor((n+4)/5). */
(double) (1U << ((DBL_MANT_DIG - 1) / 5))
* (double) (1U << ((DBL_MANT_DIG - 1 + 1) / 5))
* (double) (1U << ((DBL_MANT_DIG - 1 + 2) / 5))
* (double) (1U << ((DBL_MANT_DIG - 1 + 3) / 5))
* (double) (1U << ((DBL_MANT_DIG - 1 + 4) / 5));
/* Construct 2^(DBL_MANT_DIG-1) + x by hand. */
m.word[DBL_EXPBIT0_WORD] =
(DBL_MANT_DIG + DBL_EXP_BIAS) << DBL_EXPBIT0_BIT;
m.word[1 - DBL_EXPBIT0_WORD] = x;
/* Subtract 2^(DBL_MANT_DIG-1). */
m.value = m.value - TWO_DBL_MANT_DIG;
}
exponent =
(m.word[DBL_EXPBIT0_WORD] >> DBL_EXPBIT0_BIT) & DBL_EXP_MASK;
return exponent - DBL_EXP_BIAS;
}
}
else
# endif
if (NBITS == 32)
{
/* 6 comparisons. */
if (x != 0)
{
int result = 1;
if (x >= 0x10000)
{
x = x >> 16;
result += 16;
}
if (x >= 0x100)
{
x = x >> 8;
result += 8;
}
if (x >= 0x10)
{
x = x >> 4;
result += 4;
}
if (x >= 0x4)
{
x = x >> 2;
result += 2;
}
if (x >= 0x2)
{
x = x >> 1;
result += 1;
}
return result;
}
else
return 0;
}
else
{
/* Naive loop.
Works for any value of NBITS. */
int j;
for (j = NBITS - 1; j >= 0; j--)
if (x & (1U << j))
return j + 1;
return 0;
}
#endif
}
=========================== modules/integer_length ===========================
Description:
Finds the most significant bit in an 'unsigned int'.
Files:
lib/integer_length.h
lib/integer_length.c
lib/float+.h
m4/longlong.m4
m4/exponentd.m4
Depends-on:
float
configure.ac:
AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT])
AC_REQUIRE([gl_DOUBLE_EXPONENT_LOCATION])
Makefile.am:
lib_SOURCES += integer_length.c
Include:
"integer_length.h"
License:
LGPLv2+
Maintainer:
Bruno Haible
==============================================================================
--
In memoriam Bekir Çoban-zade <http://en.wikipedia.org/wiki/Bekir_Çoban-zade>
- new module 'integer_length',
Bruno Haible <=