Hamming weight/population count in T-SQL

Question

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.

Teamwork

weblogs.sqlteam.com/jeffs/archive/2007/05/09/60197.aspx – Dartmouth

This might be a job for a CLR function. Also, you've probably considered this, but if your count of unique binary values is thousands not millions, you could create a table to store the pop for each value after it's been calculated the first time. Or store it in your main table, since all you need is a SMALLINT. – Seignior

Answer 1

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

Grolier

Perfect! Thanks. Didn't know about spt_values before. – Teamwork

@Simon: Here's some useful info for a start: #4274223 – Grolier

Answer 2

When you are playing with smaller value (something like 16 bit max), The most efficient way to do it with SQL Server is using an Table with all result calculated and using a join.

I have speed up a query from 30 sec to 0 sec by doing this kind of thing on a query which should calculate Hamming Weight of a 4 bit value on 17'000 rows .

WITH HammingWeightHelper AS (
        SELECT  x, Fx 
        FROM (VALUES(0,0),(1,1),(2,1),(3,2),
                    (4,1),(5,2),(6,2),(7,3),
                    (8,1),(9,2),(10,2),(11,3),
                    (12,2),(13,3),(14,3),(15,4)) AS HammingWeight(x, Fx)
    )
SELECT HammingWeight.Fx As HammingWeight, SomeTable.Value As bitField
FROM   SomeTable INNER JOIN
       HammingWeightHelper ON HammingWeightHelper.x = SomeTable.Value 

Of course it is an ugly solution and it probably won't suit well for long bit field.

Shon

Answer 3

SQL Server, as of SQL Server 2022 CTP 2.1, supports BIT_COUNT(). The documentation is here.

Lagrange

Answer 4

Didn't find anything specifically about hamming weight, but here's one for hamming distance:

create function HamDist(@value1 char(8000), @value2 char(8000))
returns int
as
begin
    declare @distance int
    declare @i int
    declare @len int

    select @distance = 0,
           @i =1,
           @len = case when len(@value1) > len(@value2)
                       then len(@value1)
                       else len(@value2) end

    if (@value1 is null) or (@value2 is null)
        return null

    while (@i <= @len)
        select @distance = @distance +
                           case when substring(@value1,@i,1) != substring(@value2,@i,1)
                                then 1
                                else 0 end,
               @i = @i +1

    return @distance
end

This computes the hamming distance between two values. The hamming weight of a single value would be the hamming distance between that value and an array of zero-values.

Infrared

Thanks for the reply. It's the same algorithm that @Dartmouth already posted. However the implementation is not exactly fast. I'd have to convert the field to a CHAR first (similar to support.microsoft.com/kb/104829) and then call this routine. Isn't there something that computes the hamming distance at least byte-wise? – Teamwork

Answer 5

I couldn't find a good way to do it. In the end I calculated the hamming weight in Java and periodically update the bit counts in the database.

Teamwork