Re: lun - Lucky Number

On 16/03/2025 11:15, Marcel Logen wrote:

Richard Heathfield in sci.crypt:
 

On 15/03/2025 19:44, Marcel Logen wrote:

 [...]
 

Okay. In C, ! is the `not' operator.

 I was aware of that. So I thought that the double exclamation
mark was superfluous.
 

0 is false, 1 is true, non-zero is true, but not true is false. So:

                         ^^^^^^^^^^^^^^^^
This is probably the crucial point.

It is.

x = 6;
printf("%d", x); prints 6.
printf("%d", !x); prints 0 because not non-zero is false.
printf("%d", !!x); prints 1 because not not non-zero is true.
>
So !!x maps 0 to 0 and everything else to 1. If you're printing
bits, it's just the job.

 A good trick! So a kind of normalization, AFAICS.

Precisely, yes.

[...]
 

#define BIT_QRY(x,i) ((x[(i)>>3] & (1<<((i)&7)))!=0)
#define BIT_SET(x,i) (x)[(i)>>3]|=(1<<((i)&7))
#define BIT_CLR(x,i) (x)[(i)>>3]&=(1<<((i)&7))^0xFF

[...]

Say i is 77, which is
>
01001101
>
i >> 3 gives us 00001001, or 9.
i & 7 gives us 00000101, or 5.
>
So these macros respectively query, set, or clear bit 5 of byte 9
(counting from x).
>
A somewhat hurried explanation, so feel free to ask further.

 I'll take a closer look at this. For now, your explanation is
good enough for me. Thanks.

I knocked up a quick sieve for you so that you can see the macros being used in another context - here, to tick off compounds (by which I mean non-primes) a la Eratosthenes. (I also fixed a tiny and probably harmless bug in BIT_QRY, where x was insufficiently parenthiprotected.)
#include <stdio.h>
#define BIT_QRY(x,i) (((x)[(i)>>3] & (1<<((i)&7)))!=0)
#define BIT_SET(x,i) (x)[(i)>>3]|=(1<<((i)&7))
#define BIT_CLR(x,i) (x)[(i)>>3]&=(1<<((i)&7))^0xFF
#define MAX 1000
int main(void)
{
   unsigned char sieve[(MAX+7)/8] = {0};
   int base = 2;
   int candidate = 0;
   int count = 0;
   BIT_SET(sieve, 0); /* 0 is not prime */
   BIT_SET(sieve, 1); /* 1 is not prime */
   while(base <= MAX)
   {
     for(candidate = 2 * base; candidate <= MAX; candidate += base)
     {
       BIT_SET(sieve, candidate);
     }
     ++base;
   }
   for(candidate = 0; candidate <= MAX; candidate++)
   {
     if(!BIT_QRY(sieve, candidate))
     {
       ++count;
       printf(" %4d", candidate);
       if(count % 10 == 0)
       {
         putchar('\n');
       }
     }
   }
   putchar('\n');
   printf("%d primes in the range 0-%d.\n", count, MAX);
   return 0;
}
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within