adam machanic now blogs at http://sqlblog.com

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