Geek asks and answers

Hamming weight / population in T-SQL

I am looking for a quick way to calculate the hacking weight / population count / "number 1 bit" field of BINARY (1024). MySQL has a BIT_COUNT function that does something similar. I could not find a similar function in T-SQL?

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

If you don’t know what I'm talking about, here is a Wikipedia article about the weight of hops .

+2
source share
4 answers

You can use the auxiliary table with pre-calculated Hamming weights for small numbers, for example, bytes, then divide the value accordingly, join the helpers table and get the sum of the partial Hamming weights as the value of the 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
+4
source

When you play with a lower value (something like a 16-bit max), the most efficient way to do this using SQL Server is to use a table with all the results calculated and using the join.

My query is accelerated from 30 seconds to 0 seconds, doing such things in a query that should calculate the Hamming weight of a 4-bit value for 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, this is an ugly solution, and it is probably not well suited for a long bit field.

+1
source

I did not find anything special with regard to the weight of the interference, but here is one for the distance from the interference:

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

Here, the distance between the two values ​​is calculated. The interference weight for a single value will be the distance from the interference between this value and an array of zero values.

0
source

I could not find a good way to do this. As a result, I calculated the weight of the hack in Java and periodically updated the number of bits in the database.

0
source

More articles:


All Articles