Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern!

Archives

July 2003

August 2003

October 2003

November 2003

December 2003

March 2004

April 2004

May 2004

July 2004

August 2004

September 2004

November 2004

March 2005

April 2005

May 2005

June 2005

July 2005

August 2005

September 2005

October 2005

November 2005

December 2005

January 2006

February 2006

March 2006

April 2006

May 2006

June 2006

July 2006

August 2006

September 2006

October 2006

November 2006

December 2006

January 2007

February 2007

March 2007

April 2007

May 2007

June 2007

July 2007

August 2007

September 2007

October 2007

November 2007

December 2007

January 2008

February 2008

March 2008

April 2008

May 2008

June 2008

July 2008

August 2008

October 2008

November 2008

December 2008

January 2009

March 2009

April 2009

May 2009

June 2009

July 2009

August 2009

November 2009

December 2009

March 2010

April 2010

May 2010

June 2010

July 2010

October 2010

November 2010

April 2011

May 2011

August 2011

September 2011

October 2011

November 2011

November 2012

June 2013

January 2014

May 2015

Current Posts

July 2003

August 2003

October 2003

November 2003

December 2003

March 2004

April 2004

May 2004

July 2004

August 2004

September 2004

November 2004

March 2005

April 2005

May 2005

June 2005

July 2005

August 2005

September 2005

October 2005

November 2005

December 2005

January 2006

February 2006

March 2006

April 2006

May 2006

June 2006

July 2006

August 2006

September 2006

October 2006

November 2006

December 2006

January 2007

February 2007

March 2007

April 2007

May 2007

June 2007

July 2007

August 2007

September 2007

October 2007

November 2007

December 2007

January 2008

February 2008

March 2008

April 2008

May 2008

June 2008

July 2008

August 2008

October 2008

November 2008

December 2008

January 2009

March 2009

April 2009

May 2009

June 2009

July 2009

August 2009

November 2009

December 2009

March 2010

April 2010

May 2010

June 2010

July 2010

October 2010

November 2010

April 2011

May 2011

August 2011

September 2011

October 2011

November 2011

November 2012

June 2013

January 2014

May 2015

Current Posts

Monday, April 11, 2005

Puzzle of the Week: select count(*) on bit vectors
Recently I mentioned that counting the number of set (a.k.a on, 1) bits in a bit vector is fast. Well, that's definitely not true. This puzzle is about that problem. A naive approach is this C function:

I want to see how much one can speed up this code. Valueable responses would include code, statistics, and theoretical analysis. Assume a 32 or 64-bit machine.

I've got a quite interesting idea about that myself, not sure how it does in reality. BTW, like the sample code above, assume for simplicity that you can trash the array in place.

Submit your solutions through comment system or via email (preferrably) before Sunday April 17, 2005.

int

count_bits_naive (unsigned char *buf, int len)

{

int n = 0;

for (; len > 0; len--, buf++)

for (; *buf; *buf >>= 1)

n += *buf & 1;

return n;

}

I want to see how much one can speed up this code. Valueable responses would include code, statistics, and theoretical analysis. Assume a 32 or 64-bit machine.

I've got a quite interesting idea about that myself, not sure how it does in reality. BTW, like the sample code above, assume for simplicity that you can trash the array in place.

Submit your solutions through comment system or via email (preferrably) before Sunday April 17, 2005.

Comments:

Links to this post:

<< Archive

<< Home

I would precompute the number of set bits for every 8-bit value and store it in a 256-byte array:

char a[256] = {0};

for (int i = 1; i < 256; ++i)

a[i] = a[i/2] + i%2;

int n = 0;

for (; len > 0, --len)

n += a[*buf++];

return n;

It is also possible to precompute more values at the expense of higher memory usage.

char a[256] = {0};

for (int i = 1; i < 256; ++i)

a[i] = a[i/2] + i%2;

int n = 0;

for (; len > 0, --len)

n += a[*buf++];

return n;

It is also possible to precompute more values at the expense of higher memory usage.

what if we want to count numner of 0's? I am new to computer science and I was wondering if the same algorithm will work for 0's or not. (please mention a book about counting various numbers in datastructures if possible)

#define TRESULT long

BYTE f(TRESULT vect)

{

TRESULT lululu;

BYTE sum=0;

for(lululu=1;lululu;lululu<<=1)

if(vect&lululu)

sum++;

//for(;;)love(!); I don't have much memory, but my CPU is fast!

return sum;

}

BYTE f(TRESULT vect)

{

TRESULT lululu;

BYTE sum=0;

for(lululu=1;lululu;lululu<<=1)

if(vect&lululu)

sum++;

//for(;;)love(!); I don't have much memory, but my CPU is fast!

return sum;

}

Thanks to everybody who commented. Indeed using a precomputed table is the fastet way. But Xet, you really want to use an static table man. For the database search results bit vector that is sparse, a word-wide check for zero words can speed up by a constant factor still.

But on the smart solutions, what I was looking for was a way that takes time proportional to the number of set bits in a word, not the number of bits in the word, and indeed Brian Kernighan's method does exactly that. Thanks to Owrdac for the BitHacks link. You can find it here.

Thanks for the anonymous love letter h.

And finally, my rather dull idea was: If you have two bit vectors A and B, then C=(A|B) and D=(A&B) are two new vectors such that n(A)+n(B) == n(C)+n(D) where n(X) is the number of set bits in X. Moreover, n(C) >= max(n(A), n(B)), and n(D) <= min(n(A), n(B)). So if you have cheap operations for bitwise or, bitwise and, check for all-zero, and check for all-one on vectors, we could use this algorithm: given vector X, if X is all-zero or all-one, return with the answer, otherwise break X into X1 and X2,*boost* the number of set bits towards all-one and all-zero, by replacing X1 and X2 with (X1|X2) and (X1&X2) and recurse. Apparently this is of no use in Turing-equivalent machines we have today, but maybe in some quantum mechanics computers in the future ;).

Post a Comment
But on the smart solutions, what I was looking for was a way that takes time proportional to the number of set bits in a word, not the number of bits in the word, and indeed Brian Kernighan's method does exactly that. Thanks to Owrdac for the BitHacks link. You can find it here.

Thanks for the anonymous love letter h.

And finally, my rather dull idea was: If you have two bit vectors A and B, then C=(A|B) and D=(A&B) are two new vectors such that n(A)+n(B) == n(C)+n(D) where n(X) is the number of set bits in X. Moreover, n(C) >= max(n(A), n(B)), and n(D) <= min(n(A), n(B)). So if you have cheap operations for bitwise or, bitwise and, check for all-zero, and check for all-one on vectors, we could use this algorithm: given vector X, if X is all-zero or all-one, return with the answer, otherwise break X into X1 and X2,

Links to this post:

<< Archive

<< Home