{"id":105244,"date":"2025-02-08T16:32:01","date_gmt":"2025-02-08T16:32:01","guid":{"rendered":"https:\/\/www.red-gate.com\/simple-talk\/?p=105244"},"modified":"2025-02-12T17:10:31","modified_gmt":"2025-02-12T17:10:31","slug":"sql-server-bit_count-and-an-alternative","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/sql-server-bit_count-and-an-alternative\/","title":{"rendered":"SQL Server BIT_COUNT and an Alternative"},"content":{"rendered":"\n

I was editing an article the other day that uses the BIT_COUNT<\/code> function that was added to SQL Server 2022. The solution presented is excellent, and I will try to come back and link to it here when I remember. (It will be linked the other way.<\/p>\n\n\n\n

Reading that did two things for me. First it gave me an idea of how the BIT_COUNT<\/code> function might be actually be used in a useful way. The solution that was presented would only work in SQL Server 2022 (It will work in earlier compatibility levels, based on the tests I have done.)<\/p>\n\n\n\n

Bitwise operations, really?<\/h2>\n\n\n\n

As a person who is BIG into relational design and getting a well normalized database, let\u2019s start here. There is rarely a reason to use the bits of an integer value for any reason. I have argued with people plenty about this sort of thing, like when someone wanted to create a multi-valued domain table like the following example.<\/p>\n\n\n\n

Note that this isn’t an optimal design, so I am not advocating this for any new build. But it does happen, including places like SQL Server’s system tables.<\/p>\n\n\n\n

USE TempDB;\nGO\nCREATE SCHEMA DemoBits;\nGO\nCREATE TABLE DemoBits.Person\n(\n    PersonId int NOT NULL IDENTITY \n        CONSTRAINT PKPerson PRIMARY KEY,\n    Name varchar(20) NOT NULL\n        CONSTRAINT AKPerson UNIQUE,\n    Attributes int NOT NULL\n        CONSTRAINT DFLTPerson_Attributes DEFAULT (0)\n)\nGO\nCREATE TABLE DemoBits.AttributeType\n(\n    Attribute   int NOT NULL \n        CONSTRAINT PKAttributeTypes PRIMARY KEY,\n    Value varchar(20) NOT NULL\n)\nGO <\/pre>\n\n\n\n
Now you just load up the AttributeType<\/code> table with values that have primary key of the values that use a single bit in an integer:<\/p>\n\n\n\n
INSERT INTO DemoBits.AttributeType\nVALUES (1, 'AttributeType 1');\n\nINSERT INTO DemoBits.AttributeType\nVALUES (2, 'AttributeType 2');\n\nINSERT INTO DemoBits.AttributeType\nVALUES (4, 'AttributeType 3');\n\nINSERT INTO DemoBits.AttributeType\nVALUES (8, 'AttributeType 4');<\/pre>\n\n\n\n
Then, you have a multi-valued relationship with one less table. You can’t join to it conveniently, but it does work. For example:<\/p>\n\n\n\n
INSERT INTO DemoBits.Person(Name, Attributes)\nVALUES ('John', 1+8);<\/pre>\n\n\n\n
Now, you have a Person<\/code> row, and you can join to the attributes in this way:<\/p>\n\n\n\n
SELECT *\nFROM   DemoBits.Person\n        JOIN DemoBits.AttributeType\n            ON Person.Attributes & AttributeType.Attribute = AttributeType.Attribute<\/pre>\n\n\n\n
Which returns:<\/p>\n\n\n\n
PersonId    Name                 Attributes  Attribute   Value\n----------- -------------------- ----------- ----------- --------------------\n1           John                 9           1           AttributeType 1\n1           John                 9           8           AttributeType 4<\/pre>\n\n\n\n
And you can see that this person has two attributes with BIT_COUNT<\/code>:<\/p>\n\n\n\n
SELECT BIT_COUNT(Attributes)\nFROM  DemoBits.Person \nWHERE Name = 'John'<\/pre>\n\n\n\n
This returns:<\/p>\n\n\n\n
--------------------\n2<\/pre>\n\n\n\n
Now, of course I am not advocating this solution at all. There have been a few articles here on Simple Talk that made nice use of bits, for example Aaron Bertrand’s Days of the Week article<\/a>. But as a rule, this is not really a good design pattern, mostly for the reason that the join I created is very cryptic for 90% of people (and I didn’t exactly pull it out of active memory myself!).<\/p>\n\n\n\n
But what I did want to do is fix is if you are using a pre-SQL Server 2022 version of SQL Server and want to count the bits in an integer value, you can still use the technique from the forthcoming article I mentioned at the start of this article.<\/p>\n\n\n\n
The way this is done is basically shown in the join criteria. You and every single bit binary value, and when it is equal to the value you anded, you add one to the output. While the values you use are only the ones with a single bit, but it can also be used to find items with multiple bits. Like if you wanted to find the Person rows where they only have Attributes 1 and 4, you would just look for rows where Attributes = 9. But if you want to look for rows with at least those two:<\/p>\n\n\n\n
SELECT Name\nFROM  DemoBits.Person \nWHERE Attributes & 9 = 9;<\/pre>\n\n\n\n
And even if you updated it to 11:<\/p>\n\n\n\n
UPDATE DemoBits.Person\nSET    Attributes = 11\nWHERE  Name = 'John'<\/pre>\n\n\n\n
The SELECT<\/code> statement will still return \u2018John\u2019, and since you will still have the 1 and 8 bits set and now the SELECT<\/code> with the JOIN<\/code> from earlier in the chapter will return all three values:<\/p>\n\n\n\n
PersonId    Name                 Attributes  Attribute   Value\n----------- -------------------- ----------- ----------- --------------------\n1           John                 11          1           AttributeType 1\n1           John                 11          2           AttributeType 2\n1           John                 11          8           AttributeType 4<\/pre>\n\n\n\n
<\/p>\n\n\n\n
And BIT_COUNT<\/code> will return 3.<\/p>\n\n\n\n
The real point here is<\/h2>\n\n\n\n
Before I go too far and make this an article that looks like it is advocating for multi-valued, poorly normalized, bit based relationships… let’s get to the point. Counting bits.<\/p>\n\n\n\n
If BIT_COUNT<\/code> isn’t available, you can use something like this:<\/p>\n\n\n\n
SELECT CASE WHEN Attributes & 1 = 1 THEN 1 ELSE 0 END +\n       CASE WHEN Attributes & 2 = 2 THEN 1 ELSE 0 END +\n       CASE WHEN Attributes & 4 = 4 THEN 1 ELSE 0 END +\n       CASE WHEN Attributes & 8 = 8 THEN 1 ELSE 0 END \nFROM DemoBits.Person<\/pre>\n\n\n\n
Which will return 3, just like BIT_COUNT<\/code> will. And you can extend this pretty easily to cover all integers by doing all POWER(2)<\/code> values that will fit in an integer. This is tedious to type, so I will do this with a bit of code.<\/p>\n\n\n\n
Note: I am using the GENERATE_SERIES<\/code> function that also was added to SQL Server 2022, but you can generate a numbers table using code like this one from Greg Larsen a few years ago<\/a> if you are on an earlier version.<\/p>\n\n\n\n
SELECT CONCAT('CASE WHEN @TestValue & ',\n              POWER(2,Value), '=', \n              POWER(2,VALUE), ' THEN 1 ELSE 0 END + ')\n--only 31 values since a signed integer has < a 32 bit integer\nFROM   GENERATE_SERIES(0,30) <\/pre>\n\n\n\n
Now, copy that code and make the following function. The part after the --copied code<\/code> is what i generated, including all the bits available.<\/p>\n\n\n\n
I added an extra line to handle negative values. I would be wary of using that special bit using any method that is giving meaning to the bits, but it is available as a 32nd<\/sup> bit and counted by the BIT_COUNT<\/code> function:<\/p>\n\n\n\n
CREATE OR ALTER FUNCTION DemoBits.BitCount_Int\n(\n    @TestValue int\n) \nRETURNS int AS\nBEGIN\nRETURN(\n--copied code\nCASE WHEN @TestValue & 1=1 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 2=2 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 4=4 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 8=8 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 16=16 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 32=32 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 64=64 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 128=128 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 256=256 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 512=512 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 1024=1024 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 2048=2048 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 4096=4096 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 8192=8192 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 16384=16384 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 32768=32768 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 65536=65536 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 131072=131072 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 262144=262144 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 524288=524288 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 1048576=1048576 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 2097152=2097152 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 4194304=4194304 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 8388608=8388608 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 16777216=16777216 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 33554432=33554432 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 67108864=67108864 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 134217728=134217728 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 268435456=268435456 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 536870912=536870912 THEN 1 ELSE 0 END + \nCASE WHEN @TestValue & 1073741824=1073741824 THEN 1 ELSE 0 END +\nCASE WHEN @TestValue < 0 THEN 1 ELSE 0 END) --there is a bit to say it is negative \nEND\nGO<\/pre>\n\n\n\n
Now, you should be able to use this for most of your bit counting uses just like BIT_COUNT<\/code>.<\/p>\n\n\n\n
You could extend it for any type of uses but I will submit to you that if you find yourself doing bitwise operations for any reason other than legacy data\/designs\/or increasing processing performance with several orders of magnitude performance gains (like eliminating necessary loops in code that are executed many times over), you should rethink your plans.<\/p>\n\n\n\n
Testing your solution<\/h2>\n\n\n\n
Like any code experiment, one last thing to do, make sure you have tested the code. This code can be tested like this using a SQL Server 2022 instance, though I wouldn’t try to run this on your laptop if you are on battery.<\/p>\n\n\n\n
It is doing over 4 billion iterations of those functions and on my 4 core laptop with 11th Gen Intel Core i7-1185G7 @ 3.00GHz CPU (that is also running Discord, Slack, and especially Word as I edit this to a postable state while I wait for it to finish), it took “going out to lunch” time to complete.<\/p>\n\n\n\n
DECLARE @StartTime datetime2(7) = sysdatetime();\n\nSELECT Value\nFROM GENERATE_SERIES(-2147483648,2147483647) --testing all of the integers\nWHERE DemoBits.BitCount_Int(value) <> BIT_COUNT(value);\n\nSELECT Datediff(millisecond,@StartTime,sysdatetime()) AS TEST_THEM_BOTH;<\/pre>\n\n\n\n
The CPU graph was fun to watch while this was running. It is not doing any parallel operations. I will show you the plan for a more performance oriented test in a bit.<\/p>\n\n\n\n
For me, this returned: 5286682 milliseconds which is and, as SSMS shows me, over 128 minutes and 7 seconds. I mean, I did ask it to do that function and the BIT_COUNT<\/code> function over 4 billion times each, so I am pretty happy with that.<\/p>\n\n\n\n
Unlike most code, because I have tested every single possible value that can be entered, this code is actually verified correct for any input that is in the allowable range. Most functions cannot be tested this well, and to be fair, you wouldn\u2019t want to use my test as your unit test either, since it takes so long.<\/p>\n\n\n\n
When this returns 0 rows, you know it works like it should.<\/p>\n\n\n\n
Which version is faster?<\/h2>\n\n\n\n
One of the only reasons (other than being stuck in a legacy version) you typically say “use your own function instead of a system function” is performance. The FORMAT<\/code> function is one of those cases that Aaron Bertrand covered a few years ago on this SQL Performance post<\/a>.<\/p>\n\n\n\n
So while it is established that this function works correctly, and 100% better than not having one built in in previous versions, in this section, I want to run a quick test to see which one performs better or worse.<\/p>\n\n\n\n
To do this, I will run the functions a few times on a fairly large set of data. Whichever one was the fastest, I ran it before and after the slower one, to make sure there was nothing weird about the test based on ordering. (I also altered the order a few times before deciding to accept my results.<\/p>\n\n\n\n
DROP TABLE IF EXISTS #holdResults1;\nDROP TABLE IF EXISTS #holdResults2;\nGO\nCREATE TABLE #holdResults1 (value int);\nCREATE TABLE #holdResults2 (value int);\nGO\n--capture the current time, and set the range of values to test with. \n--This doesn\u2019t need to be all values, just a lot\nDECLARE @StartTime datetime2(7) = sysdatetime();\nDECLARE @StartValue int = 0;\nDECLARE @EndValue int = 1000000;\n\n--test system function\nINSERT INTO #holdResults1\nSELECT Value\nFROM GENERATE_SERIES(@StartValue, @EndValue)\nWHERE BIT_COUNT(value ) = 10; --I didn\u2019t want to do anything the optimizer\n                       --could optimize away. It needs to run the functions for each row\n\nSELECT DATEDIFF(millisecond,@StartTime,sysdatetime()) AS BIT_COUNT;\n\n--reset the times, do test with the user function\nSET @StartTime = sysdatetime();\nINSERT INTO #holdResults2\nSELECT Value\nFROM GENERATE_SERIES(@StartValue, @EndValue)\nWHERE DemoBits.BitCount_Int(value) = 10;\n\nSELECT datediff(millisecond,@StartTime,sysdatetime()) AS MY_FUNCTION;\n\n--output counts of matches, for comparison\nSELECT COUNT(*) BIT_COUNT_TOTALROWS \nFROM #HoldResults1;\n\nSELECT COUNT(*) MY_FUNCTION_TOTALROWS from #HoldResults2;\n\n--then run the system one again, and insert into the same table\nSET @StartTime = sysdatetime();\nINSERT INTO #holdResults1\nSELECT Value\nFROM GENERATE_SERIES(@StartValue, @EndValue)\nWHERE BIT_COUNT(value) = 10;\n\nSELECT datediff(millisecond,@StartTime,sysdatetime()) AS BIT_COUNT_AGAIN;\nGO<\/pre>\n\n\n\n
On my machine, these queries executed in considerably different times, and the system function blew it away by an order of magnitude.<\/p>\n\n\n\n
BIT_COUNT\n-----------\n258\n\nMY_FUNCTION\n-----------\n1425\n\nBIT_COUNT\n-----------\n400<\/pre>\n\n\n\n
Mind you, these are milliseconds for calculating the value a million times. And 1.4 seconds versus .4 seconds would be a win for the system function, even if it was the slower of the two! But it definitely is faster using the system function.<\/p>\n\n\n\n
In Conclusion<\/h2>\n\n\n\n
I started this experiment because of the usage of BIT_COUNT<\/code> in an article that I also felt would be useful in previous versions of SQL Server and to be honest, today is the first Saturday of the year with no football, so I had some time on my hands.<\/p>\n\n\n\n
I think the function: BitCount_Int<\/code> would be a good enough replacement for BIT_COUNT<\/code> in your earlier systems that should work in reasonable version of SQL Server.<\/p>\n\n\n\n
And remember, flipping and counting bits should be reserved for only the most time sensitive, performance tuning operations. It makes code hard to understand, hard to use, and so many more negatives. But if you find a solution that executes 100- or 1000-times shorter execution time than not using it\u2026 I can\u2019t fight you on that, though I still will try.<\/p>\n","protected":false},"excerpt":{"rendered":"
I was editing an article the other day that uses the BIT_COUNT function that was added to SQL Server 2022. The solution presented is excellent, and I will try to come back and link to it here when I remember. (It will be linked the other way. Reading that did two things for me. First……<\/p>\n","protected":false},"author":56085,"featured_media":105268,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143531],"tags":[4151],"coauthors":[19684],"class_list":["post-105244","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-t-sql-programming-sql-server","tag-sql-server"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/105244","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/56085"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=105244"}],"version-history":[{"count":22,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/105244\/revisions"}],"predecessor-version":[{"id":105556,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/105244\/revisions\/105556"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media\/105268"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=105244"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=105244"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=105244"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=105244"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}