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

From: Kanarupan Kularatnarajah <kanarupanxiii(at)gmail(dot)com>
To: pgsql-hackers(at)postgresql(dot)org
Subject: What is the algorithm used for counting the set bit (number of ones) of a bitmap/bitarray/betset in postgresql?
Date: 2013-08-25 02:24:16
Message-ID: CAFf4ZT3bVCM+KPT=3zohJMv3d76WhrNQsur=yO=-r3MeBKeCEw@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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

Browse pgsql-hackers by date

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