sqlsql-serverbinarypopulationhammingweight

Hamming weight/population count in 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.


Solution

  • 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