1

(Note:- There may be syntax errors in the code i write here)

I have a Table with 2 Fields

CREATE TABLE Traces ( TraceName VARCHAR(100), BlockVector VARCHAR(MAX), NumHits INT);

There are around 1 Millions Entries in the Table.

I want to achieve following things from that table:

1) For each row take a bitwise XOR of BlockVector column with another VARCHAR of same length and store the number of set bits in NumHits column

2) Finding Maximum Value of NumHits column.

For finding XOR in T-SQL , we can use '^' operator. How to find number of set bits.

Any help would be hightly appreciated.

abhinav
  • 527
  • 3
  • 11
  • 24
  • Look at this previously solved problem: http://stackoverflow.com/questions/5916430/hamming-weight-population-count-in-t-sql/5930944#5930944 – krisku Aug 30 '13 at 10:07
  • what data do you have in you BlockVector column? – Roman Pekar Aug 30 '13 at 10:10
  • It is a BitArray, i am storing it as VarBinary(MAX) in the database, it is around 6000 bytes. very large one. – abhinav Aug 30 '13 at 10:11
  • could you provide sample input (with some data about not 6000 by 20 bytes long)? – Roman Pekar Aug 30 '13 at 10:25
  • It is a binary Data of 6000 bytes. How can i send it ? , I will Test it here if you dont mind. Please post suggestions on how to solve this – abhinav Aug 30 '13 at 10:29

1 Answers1

1

The following function can be used to count the number of set bits in an integer:

CREATE FUNCTION dbo.bit_count (@num AS BIGINT)RETURNS INT AS
BEGIN
    DECLARE @msb INT
    SET @msb = 0

    IF @num < 0
    BEGIN -- BIGINT is signed so treat the MSB differently
        SET @msb = 1
        SET @num = 0x7FFFFFFFFFFFFFFF & @num
    END

    SET @num = @num - ((@num / 2) & 0x5555555555555555)
    SET @num = (@num & 0x3333333333333333) + ((@num / 4) & 0x3333333333333333)
    SET @num = (@num + @num / 0x10) & 0x0F0F0F0F0F0F0F0F
    SET @num = @num + @num / 0x100
    SET @num = @num + @num / 0x10000
    SET @num = @num + @num / 0x100000000

    RETURN (@num & 0x3F) + @msb
END

Note: I have not written that function, nor have I tested it. I found it here: http://www.dbforums.com/microsoft-sql-server/1630934-bit-counting.html#post6342950

krisku
  • 3,916
  • 1
  • 18
  • 10
  • Thnx :) , how to find XOR of 2 varBinaries ?? – abhinav Aug 30 '13 at 10:37
  • It would probably be best to create your own function that takes e.g. four bytes from each varbinary, converts them to binary values, performs the XOR operation, counts the remaining bits set, adds the result to a running count and then continues with the next for bytes of each varbinary, etc. The implementation is left as an exercise to the reader.. :) – krisku Aug 30 '13 at 11:05