Numarare biti setati dintr-un nr. dat

Intrebari despre limbajul C++, standardul C++, STL, OOP in C++ sau alte subiecte nelegate de VisualC++
Post Reply
0ptr
Membru
Membru
Posts: 71
Joined: 01 Feb 2011, 23:27
Judet: Ilfov

Numarare biti setati dintr-un nr. dat

Post by 0ptr » 11 May 2011, 16:57

Cum ati numara nr. de biti setati (1) dintr-un intreg?



User avatar
Marius Bancila
Fondator
Fondator
Posts: 2344
Joined: 11 Jul 2007, 11:45
Judet: Timiş
Location: Timisoara
Contact:

Re: Numarare biti setati dintr-un nr. dat

Post by Marius Bancila » 11 May 2011, 17:17

Vad ca azi e ziua intrebarilor de interviu. Din ce am citit, se pare ca cea mai buna metoda e Hamming weight (sau popcount).

Si asta e codul cu cele mai putine instructiuni http://graphics.stanford.edu/~seander/b ... etParallel:

Code: Select all

int numar_biti_unu(int n)
{
  n = n - ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
Daca citesti acolo, o sa vezi mai multe variante pentru diverse operatii.
Last edited by Marius Bancila on 13 May 2011, 11:38, edited 1 time in total.
Reason: hamming
Marius Bancila
Fondator Codexpert, Microsoft MVP VC++
Site personal | Blog

User avatar
Silviu Ardelean
Senior
Senior
Posts: 1175
Joined: 12 Jul 2007, 09:22
Judet: Timiş
Location: Timisoara
Contact:

Re: Numarare biti setati dintr-un nr. dat

Post by Silviu Ardelean » 11 May 2011, 17:19

Eu propun o varianta mai clasica.

Code: Select all

int counter(int nr)  
{ 
   int i = 0;  
  
   while (0 != nr)  
   { 
	 i += (nr & 1);  
	 nr >>= 1;  
   }  
  
  return i;  
}  

Viorel
Microsoft MVP
Microsoft MVP
Posts: 292
Joined: 13 Jul 2007, 12:26

Re: Numarare biti setati dintr-un nr. dat

Post by Viorel » 11 May 2011, 17:40

Această variantă se bazează pe un tablou cu valori pre-calculate (sau calculate eventual la prima execuţie). Tabloul t de mai jos conţine numărul de biţi setaţi în fiecare octet din intervalul 0..255. Ideea este următoare:

Code: Select all

int NumarBitiSetati(unsigned int v)
{
	static_assert(sizeof(v) * 8 == 32, "Merge numai cu 'int' pe 32 de biţi.");
 
	static const int t[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, ...... }; // TODO: a se completa
 
	return t[v & 0xFF] + t[(v >> 8) & 0xFF] + t[(v >> 16) & 0xFF] + t[(v >> 24) & 0xFF];
}
Ar fi interesantă o comparaţie a performanţei.

Post Reply