[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] count-leading-zeros: new module
From: |
Bruno Haible |
Subject: |
Re: [PATCH] count-leading-zeros: new module |
Date: |
Mon, 13 Aug 2012 10:52:20 +0200 |
User-agent: |
KMail/4.7.4 (Linux/3.1.10-1.9-desktop; KDE/4.7.4; x86_64; ; ) |
Hi Eric,
> I needed gcc's clz to determine the most significant bit of a
> number
This new module is redundant w.r.t. the 'integer_length',
'integer_length_l', 'integer_length_ll' modules that are in gnulib
already since last year:
For x != 0:
count_leading_zeros (x) = sizeof x * CHAR_BIT - integer_length (x).
Personally I prefer integer_length over count_leading_zeros, because
the value of integer_length does not depend on the type size:
integer_length_ll ((unsigned long long) x) == integer_length (x)
whereas
count_leading_zeros_ll ((unsigned long long) x) == 32 + count_leading_zeros
(x),
count_leading_zeros is mostly a helper routine for people who implement
multiprecision division or square root algorithms.
Ondřej Bílka wrote:
> Currently fastest way is convert to float and extract exponent. This is
> always log2(n) or log2(n)+1 which can be easily repaired.
Yes, and lib/integer_length.c already implements this trick.
Eric Blake wrote:
> Unfortunately, your implementation is not portable. Gnulib can't afford
> to make assumptions about the layout of a floating point number, even if
> it holds true for most platforms with IEEE doubles.
The code in lib/integer_length.c uses the layout information of floating-
point numbers, after having verified that these assumptions hold
(see m4/exponentd.m4).
> +#define TEST_COUNT_LEADING_ZEROS(FUNC, TYPE, BITS, MAX, ONE) \
> + ASSERT (FUNC (0) == BITS); \
> + for (i = 0; i < BITS; i++) \
> + { \
> + ASSERT (FUNC (ONE << i) == BITS - i - 1); \
> + for (j = 0; j < i; j++) \
> + ASSERT (FUNC ((ONE << i) | (ONE << j)) == BITS - i - 1);\
> + } \
> + for (i = 0; i < 1000; i++) \
> + { \
> + TYPE value = rand () ^ (rand () << 31 << 1); \
> + int count = 0; \
> + for (j = 0; j < BITS; j++) \
> + if (value & (ONE << j)) \
> + count = BITS - j - 1; \
> + ASSERT (count == FUNC (value)); \
> + } \
> + ASSERT (FUNC (MAX) == 0);
I try to avoid such multi-line macros, because they are hard to
single-step under gdb. Better move this code to a separate .h file
that can be #included 3 times.
Bruno