Rezolvarea naivă a acestei probleme ar consta în parcurgerea secvenţială a biţilor lui n. În continuare vă prezint această rezolvare:
==code(cpp)|

int count(long n){
  int num = 0;
  for (int i = 0; i < 32; i++)
     if (n & (1 << i)) num++;
  return num;

int count(long n) {
    int num = 0;
    for (int i = 0; i < 32; i++)
        if (n & (1 << i)) num++;
    return num;

}
==

De aici ideea algoritmului:
==code(cpp)|

int count(long n){
   int num = 0;
   if (n)
      while (n &= n - 1) num++;
   return num;

int count(long n) {
    int num = 0;
    if (n)
        do num++; while (n &= n - 1);
    return num;

}
==

Din cele prezentate mai sus se pot determina două metode evidente:
==code(cpp)|

int parity(long n){
  int num = 0;
  for (int i = 0; i < 32; i++)
     if (n & (1 << i)) num ^= 1;
  return num;

int parity(long n) {
    int num = 0;
    for (int i = 0; i < 32; i++)
        if (n & (1 << i)) num ^= 1;
    return num;

}
==
==code(cpp)|

int parity(long n){
   int num = 0;
   if (n)
      while (n &= n - 1) num ^= 1;
   return num;

int parity(long n) {
    int num = 0;
    if (n)
        do num ^= 1; while (n &= n - 1);
    return num;

}
==

Să scriem algoritmul care reiese din acest exemplu, luând în considerare faptul că numărul n este reprezentat pe 32 de biţi:
==code(cpp)|

int parity(long n){
   n = ((0xFFFF0000 & n) >> 16) ^ (n & 0xFFFF);
   n = ((0xFF00 & n) >> 8) ^ (n & 0xFF);
   n = ((0xF0 & n) >> 4) ^ (n & 0xF);
   n = ((12 & n) >> 2) ^ (n & 3);
   n = ((2 & n) >> 1) ^ (n & 1);
   return n;

int parity(long n) {
    n = ((0xFFFF0000 & n) >> 16) ^ (n & 0xFFFF);
    n = ((0xFF00 & n) >> 8) ^ (n & 0xFF);
    n = ((0xF0 & n) >> 4) ^ (n & 0xF);
    n = ((12 & n) >> 2) ^ (n & 3);
    n = ((2 & n) >> 1) ^ (n & 1);
    return n;

}
==

Rezolvarea naivă se comportă bine în medie, deoarece numărul de cicluri până la găsirea unui bit cu valoarea 1 este de obicei mic, dar din cele discutate mai sus putem găsi ceva mai bun.
Asa cum am arătat $n & (n - 1)$ are ca rezultat numărul $n$ din care s-a scăzut cel mai puţin semnificativ bit. Folosind această idee obţinem următoarea funcţie:

==code(cpp)|

int low1(long n){

int low1(long n) {

    return n ^ (n & (n - 1));
}
==

Se observă că aplicând o secvenţă asemănătoare de instrucţiuni cu cea de mai sus putem face ca un număr $n$ să se transforme în alt număr care are un număr de biţi de $1$ egal cu $1$ plus indexul celui mai semnificativ bit cu valoarea $1$ din $n$. De aici algoritmul este următorul...
==code(cpp)|

int indexHigh1(long n){

int indexHigh1(long n) {

    n = n | (n >> 1);
    n = n | (n >> 2);
    n = n | (n >> 4);
    n = n | (n >> 8);
    n = n | (n >> 16);
    return count(n) - 1;

}

==
Pentru ca această metodă să fie eficientă ne trebuie o metodă *count* eficientă.

h3. Rezolvare
==code(cpp)|

int isTwoPower(long n){
    return (n & (n-1) == 0);

int isTwoPower(long n) {
    return ( n & (n - 1) ) == 0 ;

}
==

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $num$, în care $num[i]$ este egal cu numărul de biţi de $1$ din reprezentarea binară a lui $i$. De aici obţinem soluţia...
==code(cpp)|

int count(long n){

int count(long n) {

    return num[n & 0xFFFF] + num[n >> 16];
}
==

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $par$, în care $par[i]$ este egal cu paritatea numărului de biţi de $1$ din reprezentarea binară a lui $i$. De aici obţinem soluţia...
==code(cpp)|

int parity(long n){

int parity(long n) {

    return par[n & 0xFFFF] ^ par[n >> 16];
}
==

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $l$, în care $l[i]$ este egal cu cel mai nesemnificativ bit de $1$ din reprezentarea binară a lui $i$. De aici obţinem soluţia...
==code(cpp)|

int low(long n){

int low(long n) {

    if (l[n & 0xFFFF]) return l[n & 0xFFFF];
    else return l[n >> 16] << 16;
}

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $h$, în care $h[i]$ este egal cu cel mai semnificativ bit de $1$ din reprezentarea binară a lui $i$. De aici obţinem soluţia...
==code(cpp)|

int high(long n){

int high(long n) {

    if (h[n >> 16]) return h[n >> 16] << 16;
    else return h[n & 0xFFFF];
}

char at[maxsize]; // vector de valori logice în care numerele prime vor fi marcate cu 0
int n;

int isPrime(int x){

int isPrime(int x) {

    return (!at[x]) ;
}

void sieve(){

void sieve() {

    int i, j;
    memset(at,0,sizeof(at)) ;
    for (i = 2; i <= maxsize; i++) if (!at[i])

char at[maxsize];
int n;

int isPrime(int x){

int isPrime(int x) {

    return (!at[x]) ;
}

void sieve(){

void sieve() {

    int i, j;
    memset(at,0,sizeof(at));
    for (i = 4; i <= maxsize; i += 2)

La marcarea multiplilor numărului prim $i$ toate numerele până la $i * i$ au fost deja marcate deoarece $i * i$ este cel mai mic număr care nu este divizibil cu numere naturale mai mici sau egale cu $i - 1$. Deci, avem o a treia versiune a programului...
==code(cpp)|

void sieve(){

void sieve() {

    int i, j;
    memset(at,0,sizeof(at));
    for (i = 4; i <= maxsize; i += 2)