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!!!
no info regarding signed number shift..bye
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.
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))
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
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 🙂
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
@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
for positive ints:
a << b = a * power(2, b)
a >> b = a / power(2, b)
Comments are closed.