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

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

    By
    Adam Machanic
    -
    1407
    8

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

    Previous articleBitmask Handling, part 3: Logical operators
    Next articlePattern-based split string
    Adam Machanic
    http://dataeducation.com
    Adam Machanic helps companies get the most out of their SQL Server databases. He creates solid architectural foundations for high performance databases and is author of the award-winning SQL Server monitoring stored procedure, sp_WhoIsActive. Adam has contributed to numerous books on SQL Server development. A long-time Microsoft MVP for SQL Server, he speaks and trains at IT conferences across North America and Europe.

    RELATED ARTICLESMORE FROM AUTHOR

    8 COMMENTS

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

    3. 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))

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

    5. 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 🙂

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

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

    Comments are closed.