Re: Re: Efficiently determining the number of bits set in the contents of, a VARBIT field

From: Bruce Momjian <bruce(at)momjian(dot)us>
To: Jean-David Beyer <jeandavid8(at)verizon(dot)net>
Cc: pgsql-sql(at)postgresql(dot)org
Subject: Re: Re: Efficiently determining the number of bits set in the contents of, a VARBIT field
Date: 2008-08-12 20:48:51
Message-ID: 200808122048.m7CKmpK21016@momjian.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-sql

Jean-David Beyer wrote:
> TJ O'Donnell wrote:
> > I use a c function, nbits_set that will do what you need.
> > I've posted the code in this email.
> >
> > TJ O'Donnell
> > http://www.gnova.com
> >
> > #include "postgres.h"
> > #include "utils/varbit.h"
> >
> > Datum nbits_set(PG_FUNCTION_ARGS);
> > PG_FUNCTION_INFO_V1(nbits_set);
> > Datum
> > nbits_set(PG_FUNCTION_ARGS)
> > {
> > /* how many bits are set in a bitstring? */
> >
> > VarBit *a = PG_GETARG_VARBIT_P(0);
> > int n=0;
> > int i;
> > unsigned char *ap = VARBITS(a);
> > unsigned char aval;
> > for (i=0; i < VARBITBYTES(a); ++i) {
> > aval = *ap; ++ap;
> > if (aval == 0) continue;
> > if (aval & 1) ++n;
> > if (aval & 2) ++n;
> > if (aval & 4) ++n;
> > if (aval & 8) ++n;
> > if (aval & 16) ++n;
> > if (aval & 32) ++n;
> > if (aval & 64) ++n;
> > if (aval & 128) ++n;
> > }
> > PG_RETURN_INT32(n);
> > }
> >
> >
> >
> >> Hi all,
> >> Am looking for a fast and efficient way to count the number of bits set
> >> (to 1) in a VARBIT field. I am currently using
> >> "LENGTH(REGEXP_REPLACE(CAST(a.somefield_bit_code AS TEXT),'0','','g'))".
> >>
> >> Allan.
> >
> >
> When I had to do that, in days with smaller amounts of RAM, but very long
> bit-vectors, I used a faster function sort-of like this:
>
> static char table[256] = {
> 0,1,1,2,1,2,2,3,1,.....
> };
>
> Then like above, but instead of the loop,
>
> n+= table[aval];
>
>
> You get the idea.

Uh, I was kind of confused by this, even when I saw a full
implementation:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

Actually, this looks even better:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

In response to

Responses

Browse pgsql-sql by date

  From Date Subject
Next Message Emi Lu 2008-08-14 19:07:13 Check a column value not in Array.
Previous Message Christophe 2008-08-08 20:04:53 Re: vacuum in single-user mode