bug-gnulib
[Top][All Lists]
Advanced

[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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]