Technical Article

Integer left and right shift

,

These 3 functions implement the left, right and unsigned right shift operators, commonly found in C-style languages. They are implemented as table-valued functions and can be used like so:

-- Returns y = x << s

SELECT y FROM dbo.shiftLeft(x, s)

-- Returns y = x >> s

SELECT y FROM dbo.shiftRight(x, s)

-- Returns y = x >>> s

SELECT y FROM dbo.shiftRight0(x, s)

They will work with any input (no numeric overflows) and negative values are handled properly.

IF OBJECT_ID('dbo.shiftLeft', 'IF') IS NULL
	EXEC('CREATE FUNCTION [dbo].[shiftLeft]() RETURNS TABLE AS RETURN SELECT foo = 1')
GO
/***********************************************************************
AUTHOR		:	Ioannis Tsakpinis
CREATED		:	29.12.2011
DESCRIPTION :	Performs bitwise left-shift: y = x << s
************************************************************************/
ALTER FUNCTION [dbo].[shiftLeft] (
	@x	INT,
	@s	INT
)
	RETURNS TABLE
	WITH SCHEMABINDING
AS
RETURN
	SELECT
		-- Equivalent to x * 2^s
		-- Truncate bits 32-63 and cast back to INT
		y = CAST(CAST(@x * p.pow AS BINARY(4)) AS INT)
	FROM (
		-- 2^31 will overflow, cast to BIGINT
		SELECT pow = POWER(CAST(2 AS BIGINT), @s & 0x1F) -- Wrap around 31
	) p

-- EOF --
GO
IF OBJECT_ID('dbo.shiftRight', 'IF') IS NULL
	EXEC('CREATE FUNCTION [dbo].[shiftRight]() RETURNS TABLE AS RETURN SELECT foo = 1')
GO
IF OBJECT_ID('dbo.shiftRight0', 'IF') IS NOT NULL
	DROP FUNCTION [dbo].[shiftRight0]
GO
/***********************************************************************
AUTHOR		:	Ioannis Tsakpinis
CREATED		:	29.12.2011
DESCRIPTION :	Performs bitwise right-shift with sign-extension: y = x >> s
************************************************************************/
ALTER FUNCTION [dbo].[shiftRight] (
	@x	INT,
	@s	INT
)
	RETURNS TABLE
	WITH SCHEMABINDING
AS
RETURN
	SELECT y = 
		CASE WHEN @x >= 0 THEN
			-- Equivalent to x / 2^s
			CAST(@x / p.pow AS INT)
		ELSE
			-- Go positive, shift, then go back to negative
			CAST(~(~@x / p.pow) AS INT)
		END
	FROM (
		-- 2^31 will overflow, cast to BIGINT
		SELECT pow = POWER(CAST(2 AS BIGINT), @s & 0x1F) -- Wrap around 31
	) p

-- EOF --
GO
IF OBJECT_ID('dbo.shiftRight0', 'IF') IS NULL
	EXEC('CREATE FUNCTION [dbo].[shiftRight0]() RETURNS TABLE AS RETURN SELECT foo = 1')
GO
/***********************************************************************
AUTHOR		:	Ioannis Tsakpinis
CREATED		:	29.12.2011
DESCRIPTION :	Performs bitwise right-shift with zero-extension: y = x >>> s
************************************************************************/
ALTER FUNCTION [dbo].[shiftRight0] (
	@x	INT,
	@s	INT
)
	RETURNS TABLE
	WITH SCHEMABINDING
AS
RETURN
	SELECT y =
		CASE WHEN @x >= 0 THEN
			-- Equivalent to right-shift with sign-extension
			s.y
		ELSE
			-- Calculates (x >> s) + (2 << ~s)
			-- then truncates bits 32-63 and casts back to INT
			CAST(CAST(s.y + (POWER(CAST(2 AS BIGINT), (~@s & 0x1F) + 1)) AS BINARY(4)) AS INT)
		END
	FROM dbo.shiftRight(@x, @s) s

-- EOF --
GO

Rate

3.5 (4)

You rated this post out of 5. Change rating

Share

Share

Rate

3.5 (4)

You rated this post out of 5. Change rating