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ă.
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))) ;
}
==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
