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

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