Results 1 to 8 of 8

Thread: bit counting

  1. #1
    Join Date
    Nov 2005
    Posts
    9

    Question Unanswered: bit counting

    Hello,

    Is there a function similar to the MySQL BIT_COUNT() on 64-bit values?
    If not, what would be the most efficient way to implement it in Transact-SQL?

    Thank you!

  2. #2
    Join Date
    May 2004
    Location
    Seattle
    Posts
    1,313
    don't think there's such a function. you could implement it yourself using bitwise and operator: &

  3. #3
    Join Date
    Nov 2005
    Posts
    9

    Exclamation Solved

    I implemented it using T-SQL and as an extended stored procedure (C++ DLL). Turns out the T-SQL version was fastr, probably due to the overhead of the interop invoked.

    In case you run into a similar problem, this is what we will be using:
    Code:
    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
    For an explanation of the algorithm, see here.

  4. #4
    Join Date
    May 2004
    Location
    Seattle
    Posts
    1,313
    you could update the wikipedia article with your tsql sol'n

  5. #5
    Join Date
    Apr 2007
    Posts
    183
    Code:
    CREATE FUNCTION dbo.fnBitCount
    (
    	@Num BIGINT
    )
    RETURNS TINYINT
    AS
    BEGIN
    	DECLARE	@Bits CHAR(256),
    		@Yak BINARY(8)
    
    	SELECT	@Bits = '0112122312232334122323342334344512232334233434452334344534454556122323342334344523343445344545562334344534454556344545564556566712232334233434452334344534454556233434453445455634454556455656672334344534454556344545564556566734454556455656674556566756676778',
    		@Yak = @Num
    
    	RETURN	0
    		+ SUBSTRING(@Bits, SUBSTRING(@Yak, 1, 1) + 1, 1)
    		+ SUBSTRING(@Bits, SUBSTRING(@Yak, 2, 1) + 1, 1)
    		+ SUBSTRING(@Bits, SUBSTRING(@Yak, 3, 1) + 1, 1)
    		+ SUBSTRING(@Bits, SUBSTRING(@Yak, 4, 1) + 1, 1)
    		+ SUBSTRING(@Bits, SUBSTRING(@Yak, 5, 1) + 1, 1)
    		+ SUBSTRING(@Bits, SUBSTRING(@Yak, 6, 1) + 1, 1)
    		+ SUBSTRING(@Bits, SUBSTRING(@Yak, 7, 1) + 1, 1)
    		+ SUBSTRING(@Bits, SUBSTRING(@Yak, 8, 1) + 1, 1)
    END

  6. #6
    Join Date
    Nov 2005
    Posts
    9
    Thanks Peso, that was 5% faster.

  7. #7
    Join Date
    Apr 2007
    Posts
    183

    Ok, it must be a Friday 13th thingy

    Because I get 15%-20% faster times today with SQL Profiler.

    Code:
    
    		CPU	Duration		CPU	Duration
    		------	--------		------	--------
    Alexoren	17 703	19 975		Peso	14 657	15 506
    Alexoren	17 422	19 595		Peso	14 609	15 673
    Alexoren	17 469	19 712		Peso	14 875	15 656
    Alexoren	17 672	19 742		Peso	15 016	15 529
    Alexoren	17 360	19 484		Peso	14 515	15 575
    Alexoren	17 390	19 598		Peso	15 000	15 575
    Alexoren	17 391	19 776		Peso	14 859	15 774
    Alexoren	17 172	19 947		Peso	15 047	15 725

  8. #8
    Join Date
    Nov 2005
    Posts
    9
    I confess that I did not profile it, just ran a loop of 100,000 iterations and checked the current time before and after.

    Also, configuration differences may have affected the result.

    Nonetheless, faster is faster.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •