Another minor fix in cbits.h. Improved cbits_api.md example.

2 files changed, 27 insertions, 23 deletions

diff --git a/docs/cbits_api.md b/docs/cbits_api.md
index e4b60da6..006ce52a 100644
--- a/docs/cbits_api.md
+++ b/docs/cbits_api.md
@@ -64,40 +64,44 @@ void             cbits_xor(cbits *self, cbits other);        // set of disjoint
 ```c
 #include <stc/cbits.h>
 #include <stdio.h>
+#include <math.h>
+#include <time.h>
 
-static inline cbits sieveOfEratosthenes(size_t n)
+cbits sieveOfEratosthenes(size_t n)
 {
-    cbits primes = cbits_with_size(n + 1, true);
-    cbits_reset(&primes, 0);
-    cbits_reset(&primes, 1);
-
-    c_forrange (i, size_t, 2, n+1) {
-        // If primes[i] is not changed, then it is a prime
-        if (cbits_test(primes, i) && i*i <= n) {
-            c_forrange (j, size_t, i*i, n+1, i) {
-                cbits_reset(&primes, j);
+    cbits bits = cbits_with_size(n>>1, true);
+    size_t q = (size_t) sqrt(n);
+
+    for (size_t i = 3; i <= q; i += 2) {
+        for (size_t j = i; j < n; j += 2) {
+            if (cbits_test(bits, j>>1)) {
+                i = j;
+                break;
             }
         }
+        for (size_t j = i*i; j < n; j += i*2)
+            cbits_reset(&bits, j>>1);
     }
-    return primes;
+    return bits;
 }
 
 int main(void)
 {
-    int n = 100000000;
-    printf("computing prime numbers up to %u\n", n);
+    size_t n = 100000000;
+    printf("computing prime numbers up to %zu\n", n);
 
-    cbits primes = sieveOfEratosthenes(n);
-    puts("done");
+    clock_t t1 = clock();
+    cbits primes = sieveOfEratosthenes(n + 1);
+    size_t nprimes = cbits_count(primes);
+    clock_t t2 = clock();
 
-    size_t np = cbits_count(primes);
-    printf("number of primes: %zu\n", np);
+    printf("number of primes: %zu, time: %f\n", nprimes, (float)(t2 - t1)/CLOCKS_PER_SEC);
 
-    printf("2 ");
-    c_forrange (i, int, 3, 1001, 2) {
-       if (cbits_test(primes, i)) printf("%d ", i);
-    }
+    printf(" 2");
+    for (size_t i = 3; i < 1000; i += 2)
+       if (cbits_test(primes, i>>1)) printf(" %zu", i);
     puts("");
+
     cbits_del(&primes);
 }
 ```
diff --git a/stc/cbits.h b/stc/cbits.h
index d2a309d4..5a0e11aa 100644
--- a/stc/cbits.h
+++ b/stc/cbits.h
@@ -211,13 +211,13 @@ STC_DEF size_t cbits_count(cbits_t s) {
 

 #define _cbits_SETOP(OPR, x) \

     assert(s.size == other.size); \

-    if (s.size == 0) return false; /* ? */ \

     size_t n = s.size >> 6; \

     for (size_t i = 0; i < n; ++i) \

         if ((s._arr[i] OPR other._arr[i]) != x) \

             return false; \

+    if (!(s.size & 63)) return true; \

     uint64_t i = n, m = (1ull << (s.size & 63)) - 1; \

-    return ((s._arr[i] & m) OPR (other._arr[i] & m)) == (x & m)

+    return ((s._arr[i] OPR other._arr[i]) & m) == (x & m)

 

 STC_DEF bool cbits_subset_of(cbits_t s, cbits_t other) { _cbits_SETOP(|, s._arr[i]); }

 STC_DEF bool cbits_disjoint(cbits_t s, cbits_t other) { _cbits_SETOP(&, 0); }