Oracle 中计算设置位的最佳方法

Question

为了节省 Oracle SQL 中非常特殊的用例的空间，我正在尝试使用位图方法来表示随时间变化的布尔状态（当天发生或未发生事件），每个位都以二进制形式表示代表当天是/否的数字。这样，例如，一个 32 位数字可以让我代表连续 32 天是否每天都发生某事。我只需要计算设置的位数 (=1) 即可获取事件发生的 32 天期间的天数，而无需为每一天存储单独的日期行。

这是我每天测试更新值的示例（滚出最旧的位并设置最新的位）：

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)

到目前为止，一切都很好。但现在我需要查询结果，这意味着计算结果位图的设置位。BIN_TO_NUM据我所知，Oracle 中没有相反的情况。如果不使用循环遍历每个位并单独测试它的函数，是否有一种方法可以对 Oracle 中的设置位进行计数（例如，数字 9 应该导致 2 ( 1001)，而数字 7 将导致 3 ( 0111)？也许是数学公式返回表示二进制数所需的 1 的数量？

Answer 1

您可以使用汉明权重算法，在 C++ 中它将是：

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
}

在Oracle中，可以使用以下函数：

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;
/

那么计算你的价值将是：

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
)

哪个输出：

ORIGINAL_BITMAP	NUMBER_OF_SET_BITS32（TESTBITMAP）
3429605376	11

您还应该能够使用 Java 创建 Oracle 函数：

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

对于相同的SELECT查询，给出相同的输出。

64 位和 128 位数字：

如果您想要 64 位（或 128）函数，则将所有十六进制字符串的宽度加倍（四倍），并将最终除法从 2 ²⁴更改为 2 ⁵⁶ (2 ¹²⁰ )，以获得前 8 位，如下所示在该答案顶部链接的答案中提到：

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;
/

或者，在 Java 中，对于更大的数字，您可以使用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';
/

小提琴