THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
 in Adam Machanic (Entire Site) Search

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 = 33 << 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 = 66 >> 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 = 0x0003DECLARE @LeftShiftNum INTSET @LeftShiftNum = 1SELECT Number + @LeftShiftNum AS NumberFROM dbo.splitBitmask(@Bitmask)Number------23`

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

`DECLARE @Bitmask VARBINARY(4096)SET @Bitmask = 0x0006DECLARE @RightShiftNum INTSET @RightShiftNum = 1SELECT Number - @RightShiftNum AS NumberFROM dbo.splitBitmask(@Bitmask)Number------12`

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)ASBEGIN	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)ENDGO-- Here are some examples to prove that everything works:SELECT dbo.bitwiseLeftShift(0x03, 1) AS [3_times_two]GO3_times_two-----------0x06SELECT dbo.bitwiseLeftShift(0x03, 3) AS [3_times_eight]GO3_times_eight-------------0x18SELECT CONVERT(int, 0x18) AS [int_0x18]int_0x18--------24SELECT dbo.bitwiseLeftShift(0x18, 12) AS [24_times_4096]24_times_4096-------------0x018000SELECT CONVERT(int, 0x018000) AS [int_0x018000]int_0x018000------------98304SELECT 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)ASBEGIN	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)ENDGO--Right-shifting the same number we just left-shifted 12 bits should yeild the same inputSELECT 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: ,

#### saisub said:

no info regarding signed number shift..bye

March 26, 2007 11:47 PM

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

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

#### Dawid said:

Hi,

I stumbled upon your series of handling shifts in SQL, however I have spent hours already and can't implement it. Basically I need to be able to implement left-shift for integers, just like JavaScript's   77 << 5 should give me 2464, but I can't get it to work with your functions.

I have copied leftshift and splitbitmask but running leftshift funcion with (77,5) only gives me 0x

If you're still maintaining this site and could help that would be fantastic

October 20, 2015 5:17 AM

@Dawid,

These functions don't take integers as their inputs -- rather they take bitmasks. But you really should not use them for anything production related. I wrote them just for fun.

What do you need this for? As Stephen Channell mentioned above, simple bit shifting can be done with the power() function: SELECT 77 * POWER(2,5) -- that's the same as left shifting 5 times.

That won't scale to HUGE numbers. If you need to do that, I'd write a SQLCLR function.

October 20, 2015 5:19 PM

#### In Short ... said:

for positive ints:

a << b = a * power(2, b)

a >> b = a / power(2, b)

November 9, 2015 12:51 AM

(required)
(required)
Submit