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 the 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).

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

Search Discussions

  • Rikard Bosnjakovic at Nov 24, 2009 at 6:18 pm
    On Tue, Nov 24, 2009 at 16:47, Nathaniel Trellice wrote:

    [...]
    If not, can anyone recommend the most efficient way within postgres to implement the kind of bit-counting tricks found at:
    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
  • Kenneth Marshall at Nov 24, 2009 at 6:23 pm

    On Tue, Nov 24, 2009 at 07:18:00PM +0100, Rikard Bosnjakovic wrote:
    On Tue, Nov 24, 2009 at 16:47, Nathaniel Trellice wrote:

    [...]
    If not, can anyone recommend the most efficient way within postgres to implement the kind of bit-counting tricks found at:
    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
  • Josh Kupershmidt at Nov 24, 2009 at 7:15 pm

    On Tue, Nov 24, 2009 at 1:18 PM, Rikard Bosnjakovic wrote:
    On Tue, Nov 24, 2009 at 16:47, Nathaniel Trellice wrote:

    [...]
    If not, can anyone recommend the most efficient way within postgres to implement the kind of bit-counting tricks found at:
    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
  • Nathaniel Trellice at Nov 26, 2009 at 2:27 pm
    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 other have said, it could be done in a C function (and this was my first inclination), but the hassle of worrying about linking libraries, 32/64-bit installation etc is probably overkill. So this implementation of the 'MIT Hakmem' algorithm seemed like 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
  • Jasen Betts at Nov 26, 2009 at 11:04 am

    On 2009-11-24, Nathaniel Trellice 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 count the 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 found at:
    postgres functions can be written in C (if you have superuser
    priviledges) seems like overkill though.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppgsql-novice @
categoriespostgresql
postedNov 24, '09 at 3:53p
activeNov 26, '09 at 2:27p
posts6
users5
websitepostgresql.org
irc#postgresql

People

Translate

site design / logo © 2022 Grokbase