Re: Set operations on bool-vectors

[Dmitry Antipov]

On 09/21/2013 02:59 AM, Daniel Colascione wrote:

> I've implemented built-in set operations on bool vectors.

[...]

> +/* Because we round up the BOOL_VECTOR allocate size to word_size
> +   units, we can safely read past the "end" of the vector in the
> +   operations below.  These extra bits are always zero.  Also, we
> +   always BOOL_VECTORS with at least one size_t of storage so that we
> +   don't have to special-case empty bit vectors.  */
> +
> +#if (SIZE_MAX >> 32) & 1
> +# define BITS_PER_SIZE_T 64
> +#else
> +# define BITS_PER_SIZE_T 32
> +#endif

IIUC this should go to the well-known place in lisp.h.

> +static inline
> +EMACS_INT
> +popcount_size_t(size_t val)
> +{
> +  EMACS_INT count;
> +
> +#if defined __GNUC__ && BITS_PER_SIZE_T == 64
> +  count = __builtin_popcountll (val);
> +#elif defined __GNUC__ && BITS_PER_SIZE_T == 32
> +  count = __builtin_popcount (val);
> +#elif defined __MSC_VER && BITS_PER_SIZE_T == 64
> +# pragma intrinsic __popcnt64
> +  count = __popcnt64 (val);
> +#elif defined __MSC_VER && BITS_PER_SIZE_T == 32
> +# pragma intrinsic __popcnt
> +  count = __popcnt (val);
> +#else
> +  {
> +    EMACS_INT j;
> +    count = 0;
> +    for (j = 0; j < BITS_PER_SIZE_T; ++j)
> +      count += !!((((size_t) 1) << j) & val);
> +  }
> +#endif

Why loop? See http://en.wikipedia.org/wiki/Hamming_weight.

Dmitry