T-SQL 中的汉明权重/人口计数

2022-01-09 00:00:00 binary sql sql-server population hammingweight

我正在寻找一种快速方法来计算 BINARY(1024) 字段的汉明权重/人口计数/1 位的数量".MySQL 有一个 BIT_COUNT 函数可以做类似的事情.我在 T-SQL 中找不到类似的函数?

I'm looking for a fast way to calculate the hamming weight/population count/"the number of 1 bits" of a BINARY(1024) field. MySQL has a BIT_COUNT function that does something like that. I couldn't find a similar function in T-SQL?

或者您是否建议将二进制数据存储在另一种类型的字段中?

Or would you suggest storing the binary data in a field of another type?

如果你不知道我在说什么，这里有一篇关于汉明权重的维基百科文章.

If you don't know what I'm talking about, here's a Wikipedia article about the hamming weight.

推荐答案

您可以使用具有预先计算的汉明权重的辅助表来处理小数字，例如字节，然后相应地拆分值，加入辅助表并获得总和部分汉明权重作为值的汉明权重:

You could use a helper table with precalculated Hamming weights for small numbers, like bytes, then split the value accordingly, join to the helper table and get the sum of partial Hamming weights as the value's Hamming weight:

-- define Hamming weight helper table
DECLARE @hwtally TABLE (byte tinyint, hw int);
INSERT INTO @hwtally (byte, hw) VALUES (0, 0);
INSERT INTO @hwtally (byte, hw) SELECT   1 - byte, 1 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT   3 - byte, 2 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT   7 - byte, 3 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  15 - byte, 4 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  31 - byte, 5 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  63 - byte, 6 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT 127 - byte, 7 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT 255 - byte, 8 - hw FROM @hwtally;

-- calculate
WITH split AS (
  SELECT SUBSTRING(@value, number, 1) AS byte
  FROM master.dbo.spt_values
  WHERE type = 'P' AND number BETWEEN 1 AND LEN(@value)
)
SELECT
  Value = @value,
  HammingWeight = SUM(t.hw)
FROM split s
  INNER JOIN @hwtally t ON s.byte = t.byte

相关文章