A Scenario to Ponder #5
This should be quite simple. But, I would like to find the best approach to this problem.
The question is to get the binary values for positive integers.
Lets take this table called numbers that has one column called id holding positive integer values. Now, I need to write a query (or set of queries) to select from the table "numbers" and return me the id and the binary value of that id.
Some points to note:
1. The table can have any number of rows.
2. The ids can be in random order with gaps in between.
My solution is written for SQL Server 2005. You may implement it in SQL Server 2000 or 2005. If the solution is in SQL Server 2000, then I am really looking forward to see it.
Here is an example of the output for the table having 4 numbers
id bin
543080 10000100100101101000
667997 10100011000101011101
815717 11000111001001100101
901825 11011100001011000001
Posts
7 comments:
:) Nice question.
Assuming my nums0 table (which starts at 0 rather than 1).
--First populate my nums_bin table - values which are going to be converted to binary
select num
into dbo.nums_bin
from nums0
where num in (543080,667997,815717,901825);
--Now use a CTE to recursively go through my nums0 table, extending the binval field each time...
with ctebins as
(select num as num_orig, num as working_level, cast('' as varchar(max)) as binval
from nums_bin
union all
select c.num_orig, n.num, cast(c.working_level % 2 as varchar(max)) + c.binval
from nums0 n
join
ctebins c
on n.num = c.working_level / 2
and c.working_level > 0
)
--And grab the records from the CTE where the working_level is 0
select num_orig, binval
from ctebins
where working_level = 0
;
Actually, you don't need nums0. That had been based on an earlier incarnation I had.
with ctebins as
(select num as num_orig, num as working_level, cast('' as varchar(max)) as binval
from nums_bin
union all
select c.num_orig, c.working_level / 2, cast(c.working_level % 2 as varchar(max)) + c.binval
from
ctebins c
where c.working_level > 0
)
--And grab the records from the CTE where the working_level is 0
select num_orig, binval
from ctebins
where working_level = 0
;
Hi Rob,
Beautiful implementation. I was thinking in the same lines for the implementation.
But then I thought, if I extend it to work on, say, a million rows, I would end up caching so much data. Since I would be appending a million rows for every iteration. What do you think?
And I read through your post in your blog. If you like recursive ctes then you may be interested in this blog post (in case you hadn't already seen it) :)
http://omnibuzz-sql.blogspot.com/2006/06/interesting-queries-using-recursive.html
-Omni
Hi all (those who are following this),
The solution provided by Rob takes 37 seconds in my server box to return the result for 50,000 numbers. So far the best I have. Any one to challenge that?
Rob, you want to take another stab at it :)
-Omni
How about this:
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
There's more info over at my blog
Hi Mitch,
Its a wonderful implementation. Something I have never come across till date. Its pretty much as fast as it can get. It took just a second for processing 50,000 records, the time I would attribute to sending data over the network.
Great One.
-Omni
Here is my solution using the common table expressions. Definitely not as brainy as the one given by Mitch. But works fine :)
Assuming nums_bin is the table having the 50000 records, the following is the query
declare @maxval int
select @maxval = max(num) from nums_bin;
with cte as
(
select 1 as bin,1 as counter
union all
select bin*2,counter + 1 from cte
where bin*2 < @maxval
)
select num,
(select (num&bin)/bin from cte b order by counter desc for xml path('')) as bin
from nums_bin
Post a Comment