Monday, October 23, 2006

 

The T-SQL Way: Converting Integers to Binary Strings

A post over at Rob Farley's blog on converting integers to binary using Transact-SQL caught my eye and it reminded me of a challenge a fellow developer gave me a few years ago, namely that I couldn't speed up one of the VB functions he had written with the condition that it must still be written in VB. I did, by 3 orders of magnitude!, but that's another story...

My solution is probably not quite as elegant as Rob's CTE solution but I reckon it might be faster and use less memory. In fact there are two very similar function based solutions. One is certainly more readable than it's slightly faster counterpart.

Originally, I used the formula as the basis for a computed column, like so:


CREATE TABLE #t (

intVal int ,

binaryStr AS (

SUBSTRING( '0000000100100011010001010110011110001001101010111100110111101111' , (IntVal / 268435456) * 4 + 1, 4 ) +

SUBSTRING( '0000000100100011010001010110011110001001101010111100110111101111' , ((IntVal / 16777216) & 15) * 4 + 1 , 4 ) +

SUBSTRING( '0000000100100011010001010110011110001001101010111100110111101111' , ((IntVal / 1048576) & 15) * 4 + 1 , 4 ) +

SUBSTRING( '0000000100100011010001010110011110001001101010111100110111101111' , ((IntVal / 65536) & 15) * 4 + 1 , 4 ) +

SUBSTRING( '0000000100100011010001010110011110001001101010111100110111101111' , ((IntVal / 4096) & 15) * 4 + 1 , 4 ) +

SUBSTRING( '0000000100100011010001010110011110001001101010111100110111101111' , ((IntVal / 256) & 15) * 4 + 1 , 4 ) +

SUBSTRING( '0000000100100011010001010110011110001001101010111100110111101111' , ((IntVal / 16) & 15) * 4 + 1 , 4 ) +

SUBSTRING( '0000000100100011010001010110011110001001101010111100110111101111' , (IntVal & 15) * 4 + 1 , 4 )

)

);

-- Test values

insert into #t VALUES (0)

insert into #t VALUES (1)

insert into #t VALUES (2)

insert into #t VALUES (3)

insert into #t VALUES (4)

insert into #t VALUES (15)

insert into #t VALUES (31)

insert into #t VALUES (65)

insert into #t VALUES (127)

insert into #t VALUES (128)

insert into #t VALUES (129)

insert into #t VALUES (65535)

insert into #t VALUES (65536)

insert into #t VALUES (166754132)

insert into #t VALUES (1073741824)

-- int's are signed, max value is therefore, 2^31 - 1 = 2147483647

insert into #t VALUES (2147483647)

select * from #t


The first function version is:

CREATE FUNCTION IntegerToBinaryString(@intval int)

RETURNS char(32)

AS

BEGIN

DECLARE @bincode char(64)

SET @bincode = '0000000100100011010001010110011110001001101010111100110111101111'

RETURN (

SUBSTRING( @bincode, (@IntVal / 268435456) * 4 + 1, 4 ) +

SUBSTRING( @bincode, ((@IntVal / 16777216) & 15) * 4 + 1 , 4 ) +

SUBSTRING( @bincode, ((@IntVal / 1048576) & 15) * 4 + 1 , 4 ) +

SUBSTRING( @bincode, ((@IntVal / 65536) & 15) * 4 + 1 , 4 ) +

SUBSTRING( @bincode, ((@IntVal / 4096) & 15) * 4 + 1 , 4 ) +

SUBSTRING( @bincode, ((@IntVal / 256) & 15) * 4 + 1 , 4 ) +

SUBSTRING( @bincode, ((@IntVal / 16) & 15) * 4 + 1 , 4 ) +

SUBSTRING( @bincode, (@IntVal & 15) * 4 + 1 , 4 )

)

END

GO


This uses a concatenated string of the 4-bit binary string representations of 0 to 15, indexed by the 32-bit input integer broken into 4-bit chunks. You can reduce the number of arithmetic operations still further by creating a combined string of the 256 8-bit combinations:

CREATE FUNCTION IntegerToBinaryString2(@intval int)

RETURNS char(32)

AS

BEGIN

DECLARE @bincode256 char(2048)

SET @bincode256 = '00000000000000010000001000000011 ...'

RETURN (

SUBSTRING( @bincode256, (@IntVal / 16777216) * 8 + 1, 8 ) +

SUBSTRING( @bincode256, ((@IntVal / 65536) & 255) * 8 + 1 , 8 ) +

SUBSTRING( @bincode256, ((@IntVal / 256) & 255) * 8 + 1 , 8 ) +

SUBSTRING( @bincode256, (@IntVal & 255) * 8 + 1 , 8 ) )

END

GO


[Note: I originally posted the whole 2048 characters of @bincode256, but it caused my blog some alignment problems! You can either use the technique of small cranes to build big cranes, using the following T-SQL snippet to call the first function to create the string, and then cut and paste it, OR type it in yourself. Personally, I 'd go with the first suggestion!

DECLARE @i int

DECLARE @res varchar(2048)

SET @i = 0

SET @res = ''

WHILE @i < 256

BEGIN

SET @res = @res + '' + CAST(Substring(dbo.IntegerToBinaryString(@i), 25, 8) as varchar(8))

SET @i = @i + 1

END

PRINT @res

GO


I'm not sure what Rob and Omnibuzz (!) use for their timing harness or test dataset but hopefully, I'll follow up with relative timings.

Rob's was originally inspired by this post.

# posted by Mitch Wheat @ 5:21 pm

0 Comments:

Post a Comment



<< Home
    

Powered by Blogger