Postgres Pro
Downloads
Home   >   mailing lists

What is the algorithm used for counting the set bit (number of ones) of a bitmap/bitarray/betset in postgresql? - Mailing list pgsql-hackers

From Kanarupan Kularatnarajah
Subject What is the algorithm used for counting the set bit (number of ones) of a bitmap/bitarray/betset in postgresql?
Date
Msg-id CAFf4ZT3bVCM+KPT=3zohJMv3d76WhrNQsur=yO=-r3MeBKeCEw@mail.gmail.com
Whole thread Raw
List pgsql-hackers
Tree view

I've come across lookup tables, Hamming weights and Brain Kernighan's Algo. Are they used (combined or separately) in bitmap counting? 

Where can I find the coding and please explain the flow a count function (for a bit counting) via coding rather than the high level architectural diagrams (which I'm aware of). 

I've noted using the below expression to count a particular bits (0 or 1 with minor modification). Could anyone explain at the coding level of postgresql and what algorithms are used?

postgres=> SELECT LENGTH( REPLACE( CAST( B'101000000000000000000010' 
AS TEXT ), '0', ''));  


Regards,
K.Kanarupan
Undergraduate,k
Dept. of Computer Science & Engineering
University of Moratuwa

Mobile:  +94 777 420 179

pgsql-hackers by date:

Previous
From: Kanarupan Kularatnarajah
Date:
Subject: bitset counting as a user defined function in postgresql 9.2?
Next
From: Amit Kapila
Date:
Subject: Re: ALTER SYSTEM SET command to change postgresql.conf parameters (RE: Proposal for Allow postgresql.conf values to be changed via SQL [review])