Skip site navigation (1) Skip section navigation (2)

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

From: Allan Kamau <allank(at)sanbi(dot)ac(dot)za>
To:
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-21 18:58:20
Message-ID: 48ADBACC.20301@sanbi.ac.za (view raw or flat)
Thread:
Lists: pgsql-sql
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
>
>   


In response to

Responses

pgsql-sql by date

Next:From: s.cailletDate: 2008-08-22 09:02:29
Subject: Re: Question on partitioning
Previous:From: Mark RobertsDate: 2008-08-21 18:00:41
Subject: Re: Question on partitioning

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group