Fast algorithm to count the number of 1 for binary number

Question

If I have binary number 0111000111111, Is there any fast algorithm to count the number of 1 ?
If 0111000111111 is a string(e.g "0111000111111") Is there any fast algorithm to count the number of 1 in the string?

score 2 · Answer 1 · answered Jun 25 '14 at 20:28

2

A relatively fast way is to precompute a table of the bit counts for all byte values and to sum for the four bytes of the (unsigned) integer.

byte NB[256]= { 0, 1, 1, 2, 1, 2, 2, 3, 1, 1, ... };

N= NB[U & 255] + NB[(U >> 8) & 255] + NB[(U >> 16) & 255] + NB[(U >> 24) & 255];

You can adapt this for different numbers of bits per slice.

answered Jun 25 '14 at 20:28

Sorry,but I couldn't understand this pre-computed table! – Am_I_Helpful Jun 25 '14 at 20:30
1

0 = 00000000 -> 0; 1 = 00000001 -> 1; 2 = 00000010 -> 1; 3 = 00000011 -> 2; 4 = 00000100 -> 1 ... – Jun 25 '14 at 20:31
@YvesDaoust-Ahh,Thanks,+1! – Am_I_Helpful Jun 25 '14 at 20:32

1 Answers1