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!!!

## Comments

## saisub said:

no info regarding signed number shift..bye

## 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.

## 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))

## 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

## 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 :-)

## 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

## Adam Machanic said:

@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.

--Adam

## In Short ... said:

for positive ints:

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

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