Best way to count set bits in Oracle

Question

In order to save space for a very particular use-case in Oracle SQL, I'm experimenting with using a bitmap methodology for representing Boolean state over time (an event did or did not happen on that day), with each bit in a binary number representing yes/no for that day. That way, for example, a 32 bit number would allow me to represent 32 consecutive days of whether something happened each day. I would simply need to count the number of bits that are set (=1) to get the count of days in that 32-day period that the event occurred, without having store a separate dated row for each day.

Here's an example of me testing updating the value each day (rolling off the oldest bit and setting the newest one):

SELECT testbitmap original_bitmap,
       BITAND((testbitmap * POWER(2,/*rolloff the nbr of days since last event*/1)) + /*the event happened today*/1,POWER(2,32)-1) new_bitmap
  FROM (SELECT BIN_TO_NUM(1,1,0,0,1,1,0,0,0,1,1,0,1,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0) testbitmap
          FROM dual)

So far so good. But now I need to query the result, and that means counting the set bits of my resulting bitmap. There isn't an inverse of BIN_TO_NUM that I know of in Oracle. Without using a function that loops through each bit and tests it individually, is there a way to count set bits in Oracle (e.g. the number 9 should result in 2 (1001), whereas the number 7 would result in 3 (0111)? Maybe a mathematical formula the returns the number of 1s required to represent a number in binary?

Answer 1

You can use the Hamming Weight algorithm, in C++ it would be:

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

In Oracle, you can use the function:

CREATE FUNCTION number_of_set_bits32(
  i NUMBER
) RETURN NUMBER DETERMINISTIC
IS
  v NUMBER := i;
  c_max CONSTANT NUMBER := POWER(2, 32);
BEGIN
  v := v - BITAND(TRUNC(v/2), TO_NUMBER('55555555', 'XXXXXXXX'));
  v := MOD(
         BITAND(v, TO_NUMBER('33333333', 'XXXXXXXX'))
         + BITAND(TRUNC(v/4), TO_NUMBER('33333333', 'XXXXXXXX')),
         c_max
       );
  v := BITAND(v + FLOOR(v/16), TO_NUMBER('0F0F0F0F', 'XXXXXXXX'));
  RETURN TRUNC(MOD(v * TO_NUMBER('01010101', 'XXXXXXXX'), c_max) / POWER(2, 24));
END;
/

Then to count your value would be:

SELECT testbitmap AS original_bitmap,
       NUMBER_OF_SET_BITS32(testbitmap)
FROM   (
  SELECT BIN_TO_NUM(1,1,0,0,1,1,0,0,0,1,1,0,1,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0)
           AS testbitmap
  FROM   DUAL
)

Which outputs:

ORIGINAL_BITMAP	NUMBER_OF_SET_BITS32(TESTBITMAP)
3429605376	11

---

You should also be able to create an Oracle function using Java:

CREATE OR REPLACE FUNCTION number_of_set_bits(i NUMBER) RETURN NUMBER DETERMINISTIC
  AS LANGUAGE JAVA NAME 'java.lang.Long.bitCount( long ) return long';
/

Which, for the same SELECT query, gives the same output.

---

64- and 128-bit Numbers:

If you want a 64-bit (or 128) function then double (quadruple) the width of all the hex-strings and change the final divide from 2²⁴ to 2⁵⁶ (2¹²⁰), to get the top 8-bits, as mentioned in the answer linked at the top of this answer:

CREATE FUNCTION number_of_set_bits64(
  i NUMBER
) RETURN NUMBER DETERMINISTIC
IS
  v NUMBER := i;
  c_max CONSTANT NUMBER := POWER(2, 64);
BEGIN
  v := v - BITAND(TRUNC(v/2), TO_NUMBER('5555555555555555', 'XXXXXXXXXXXXXXXX'));
  v := MOD(
         BITAND(v, TO_NUMBER('3333333333333333', 'XXXXXXXXXXXXXXXX'))
         + BITAND(TRUNC(v/4), TO_NUMBER('3333333333333333', 'XXXXXXXXXXXXXXXX')),
         c_max
       );
  v := BITAND(v + FLOOR(v/16), TO_NUMBER('0F0F0F0F0F0F0F0F', 'XXXXXXXXXXXXXXXX'));
  RETURN TRUNC(
    MOD(v * TO_NUMBER('0101010101010101', 'XXXXXXXXXXXXXXXX'), c_max)
    / POWER(2, 56)
  );
END;
/

CREATE FUNCTION number_of_set_bits128(
  i NUMBER
) RETURN NUMBER DETERMINISTIC
IS
  v NUMBER := i;
  c_max CONSTANT NUMBER := POWER(2, 128);
BEGIN
  v := v - BITAND(TRUNC(v/2), TO_NUMBER('55555555555555555555555555555555', 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'));
  v := MOD(
         BITAND(v, TO_NUMBER('33333333333333333333333333333333', 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'))
         + BITAND(TRUNC(v/4), TO_NUMBER('33333333333333333333333333333333', 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX')),
         c_max
       );
  v := BITAND(v + FLOOR(v/16), TO_NUMBER('0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F', 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'));
  RETURN TRUNC(
    MOD(v * TO_NUMBER('01010101010101010101010101010101', 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'), c_max)
    / POWER(2, 120)
  );
END;
/

Or, in Java, for larger numbers you can use java.math.BigInteger.bitCount():

CREATE AND COMPILE JAVA SOURCE NAMED bitutils AS
import java.math.BigDecimal;

public class BitUtils {
  public static Integer bitCount(
    final BigDecimal value
  )
  {
    return value == null ? null : value.toBigInteger().bitCount();
  }
};
/

CREATE OR REPLACE FUNCTION number_of_set_bits_java(i NUMBER) RETURN NUMBER DETERMINISTIC
  AS LANGUAGE JAVA NAME 'BitUtils.bitCount( java.math.BigDecimal ) return java.lang.Integer';
/

fiddle