Added cbitset_count()

3 files changed, 33 insertions, 9 deletions

diff --git a/examples/bits.c b/examples/bits.c
index 07e17605..16adaf96 100644
--- a/examples/bits.c
+++ b/examples/bits.c
@@ -3,6 +3,7 @@
 

 int main() {

     CBitset set = cbitset_make(23, true);

+    printf("count %zu, %zu\n", cbitset_count(set), set.size);

     cbitset_reset(&set, 9);

     cbitset_resize(&set, 43, false);

     printf("%4zu: ", set.size);

diff --git a/examples/prime.c b/examples/prime.c
index 04f37e9a..74aa108e 100644
--- a/examples/prime.c
+++ b/examples/prime.c
@@ -1,17 +1,22 @@
-#include <stdint.h>

-#include <stdbool.h>

-#include <stdlib.h>

-#include <stdio.h>

-#include <string.h>

 #include <stc/cbitset.h>

 

+#if defined(__GNUC__)

+#define cbitset_popcnt64(i) __builtin_popcountll(i)

+#else

+#define cbitset_popcnt64(i) _mm_popcnt_u64(i)

+#endif

+

+#include <stdio.h>

+

 static inline void sieveOfEratosthenes(size_t n)

 {

     CBitset prime = cbitset_make(n + 1, true);

-    printf("computing primes up to %zu\n", n);

+    printf("computing prime numbers up to %zu\n", n);

     cbitset_reset(&prime, 0);

     cbitset_reset(&prime, 1);

 

+    uint64_t m = cbitset_popcnt64(123456);

+

     for (size_t i = 2; i <= n; ++i) {

         // If prime[i] is not changed, then it is a prime

         if (cbitset_test(prime, i) && i*i <= n) {

@@ -21,12 +26,15 @@ static inline void sieveOfEratosthenes(size_t n)
         }

     }

     puts("done");

-    // Print all prime numbers

+    // Count the primes

     size_t count = 0;

     for (size_t i = 1; i <= n; ++i)

-       if (cbitset_test(prime, i)) ++count; // printf("%zu\n", i);

-

+       if (cbitset_test(prime, i)) ++count;

     printf("number of primes: %zu\n", count);

+    // print primes < 1000

+    for (size_t i = 1; i <= 1000; ++i)

+       if (cbitset_test(prime, i)) printf("%zu ", i);

+    puts("");

     cbitset_destroy(&prime);

 } 

 

diff --git a/stc/cbitset.h b/stc/cbitset.h
index 7f2c2c39..c6311080 100644
--- a/stc/cbitset.h
+++ b/stc/cbitset.h
@@ -48,6 +48,13 @@ int main() {
 #include <assert.h>

 #include "cdefs.h"

 

+#if defined(__GNUC__)

+#define cbitset_popcnt64(i) __builtin_popcountll(i)

+#else

+#include <nmmintrin.h>

+#define cbitset_popcnt64(i) _mm_popcnt_u64(i)

+#endif

+

 typedef struct { uint64_t* _arr; size_t size; } CBitset;

 

 #define cbitset_init {NULL, 0}

@@ -87,6 +94,14 @@ STC_INLINE void cbitset_flip(CBitset *self, size_t i) {
 STC_INLINE bool cbitset_test(CBitset set, size_t i) {

     return (set._arr[i >> 6] & (1ull << (i & 63))) != 0;

 }

+STC_INLINE size_t cbitset_count(CBitset set) {

+    size_t count = 0, n = (set.size + 63) >> 6;

+    if (set.size > 0) {

+        --n; for (size_t i=0; i<n; ++i) count += cbitset_popcnt64(set._arr[i]);

+        count += cbitset_popcnt64(set._arr[n] & ((1ull << (set.size & 63)) - 1));

+    }

+    return count;

+}

 

 STC_INLINE void cbitset_setAll(CBitset *self, bool value) {

     memset(self->_arr, value ? 0xff : 0x0, ((self->size + 63) >> 6) * 8);