Обсуждение: Bit count

I'd like to use an integer column (16 bits will suffice) to hold a bit-field. I'd like to be able to efficiently count
thenumber of bits set in this field. 

Is there a built-in function call I can use? (I can't find one in the manual).

If not, can anyone recommend the most efficient way within postgres to implement the kind of bit-counting tricks found
at:

http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/
http://graphics.stanford.edu/~seander/bithacks.html

Nathaniel

On Tue, Nov 24, 2009 at 16:47, Nathaniel Trellice <naptrel@yahoo.co.uk> wrote:

[...]
> If not, can anyone recommend the most efficient way within postgres to implement the kind of bit-counting tricks
foundat: 

Perhaps something like this:

CREATE OR REPLACE FUNCTION bitcount(i integer) RETURNS integer AS $$
DECLARE n integer;
DECLARE amount integer;
  BEGIN
    amount := 0;
    FOR n IN 1..16 LOOP
      amount := amount + ((i >> (n-1)) & 1);
    END LOOP;
    RETURN amount;
  END
$$ LANGUAGE plpgsql;


bos=# select bitcount(6);
 bitcount
----------
        2
(1 row)

bos=# select bitcount(7);
 bitcount
----------
        3

bos=# select bitcount(4711);
 bitcount
----------
        7
(1 row)

bos=# select bitcount(1024);
 bitcount
----------
        1
(1 row)


--
- Rikard

On Tue, Nov 24, 2009 at 07:18:00PM +0100, Rikard Bosnjakovic wrote:
> On Tue, Nov 24, 2009 at 16:47, Nathaniel Trellice <naptrel@yahoo.co.uk> wrote:
>
> [...]
> > If not, can anyone recommend the most efficient way within postgres to implement the kind of bit-counting tricks
foundat: 
>
> Perhaps something like this:
>
> CREATE OR REPLACE FUNCTION bitcount(i integer) RETURNS integer AS $$
> DECLARE n integer;
> DECLARE amount integer;
>   BEGIN
>     amount := 0;
>     FOR n IN 1..16 LOOP
>       amount := amount + ((i >> (n-1)) & 1);
>     END LOOP;
>     RETURN amount;
>   END
> $$ LANGUAGE plpgsql;
>
>
> bos=# select bitcount(6);
>  bitcount
> ----------
>         2
> (1 row)
>
> bos=# select bitcount(7);
>  bitcount
> ----------
>         3
>
> bos=# select bitcount(4711);
>  bitcount
> ----------
>         7
> (1 row)
>
> bos=# select bitcount(1024);
>  bitcount
> ----------
>         1
> (1 row)
>
>
> --
> - Rikard
>

You could also setup a lookup table and just select the
bit count from the table. There was also a thread on how
to efficiently count the set bits that concluded with the
posting of a C function that could be used. It all depends
on your need for speed.

Regards,
Ken

On Tue, Nov 24, 2009 at 1:18 PM, Rikard Bosnjakovic
<rikard.bosnjakovic@gmail.com> wrote:
> On Tue, Nov 24, 2009 at 16:47, Nathaniel Trellice <naptrel@yahoo.co.uk> wrote:
>
> [...]
>> If not, can anyone recommend the most efficient way within postgres to implement the kind of bit-counting tricks
foundat: 
>
> Perhaps something like this:
>
> CREATE OR REPLACE FUNCTION bitcount(i integer) RETURNS integer AS $$
> DECLARE n integer;
> DECLARE amount integer;
>  BEGIN
>    amount := 0;
>    FOR n IN 1..16 LOOP
>      amount := amount + ((i >> (n-1)) & 1);
>    END LOOP;
>    RETURN amount;
>  END
> $$ LANGUAGE plpgsql;
>

[snip]
Clever! Here's a pure SQL version I whipped up.. perhaps there's a
more efficient pure SQL way that can avoid the string operations I'm
using :-)

# SELECT num, char_length(replace(num::bit(16)::text, '0', '')) AS
num_set_bits FROM numbers;
 num  | num_set_bits
------+--------------
    6     |            2
    7     |            3
 4711  |            7
 1024  |            1

Josh

On 2009-11-24, Nathaniel Trellice <naptrel@yahoo.co.uk> wrote:
> I'd like to use an integer column (16 bits will suffice) to hold a bit-field. I'd like to be able to efficiently
countthe number of bits set in this field. 
>
> Is there a built-in function call I can use? (I can't find one in the manual).

convert it to a text representation of the binary value use regexp_replace to remove the 0s take the length.

> If not, can anyone recommend the most efficient way within postgres to implement the kind of bit-counting tricks
foundat: 

postgres functions can be written in C (if you have superuser
priviledges) seems like overkill though.

Thanks for all the replies.

I'm giving this a spin, at present. It's based on Rikard's suggestion of using plpgsql script function. Like Jason and
otherhave said, it could be done in a C function (and this was my first inclination), but the hassle of worrying about
linkinglibraries, 32/64-bit installation etc is probably overkill. So this implementation of the 'MIT Hakmem' algorithm
seemedlike a good compromise between efficiency and efficacy: 

CREATE FUNCTION mybitcount(n int4) RETURNS int4 AS $$
  DECLARE tmp int4;
  BEGIN
    tmp = n - ((n >> 1) & 3681400539) - ((n >> 2) & 1227133513);
    RETURN ((tmp + (tmp >> 3)) & 3340530119) % 63;
  END
$$ LANGUAGE plpgsql IMMUTABLE STRICT;


Nathaniel