Technical Article

Function to count set bits in a signed integer

,

This function will count the number of 1's in the binary representation of a two's complement integer. For example the number 15 in binary is written as 1111; this contains four 1s. Or 33 is represented as 100001 and contains two 1's. SQL Server's data types do not include "unsigned-integer" so this alogrithm has been designed to also count the left most 1 in the Two's Complement representation of negative numbers.

It works by using the fact that when you subtract 1 from a binary number the right most 1 becomes zero and all leading zeros become 1. e.g.

  00011110000 - 1 = 00011101111

Then a bitwise AND is done on the orginal number and the result

  00011110000 & 00011101111 = 0001110000

This gives a result with one less 1 in.

The process is repeated until the result is zero. This takes as many operations as there are 1's in the original number so it is efficient when 1's are sparse in the bigint.

-- =============================================
-- Author:		Jonathan Roberts
-- Create date: 24/02.2014
-- Description:	Counts the number of set bits in a signed integer
-- Sample calls: 
--   SELECT [dbo].[BitsIn] (-9223372036854775808) -- Returns 1
--   SELECT [dbo].[BitsIn] (-1) -- Returns 64
--   SELECT [dbo].[BitsIn] (0)  -- Returns 0
--   SELECT [dbo].[BitsIn] (3)  -- Returns 2
--   SELECT [dbo].[BitsIn] (15) -- Returns 4
--   SELECT [dbo].[BitsIn] (16) -- Returns 1
--   SELECT [dbo].[BitsIn] (9223372036854775807)  -- Returns 63
-- =============================================
CREATE FUNCTION [dbo].[BitsIn]
(
	@Input bigint
)
RETURNS int
AS
BEGIN

	DECLARE @BitsIn tinyint = 0

	IF @Input < 0 BEGIN -- To cope with negative numbers
		SELECT @Input &= ~CONVERT(bigint, -9223372036854775808),
		       @BitsIn = 1
	END

	WHILE @Input > 0 BEGIN
		SET @Input &= @Input & (@Input - 1)
		SET @BitsIn += 1
	END
		
	RETURN @BitsIn

END
GO

Rate

4 (4)

You rated this post out of 5. Change rating

Share

Share

Rate

4 (4)

You rated this post out of 5. Change rating