[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Set operations on bool-vectors
From: |
Dmitry Antipov |
Subject: |
Re: Set operations on bool-vectors |
Date: |
Sat, 21 Sep 2013 06:26:07 +0400 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 |
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