Function to count set bits in a signed integer

Question

Post reply

Function to count set bits in a signed integer

Jonathan AC Roberts

SSCoach

Points: 18361
More actions
April 22, 2015 at 5:36 pm

#316881

Comments posted to this topic are about the item Function to count set bits in a signed integer

Viewing 10 posts - 1 through 9 (of 9 total)

You must be logged in to reply to this topic. Login to reply

Michael Meierruth SSChampion Points: 10051 More actions · Answer 1

Any particular reason for

~CONVERT(bigint, -9223372036854775808)

instead of

CONVERT(bigint, 9223372036854775807)

My Italian keyboard doesn't have this famous tilde characters! :crying:

Oh crap, forgot all about copy/paste. 🙂

Jonathan AC Roberts SSCoach Points: 18361 More actions · Answer 2

~ is the T-SQL's bitwise NOT operator. It inverts all the bits in an integer.

It's used so the right-most bit, which is set to 1 two's compliment signed integer that has a negative value, can be counted.

In binary -9223372036854775808 = 1000000000000000000000000000000000000000000000000000000000000000 (1 with 63 trailing zeros), when you bitwize NOT this number you get 0111111111111111111111111111111111111111111111111111111111111111 (0 with 63 trailing 1's). When we AND this with the bigint parameter to the function it removes the leading 1 making it a positive number.

Michael Meierruth SSChampion Points: 10051 More actions · Answer 3

Jonathan AC Roberts (4/28/2015)
~ is the T-SQL's bitwise NOT operator. It inverts all the bits in an integer.
It's used so the right-most bit, which is set to 1 two's compliment signed integer that has a negative value, can be counted.
In binary -9223372036854775808 = 1000000000000000000000000000000000000000000000000000000000000000 (1 with 63 trailing zeros), when you bitwize NOT this number you get 0111111111111111111111111111111111111111111111111111111111111111 (0 with 63 trailing 1's). When we AND this with the bigint parameter to the function it removes the leading 1 making it a positive number.

What I was trying to say was that

~CONVERT(bigint, -9223372036854775808)

and

CONVERT(bigint, 9223372036854775807)

return the same value.

Jonathan AC Roberts SSCoach Points: 18361 More actions · Answer 4

Michael Meierruth (4/28/2015)
Jonathan AC Roberts (4/28/2015)
~ is the T-SQL's bitwise NOT operator. It inverts all the bits in an integer.
It's used so the right-most bit, which is set to 1 two's compliment signed integer that has a negative value, can be counted.
In binary -9223372036854775808 = 1000000000000000000000000000000000000000000000000000000000000000 (1 with 63 trailing zeros), when you bitwize NOT this number you get 0111111111111111111111111111111111111111111111111111111111111111 (0 with 63 trailing 1's). When we AND this with the bigint parameter to the function it removes the leading 1 making it a positive number.
What I was trying to say was that
~CONVERT(bigint, -9223372036854775808)
and
CONVERT(bigint, 9223372036854775807)
return the same value.

Yes, both give the answer of (2^63) - 1

akljfhnlaflkj SSC Guru Points: 76202 More actions · Answer 5

Not sure I will ever use it in my every day work. Interesting nevertheless and I'm sure someone will make use of it. Thanks for the exercise.

Michael Meierruth SSChampion Points: 10051 More actions · Answer 6

Iwas Bornready (4/28/2015)
Not sure I will ever use it in my every day work. Interesting nevertheless and I'm sure someone will make use of it. Thanks for the exercise.

In fact, this will lead us into the question of what in the real world gets represented as positional bits in an Int or BigInt column and where counting the number of bits turned on becomes meaningful/useful.

Jonathan AC Roberts SSCoach Points: 18361 More actions · Answer 7

Well it probably is bit of an obscure/esoteric thing to do but one of the most efficient ways of storing items that are switched is in a bit string within an integer. For Quine-McCluskey minimisation (the reason I wrote this function) part of the algorithm involves counting the set bits in an integer (the minterms). This information is then used to group the integers into sets by how many 1's they contain.

Mark D Powell SSCarpal Tunnel Points: 4775 More actions · Answer 8

Unless I typed over the comment by accident there is an error in the comments since BitsIn returns 4 for an input of 15 while the comment lists 3 as the result.

HTH -- Mark D Powell --

Jonathan AC Roberts SSCoach Points: 18361 More actions · Answer 9

Mark D Powell (4/28/2015)
Unless I typed over the comment by accident there is an error in the comments since BitsIn returns 4 for an input of 15 while the comment lists 3 as the result.
HTH -- Mark D Powell --

Yes, well spotted, that's an error in the comment. Fortunately the error is not in the code as 15 has four bits set as its binary representation is 1111