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:

[sql]0011 (base 2) = 1 + 2 = 3

3 << 1 = 0110 (base 2) = 4 + 2 = 6

— Note that << is the C++ left-shift operator
[/sql]

Or we could go the other way and divide:

[sql]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
[/sql]

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.

[sql]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
[/sql]

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

[sql]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
[/sql]

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:

[sql]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
[/sql]

… and the same for right-shift:

[sql]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 🙂
[/sql]

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