THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Adam Machanic

Adam Machanic, Boston-based SQL Server developer, shares his experiences with programming, monitoring, and performance tuning SQL Server. And the occasional battle with the query optimizer.

Bitmask Handling, part 4: Left-shift and right-shift

Quick installment this time. Left-shift and right-shift operators.

Left-shift and right-shift are integral to binary mathematical operations as they have two important qualities: Left-shifting a bitmask once multiplies by two. Right-shifting once divides by two. For example:

 

0011 (base 2) = 1 + 2 = 3

3 << 1 = 0110 (base 2) = 4 + 2 = 6

-- Note that << is the C++ left-shift operator

Or we could go the other way and divide:

 

0110 (base 2) = 4 + 2 = 6

6 >> 1 = 0011 (base 2) = 2 + 1 = 3


-- But what happens if we do a second right-shift?

3 >> 1 = 0001 (base 2) = 1


-- Now we've lost a bit (it "fell off the edge") -- causing rounding.
-- Luckily, that's the same way SQL Server treats this situation:

SELECT 3 / 2 AS [3_Right_1]


3_Right_1
---------
1

So now you've seen the basics of left-shifting and right-shifting. But how easy is it to implement given the bitmask handling framework already established in previous installments?

Very, very easy!

Remember that 0011 (base 2) is 3 (base 10) or 0x0003 (base 16), and has bits 1 and 2 turned on. Left-shifting once should produce 0110 / 6 / 0x0006 -- bits 2 and 3 turned on.

 

DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x0003

DECLARE @LeftShiftNum INT
SET @LeftShiftNum = 1


SELECT Number + @LeftShiftNum AS Number
FROM dbo.splitBitmask(@Bitmask)


Number
------
2
3

And that's literally all there is to it. Right-shift is just as easy, but we subtract:

 

DECLARE @Bitmask VARBINARY(4096)
SET @Bitmask = 0x0006

DECLARE @RightShiftNum INT
SET @RightShiftNum = 1


SELECT Number - @RightShiftNum AS Number
FROM dbo.splitBitmask(@Bitmask)


Number
------
1
2

Right-shifting twice will produce an out-of-bounds bit, 0. But that's not an issue, because the bitmask re-constitution pattern uses the bitmaskNumbers table, which conveniently doesn't contain a 0. A bit of accidental foresight on my part, perhaps.

I have nothing more to say on this issue. Plug everything back into the re-constitution pattern and we're done:

 

CREATE FUNCTION bitwiseLeftShift
(
@Bitmask VARBINARY(4096),
@LeftShiftNum INT
)
RETURNS VARBINARY(4096)
AS
BEGIN
DECLARE @BitsInBitmask TABLE(Number SMALLINT)
INSERT @BitsInBitmask
SELECT Number
FROM
(
SELECT Number + @LeftShiftNum AS Number
FROM dbo.splitBitmask(@Bitmask)
) x

SET @Bitmask = 0x

SELECT @Bitmask = @Bitmask +
CONVERT(VARBINARY(1),
SUM(CASE
WHEN x.Number IS NULL THEN 0
ELSE BitmaskNumbers.BitValue
END)
)
FROM @BitsInBitmask x
RIGHT JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number
WHERE BitmaskNumbers.Byte <=
(SELECT
CASE MAX(Number) % 8
WHEN 0 THEN (MAX(Number) - 1) / 8
ELSE MAX(Number) / 8
END + 1
FROM @BitsInBitmask)
GROUP BY BitmaskNumbers.Byte
ORDER BY BitmaskNumbers.Byte DESC

RETURN(@Bitmask)
END
GO


-- Here are some examples to prove that everything works:


SELECT dbo.bitwiseLeftShift(0x03, 1) AS [3_times_two]
GO


3_times_two
-----------
0x06



SELECT dbo.bitwiseLeftShift(0x03, 3) AS [3_times_eight]
GO


3_times_eight
-------------
0x18



SELECT CONVERT(int, 0x18) AS [int_0x18]


int_0x18
--------
24



SELECT dbo.bitwiseLeftShift(0x18, 12) AS [24_times_4096]


24_times_4096
-------------
0x018000


SELECT CONVERT(int, 0x018000) AS [int_0x018000]


int_0x018000
------------
98304



SELECT 98304 / 4096 AS [this_will_be_24]


this_will_be_24
---------------
24

... and the same for right-shift:

CREATE FUNCTION bitwiseRightShift
(
@Bitmask VARBINARY(4096),
@RightShiftNum INT
)
RETURNS VARBINARY(4096)
AS
BEGIN
DECLARE @BitsInBitmask TABLE(Number SMALLINT)
INSERT @BitsInBitmask
SELECT Number
FROM
(
SELECT Number - @RightShiftNum AS Number
FROM dbo.splitBitmask(@Bitmask)
) x

SET @Bitmask = 0x

SELECT @Bitmask = @Bitmask +
CONVERT(VARBINARY(1),
SUM(CASE
WHEN x.Number IS NULL THEN 0
ELSE BitmaskNumbers.BitValue
END)
)
FROM @BitsInBitmask x
RIGHT JOIN BitmaskNumbers ON BitmaskNumbers.Number = x.Number
WHERE BitmaskNumbers.Byte <=
(SELECT
CASE MAX(Number) % 8
WHEN 0 THEN (MAX(Number) - 1) / 8
ELSE MAX(Number) / 8
END + 1
FROM @BitsInBitmask)
GROUP BY BitmaskNumbers.Byte
ORDER BY BitmaskNumbers.Byte DESC

RETURN(@Bitmask)
END
GO


--Right-shifting the same number we just left-shifted 12 bits should yeild the same input

SELECT dbo.bitwiseRightShift(0x018000, 12) AS [should_be_0x18]


should_be_0x18
--------------
0x18



--Is overflow handled the same way that SQL Server handles it?

SELECT
CONVERT(INT, dbo.bitwiseRightShift(0x018000, 16)) AS [overflow],
98304 / 65536 AS [98304_divide_65536]

overflow 98304_divide_8192
-------- -----------------
1 1


--Apparently :)

Enough for now. Next installment, the long awaited mathematical operators. Special thanks to Steve Kass for smacking me around a bit in the comments section of the last installment and teaching me how to properly implement signed numbers in a binary system. So the next installment will actually be able to deal with negative integers too. Thanks, Steve!!!


Published Wednesday, July 12, 2006 10:29 PM by Adam Machanic
Filed under: ,

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

saisub said:

no info regarding signed number shift..bye

March 26, 2007 11:47 PM
 

Adam Machanic said:

Sorry, I kind of dropped the ball on this over two years ago.  Some day perhaps I'll revisit it, but no promises.  I'll probably use SQLCLR if I do.

May 22, 2007 2:05 PM
 

Stephen Channell said:

Have I missed something.. but bit shifting can be done with the power() function.. e.g. 100 left shift 3 and right shift 3

select 100 * power(2,3), convert(int, 100 / power(2,3))

May 22, 2008 8:58 AM
 

Justin Dearing said:

Stephen,

Yes you can. and I did that to do byte shifting like so:

SELECT

CAST(0xFF * POWER(CAST(256 AS BIGINT), 0) AS BINARY(12)) AS Shift0,

CAST(0xFF * POWER(CAST(256 AS BIGINT), 1) AS BINARY(12)) AS Shift1,

CAST(0xFF * POWER(CAST(256 AS BIGINT), 2) AS BINARY(12)) AS Shift2,

CAST(0xFF * POWER(CAST(256 AS BIGINT), 3) AS BINARY(12)) AS Shift3,

CAST(0xFF * POWER(CAST(256 AS BIGINT), 4) AS BINARY(12)) AS Shift4,

CAST(0xFF * POWER(CAST(256 AS BIGINT), 5) AS BINARY(12)) AS Shift5

July 31, 2010 10:26 PM
 

Adam Machanic said:

Stephen and Justin:

Yes, that will work, but since we lack unsigned types in T-SQL you can wind up with an overflow exception if you do it like that. Anyway, these techniques are way outdated today thanks to the inclusion of SQLCLR in SQL Server 2005/2008--I certainly don't recommend actually doing this stuff for production purposes :-)

August 1, 2010 3:01 PM

Leave a Comment

(required) 
(required) 
Submit

About Adam Machanic

Adam Machanic is a Boston-based SQL Server developer, writer, and speaker. He focuses on large-scale data warehouse performance and development, and is author of the award-winning SQL Server monitoring stored procedure, sp_WhoIsActive. Adam has written for numerous web sites and magazines, including SQLblog, Simple Talk, Search SQL Server, SQL Server Professional, CoDe, and VSJ. He has also contributed to several books on SQL Server, including "SQL Server 2008 Internals" (Microsoft Press, 2009) and "Expert SQL Server 2005 Development" (Apress, 2007). Adam regularly speaks at conferences and training events on a variety of SQL Server topics. He is a Microsoft Most Valuable Professional (MVP) for SQL Server, a Microsoft Certified IT Professional (MCITP), and an alumnus of the INETA North American Speakers Bureau.

This Blog

Syndication

Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement