Nu exista diferente intre titluri.
Diferente intre continut:
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){
return n ^ (n & (n - 1));
int low1(long n) {
return n ^ (n & (n - 1));
}
==
==code(cpp)|
int high1(long n) {
long num = 0;
if (!n) return -1;
if (0xFFFF0000 & n) {
n = (0xFFFF0000 & n)>>16;
num += 16;
}
if (0xFF00 & n) {
n = (0xFF00 & n) >> 8;
num += 8;
}
if (0xF0 & n) {
n = (0xF0 & n) >> 4;
num += 4;
}
if (12 & n) {
n = (12 & n) >> 2;
num += 2;
}
if (2 & n) {
n = (2 & n) >> 1;
num += 1;
}
return 1 << num;
long num = 0;
if (!n) return -1;
if (0xFFFF0000 & n) {
n = (0xFFFF0000 & n)>>16;
num += 16;
}
if (0xFF00 & n) {
n = (0xFF00 & n) >> 8;
num += 8;
}
if (0xF0 & n) {
n = (0xF0 & n) >> 4;
num += 4;
}
if (12 & n) {
n = (12 & n) >> 2;
num += 2;
}
if (2 & n) {
n = (2 & n) >> 1;
num += 1;
}
return 1 << num;
}
==
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){
n = n | (n >> 1);
n = n | (n >> 2);
n = n | (n >> 4);
n = n | (n >> 8);
n = n | (n >> 16);
return count(n) - 1;
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ă.
bq. Să se determine dacă $n$ este o putere a lui 2 (întrebare interviu Microsoft).
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){
return num[n & 0xFFFF] + num[n >> 16];
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){
return par[n & 0xFFFF] ^ par[n >> 16];
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){
if (l[n & 0xFFFF]) return l[n & 0xFFFF];
else return l[n >> 16] << 16;
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){
if (h[n >> 16]) return h[n >> 16] << 16;
else return h[n & 0xFFFF];
int high(long n) {
if (h[n >> 16]) return h[n >> 16] << 16;
else return h[n & 0xFFFF];
}
==
==code(cpp)|
int indexHigh(long n) {
if (iH[n >> 16] != -1) return iH[n >> 16] + 16;
else return iH[n & 0xFFFF];
if (iH[n >> 16] != -1) return iH[n >> 16] + 16;
else return iH[n & 0xFFFF];
}
==
define maxsize 10000000
char at[maxsize]; // vector de valori logice în care numerele prime vor fi marcate cu 0
int n;
int isPrime(int x){
return (!at[x]) ;
int isPrime(int x) {
return (!at[x]) ;
}
void sieve(){
int i, j;
memset(at,0,sizeof(at)) ;
for (i = 2; i <= maxsize; i++)
if (!at[i])
for (j = i + i; j <= maxsize; j += i)
at[j]=1; //marcam toti multipli lui i ca fiind numere prime
void sieve() {
int i, j;
memset(at,0,sizeof(at)) ;
for (i = 2; i <= maxsize; i++) if (!at[i])
for (j = i + i; j <= maxsize; j += i)
at[j] = 1; // marcăm toţi multipli lui i ca fiind numere prime
}
==
==code(cpp)|
#define maxsize 10000000
char at[maxsize];
int n;
int isPrime(int x){
return (!at[x]) ;
int isPrime(int x) {
return (!at[x]) ;
}
void sieve(){
int i, j;
memset(at,0,sizeof(at));
for (i = 4; i <= maxsize; i += 2)
at[i] = 1;
for (i = 3; i <= maxsize; i += 2)
if (!at[i])
for (j = i + i + i; j <= maxsize; j += i + i)
at[j] = 1;
void sieve() {
int i, j;
memset(at,0,sizeof(at));
for (i = 4; i <= maxsize; i += 2)
at[i] = 1;
for (i = 3; i <= maxsize; i += 2) if (!at[i])
for (j = i + i + i; j <= maxsize; j += i + i)
at[j] = 1;
}
==
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(){
int i, j;
memset(at,0,sizeof(at));
for (i = 4; i <= maxsize; i += 2)
at[i] = 1;
for (i = 3; i <= maxsize; i += 2)
if (!at[i])
for (j = i * i; j <= maxsize; j += i + i)
at[j] = 1;
void sieve() {
int i, j;
memset(at,0,sizeof(at));
for (i = 4; i <= maxsize; i += 2)
at[i] = 1;
for (i = 3; i <= maxsize; i += 2) if (!at[i])
for (j = i * i; j <= maxsize; j += i + i)
at[j] = 1;
}
==
==code(cpp)|
#define maxsize 10000000
char at[maxsize/16];
char at[maxsize / 16];
int n;
int isPrime(int x) {
if (!(x & 1))
if (x==2) return 0 ;
else return 1 ;
else return (at[((x - 3) >> 1) >> 8] &
(1 << (((x - 3) >> 1) & 7))) ;
if (!(x & 1))
if (x == 2) return 0 ;
else return 1 ;
else return (at[((x - 3) >> 1) >> 8] & (1 << (((x - 3) >> 1) & 7))) ;
}
void sieve() {
int i, j;
memset(at, 0, sizeof(at)) ;
for (i = 3; i <= maxsize; i += 2)
if (!at[((i - 3) >> 1) >> 8] &
(1 << (((i - 3) >> 1) & 7)))
for (j=i * i ; j <= maxsize ; j += i + i)
at[((i - 3) >> 1) >> 8] |=
(1 << (((i - 3) >> 1) & 7))) ;
int i, j;
memset(at, 0, sizeof(at)) ;
for (i = 3; i <= maxsize; i += 2)
if (!at[((i - 3) >> 1) >> 8] & (1 << (((i - 3) >> 1) & 7)))
for (j = i * i ; j <= maxsize ; j += i + i)
at[((i - 3) >> 1) >> 8] |= (1 << (((i - 3) >> 1) & 7))) ;
}
==
h2. Concluzie
Asemenea optimizări ca şi cele prezentate în cadrul acestui articol se pot dovedi foarte utile în unele cazuri, dar ele fac
programul ilizibil, tocmai din acest motiv, asemenea trucuri trebuie aplicate numai în locurile critice ale codurilor sursă pentru a
duce la o creştere semnificativă de viteză a aplicaţiilor şi trebuie documentate foarte bine, mai ales dacă se doreşte sau este necesar ca alt programator să poată lucra cu codul respectiv mai târziu.
Asemenea optimizări ca şi cele prezentate în cadrul acestui articol se pot dovedi foarte utile în unele cazuri, dar ele fac programul ilizibil, tocmai din acest motiv, asemenea trucuri trebuie aplicate numai în locurile critice ale codurilor sursă pentru a duce la o creştere semnificativă de viteză a aplicaţiilor şi trebuie documentate foarte bine, mai ales dacă se doreşte sau este necesar ca alt programator să poată lucra cu codul respectiv mai târziu.
h2(#bibliografie). Bibliografie
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
