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

Started by Kanarupan Kularatnarajahover 12 years ago1 messageshackers
Jump to latest
#1Kanarupan Kularatnarajah
kanarupanxiii@gmail.com

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