Skip to main content

Bitwise Sieve w/ code sample

Sieve of Eratosthenes is explained HERE
Bitwise sieve is an optimized implementation of  Sieve of Eratosthenes. It does the same thing but more memory efficient because it uses logic operations( &,|,>>,<< ) on binary numbers.

In normal implementation, we use an array as flag to check if a number is prime or not.we know index of an array ( i.e  myarray[n]  ) is 32 bit long. If an array is 10 index long, that it has 32x10(=320) bits.  We use bits of that array as flag. that way we can flag numbers upto 320 as prime or not prime. i.e, how to check the flag status of 51 in myarray[ n ] ? We'll divide 5 by 32, that will give us the index number of the certain bit, then we'll mod 5 by 32, that will give us the certain bit position to check for 0 or 1. Remember bit positions are defined from right to left, starting from 0. Meaning LST = 0 and MST = 31.
So we need to define two functions, one to set that certain bit as 0 or 1, another to check if  bit is 0 or 1.

#define check(arr,n) ( (arr[n/32]>>(n%32))&1 )
#define sett(arr,n) ( arr[n/32] = arr[n>>5] | (1<<(n%32) ))
* I've used macros, but you can write the same code in functions if you want.

CHECK: now in case of 51, (51/32)= 1, so the the bit flag is index 1. the bit position is (51%32)=19.
this means we'll have to check 19th bit of myarray[1] . To understand the next part, you need to know bit operation and bit masking.

BITWISE OPS | BITMASKING

assuming you know bitwise operations, we right shifted myarray[1] 19 times ( myarray[1] >>19 ) and then performed AND operation to see if the bit is 0 or 1. The latter is a bitmask.

SETT: we use same procedure to find the index number and bit position. Then set that bit as we want by another bitmask.

sample:


#include<bits/stdc++.h> using namespace std; #define MAX 46340                        // to find primes from 2 to 46340 #define MAXh 216                          // sqrt of 46340 #define check(arr,n) ( (arr[n/32]>>(n%32))&1 ) #define sett(arr,n) ( arr[n/32] = arr[n>>5] | (1<<(n%32) )) unsigned int prime[100000], flag[MAX/32]; void sieve() {     unsigned int i,j,k,id=0;     for(i=3;i<=MAXh;i+=2)     {         if(!check(flag,i))         {             for(j=i*i;j<=MAX;j+=i)             {                 sett(flag,j);             }         }     }
    prime[id++]=2;     for(i=3;i<=MAX;i+=2)     {         if(!check(flag,i))  prime[id++]=i;     } }
If there's any wrong information or explanation, please let me know.

Comments

Popular posts from this blog

SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 } Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } A node contains-  [ START & END is a node's segment limit ] Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous) Suffix is the maximum sum ending at END, start can be anywhere. There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix   (which will make the suffix contiguous). Sum : leftChild's sum + rightChild's sum. MAX Maximum of  -  prefix (result is in the node, starts from START but doesn't end in END ) suffix  (result is in the node, doesn't start from START but surely ends in END ) leftChild's max ( result is in left ...

Minimum moves for balancing brackets

You’re given a non-empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition of being stable is as follows: An empty string is stable. If S is stable, then {S} is also stable. If S and T are both stable, then ST (the concatenation of the two) is also stable. All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{. The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa. Solution Heuristics: Traverse the string. When the number of opening braces( { ) matches the number of closing braces ( } ), the string is balanced. Else it's not balanced. So count both of them. Make a list. Insert only opening braces. If a closing brace is found delete one brace( if the size of the list is > 0 ) from the list. Because they would make a pair. If the list is empty then we'll conve...