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

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.

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.

--
.~. Jean-David Beyer Registered Linux User 85642.
/V\ PGP-Key: 9A2FC99A Registered Machine 241939.
/( )\ Shrewsbury, New Jersey http://counter.li.org
^^-^^ 20:20:01 up 7 days, 1:08, 4 users, load average: 4.16, 4.15, 4.10

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. +

Thank you TJ and everyone else for the advise and the c code. Today I
did finally return to the 'number of bits set challenge' and managed to
compile and link the nbits c function which went smoothly. However the
function does crash my postgres server installation (8.3.3) with a
segmentation fault each time I call it for example SELECT
nbits_set(B'1101');
My C skills are very sparse and am unable to debug the function, I have
included the C code of this function. Is there something I may have left
out?

#include "postgres.h"
#include "utils/varbit.h"
#include "fmgr.h"
#ifdef PG_MODULE_MAGIC
PG_MODULE_MAGIC;
#endif

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);
}

Allan

Bruce Momjian wrote:
> 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
>
>

All was well with the code below, apologies to all who read my previous
email. The error (an oversight) was on my part. In the "CREATE FUNCTION
..." statement I had FLOAT as the return type instead of INTEGER.
Now the function runs smoothly. Preliminary results show it is orders of
magnitude faster than the LENGTH(REGEXP(CAST(myVarBit AS
TEXT),'0','','g')) solution.
Thanks again TJ and the rest of the team.

Allan

Allan Kamau wrote:
> Thank you TJ and everyone else for the advise and the c code. Today I
> did finally return to the 'number of bits set challenge' and managed
> to compile and link the nbits c function which went smoothly. However
> the function does crash my postgres server installation (8.3.3) with a
> segmentation fault each time I call it for example SELECT
> nbits_set(B'1101');
> My C skills are very sparse and am unable to debug the function, I
> have included the C code of this function. Is there something I may
> have left out?
>
>
>
> #include "postgres.h"
> #include "utils/varbit.h"
> #include "fmgr.h"
> #ifdef PG_MODULE_MAGIC
> PG_MODULE_MAGIC;
> #endif
>
> 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);
> }
>
> Allan
>
> Bruce Momjian wrote:
>> 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
>>
>>
>>
>
>

Hi all,
I am now looking for a function to return the position of the first
position of the left most set bit. And optionally another to return the
position of the right most set bit.

I have been looking at
"http://graphics.stanford.edu/~seander/bithacks.html#OperationCounting"
but it seems it will take me a while to figure out bit manipulation.

Allan.

Allan Kamau wrote:
> All was well with the code below, apologies to all who read my
> previous email. The error (an oversight) was on my part. In the
> "CREATE FUNCTION ..." statement I had FLOAT as the return type instead
> of INTEGER.
> Now the function runs smoothly. Preliminary results show it is orders
> of magnitude faster than the LENGTH(REGEXP(CAST(myVarBit AS
> TEXT),'0','','g')) solution.
> Thanks again TJ and the rest of the team.
>
> Allan
>
> Allan Kamau wrote:
>> Thank you TJ and everyone else for the advise and the c code. Today I
>> did finally return to the 'number of bits set challenge' and managed
>> to compile and link the nbits c function which went smoothly. However
>> the function does crash my postgres server installation (8.3.3) with
>> a segmentation fault each time I call it for example SELECT
>> nbits_set(B'1101');
>> My C skills are very sparse and am unable to debug the function, I
>> have included the C code of this function. Is there something I may
>> have left out?
>>
>>
>>
>> #include "postgres.h"
>> #include "utils/varbit.h"
>> #include "fmgr.h"
>> #ifdef PG_MODULE_MAGIC
>> PG_MODULE_MAGIC;
>> #endif
>>
>> 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);
>> }
>>
>> Allan
>>
>> Bruce Momjian wrote:
>>> 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
>>>
>>>
>>>
>>
>>
>
>

Seems I have a solution based on the code TJ had provided for counting
the bits sets, for those interested below are the two functions.

#include "postgres.h"
#include "utils/varbit.h"
#include "fmgr.h"
#ifdef PG_MODULE_MAGIC
PG_MODULE_MAGIC;
#endif

PG_FUNCTION_INFO_V1(last_bit_set);
Datum
last_bit_set(PG_FUNCTION_ARGS)
{
/* position of last set bit of a bitstring? */
int n=0;
VarBit *a = PG_GETARG_VARBIT_P(0);
int i;
unsigned char *ap = VARBITS(a);
unsigned char aval;
int b=0;
int byte_cnt=0;
int last_bit_set_position=0;

for(i=0;i<VARBITBYTES(a);++i){
aval=*ap;++ap;
if(aval&128)
{
++n;
b=(8*byte_cnt)+1;
}
if(aval&64)
{
++n;
b=(8*byte_cnt)+2;
}
if(aval&32)
{
++n;
b=(8*byte_cnt)+3;
}
if(aval&16)
{
++n;
b=(8*byte_cnt)+4;
}
if(aval&8)
{
++n;
b=(8*byte_cnt)+5;
}
if(aval&4)
{
++n;
b=(8*byte_cnt)+6;
}
if(aval&2)
{
++n;
b=(8*byte_cnt)+7;
}
if(aval&1)
{
++n;
b=(8*byte_cnt)+8;
}
++byte_cnt;
}
last_bit_set_position=b;
PG_RETURN_INT32(last_bit_set_position);
}

#include "postgres.h"
#include "utils/varbit.h"
#include "fmgr.h"
#ifdef PG_MODULE_MAGIC
PG_MODULE_MAGIC;
#endif

PG_FUNCTION_INFO_V1(first_bit_set);
Datum
first_bit_set(PG_FUNCTION_ARGS)
{
/* position of first set bit of a bitstring? */
int n=0;
VarBit *a = PG_GETARG_VARBIT_P(0);
int i;
unsigned char *ap = VARBITS(a);
unsigned char aval;
int b=0;
int byte_cnt=0;
int first_bit_set_position=0;

for(i=0;b==0&&i<VARBITBYTES(a);++i){
aval=*ap;++ap;
if(aval&128)
{
++n;
b=1;
break;
}
if(aval&64)
{
++n;
b=2;
break;
}
if(aval&32)
{
++n;
b=3;
break;
}
if(aval&16)
{
++n;
b=4;
break;
}
if(aval&8)
{
++n;
b=5;
break;
}
if(aval&4)
{
++n;
b=6;
break;
}
if(aval&2)
{
++n;
b=7;
break;
}
if(aval&1)
{
++n;
b=8;
break;
}
++byte_cnt;
}
if(b>0)
first_bit_set_position=(8*byte_cnt)+b;
else
first_bit_set_position=0;
PG_RETURN_INT32(first_bit_set_position);
}

Allan.

On Thu, Mar 12, 2009 at 2:53 PM, Allan Kamau <allank(at)sanbi(dot)ac(dot)za> wrote:
> Hi all,
> I am now looking for a function to return the position of the first position
> of the left most set bit. And optionally another to return the position of
> the right most set bit.
>
> I have been looking at
> "http://graphics.stanford.edu/~seander/bithacks.html#OperationCounting" but
> it seems it will take me a while to figure out bit manipulation.
>
> Allan.
>
> Allan Kamau wrote:
>>
>> All was well with the code below, apologies to all who read my previous
>> email. The error (an oversight) was on my part. In the "CREATE FUNCTION ..."
>> statement I had FLOAT as the return type instead of INTEGER.
>> Now the function runs smoothly. Preliminary results show it is orders of
>> magnitude faster than the LENGTH(REGEXP(CAST(myVarBit AS TEXT),'0','','g'))
>> solution.
>> Thanks again TJ and the rest of the team.
>>
>> Allan
>>
>> Allan Kamau wrote:
>>>
>>> Thank you TJ and everyone else for the advise and the c code. Today I did
>>> finally return to the 'number of bits set challenge' and managed to compile
>>> and link the nbits c function which went smoothly. However the function does
>>> crash my postgres server installation (8.3.3) with a segmentation fault each
>>> time I call it for example SELECT nbits_set(B'1101');
>>> My C skills are very sparse and am unable to debug the function, I have
>>> included the C code of this function. Is there something I may have left
>>> out?
>>>
>>>
>>>
>>> #include "postgres.h"
>>> #include "utils/varbit.h"
>>> #include "fmgr.h"
>>> #ifdef PG_MODULE_MAGIC
>>> PG_MODULE_MAGIC;
>>> #endif
>>>
>>> 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);
>>> }
>>>
>>> Allan
>>>
>>> Bruce Momjian wrote:
>>>>
>>>> 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
>>>>
>>>>
>>>
>>>
>>
>>
>
>