Function to count set bits in a signed integer

  • Jonathan AC Roberts

    SSCoach

    Points: 16884

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

  • Michael Meierruth

    SSCrazy Eights

    Points: 9991

    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: 16884

    ~ 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

    SSCrazy Eights

    Points: 9991

    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: 16884

    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

    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

    SSCrazy Eights

    Points: 9991

    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: 16884

    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: 4379

    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: 16884

    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

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

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