Article: Bit-Masks - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

Site Related Forums

Article Discussion

Article: Bit-Masks

Author

Topic

AskSQLTeam
Ask SQLTeam Question

0 Posts

Posted - 2000-08-09 : 10:44:43

chris writes "I am having difficultly finding information on bit masks. Can you help me understand advantages and how to create using VID6.0? SQL Server 7.0/Win98" Bitmasks are interesting. Here's the scoop.

Article Link.

jfuex
Starting Member

29 Posts

Posted - 2002-06-20 : 17:34:22

It was asked in the original question and not addressed in the answer why you would want to use a bitmask. They are very useful for storing a series of related boolean values in a single field. Most frequently I use them for security related functionalty. For example, say that you have a user security table in which you want to store the user name, password and which of 32 pre-defined rights that user has. You could implement this as 2 varchar fields and 32 bit fields, but you could simplify this model by representing all of the permissions in an integer field. An integer field is essentially a binary value consisting of 32 bits. If you logically assign a specific permission to each bit position, you can store any combination of 32 distinct permission values in a single field.

Example:
Bit 1 = Read Permission
Bit 2 = Write Permissin
Bit 3 = Admin Permission.

To give a person read and write, but not admin permission you would set the permission (integer) value by OR'ing (|) all the rights you are interesting in combining as follows:
SET @USER_RIGHTS = 2 OR 4 {2 = 2^1 and 2 = 2^2)

To query to see if a user has admin rights you can do a bitwise comparison such as
IF (@USER_RIGHTS & 8 = 8) .... (8 = 2^3)

It makes your code a lot easier to readif you use some sort of constant to represent each of the bit/right assignments

PERMISSION_READ = 2 '00000000000000000000000000000010
PERMISSION_WRITE = 4 '00000000000000000000000000000100
PERMISSION_ADMIN = 8 '00000000000000000000000000001000

SET @USER_RIGHTS = PERMISSION_READ OR PERMISSION_ADMIN

An added bonus is that boolean operations are in the computer's native language and thus are pretty much one of the fastest operations around in just about any environment.

tymberwyld
Starting Member

4 Posts

Posted - 2004-10-11 : 15:30:07

Ok, you mentioned using an "Int" DataType field (lets assume this is SQL Server). I've tried doing this, and maybe I don't understand enough, but I cannot store 32bits into an Int Column.

Lets say I have an Enum and the values are 1 - 23. Lets also assume that each value is represented by 1 bit (Booleans). Using your example, I should be able to do something like this:
Set @USER_RIGHTS = Power(2,32) -- Set the 32nd Bit

I get Arithmetic Overflow Errors doing this. What am I doing wrong and how to I get this working??

robvolk
Most Valuable Yak

15732 Posts

Posted - 2004-10-11 : 22:18:13

The 32nd bit of a 32 bit word is for flagging negative/positive values. You can set it by negating the numeric value:

SET myIntColumn = -myIntColumn

Also, because the upper limit of an int is 2^31 - 1, you cannot raise 2 to any power greater than 30. You can get around this with:

SET myIntColumn=Power(2, 30) - 1 + Power(2, 30)

I leave the bitwise math equivalent of that to you (I sure can't figure it out)

Don't forget that you can do bitwise operations using binary or varbinary values too (as the article demonstrates), as long as one of the arguments is an int, smallint, or tinyint. You can then convert the binary value to an int, or just store is as binary.

I'd suggest that if you had more than 32 settings you want to store, use a regular binary value instead. You can do bitwise operations on up to 4 bytes of it at a time, and if you need to work with more than 4 bytes you can use SUBSTRING() to extract the extra bytes you need:

DECLARE @flags binary(8)
set @flags=0xFFEEDDCCBBAA9900
select substring(@flags, 1, 4) & 16384
select substring(@flags, 5, 4) & 4096

Keep in mind that SQL Server is not designed for efficient bitwise handling, and unless you need to save many dozen or hundreds of settings (especially if you have to query them regularly) you are most likely better off storing them in individual bit columns. In SQL Server 2000 bit columns can be indexed. Additionally, you can create calculated columns that do the bitwise operations needed to mask out a setting, making it easier to read and query, and these can also be indexed in SQL Server 2000.

tymberwyld
Starting Member

4 Posts

Posted - 2004-10-11 : 22:41:48

What I ended up doing (after further reading and understand) is making a Column called "SecurityAccess" with a DataType of BigInt. At this point in time I only need 23 values (or Bits) but I figured to go with the 64-Bit handling of a BigInt. Please let me know if there is a better way, I'll look into VarBinary DataTypes.

However, this made the Querying of what I need faster than ever! I was impressed! For instance, if I need all the Managers in the App:

Select * From Users Where SecurityAccess & Power(2, 4) > 0

There it is, short and sweet!

robvolk
Most Valuable Yak

15732 Posts

Posted - 2004-10-11 : 22:44:42

Take a shot at creating a calculated column and indexing it, you may see an even bigger improvement.

tymberwyld
Starting Member

4 Posts

Posted - 2004-10-11 : 22:48:21

Would you happen to have a sample Script? I'm not too familiar with Calculated Columns...and I'm not sure what it would be calculating. I don't have a Bit Column for each setting because the Settings can grow / shrink over the course of the App's lifetime...so I didn't want to "hard-code" Columns or have to Create / Delete Columns everytime a setting was Added / Deleted. In the begining I thought about Child Tables to store the info, but that would be insane to maintain because I need this info in 3 different tables.

robvolk
Most Valuable Yak

15732 Posts

Posted - 2004-10-11 : 22:59:47

ALTER TABLE Users ADD Level4 AS SIGN(SecurityAccess & 16) -- gives a 1 or 0 if 4th bit is set
CREATE INDEX idx_Users_Level4 ON Users(Level4) -- index column
SELECT * FROM Users WHERE Level4=1 -- regular query

Forgot to mention that using this method to index the computed column lets the query optimizer choose an index seek instead of a table scan, which can greatly improve the query performance.

Even if you indexed the SecurityAccess column, since you were originally doing a bitwise operation in the WHERE clause:

WHERE SecurityAccess & Power(2, 4) > 0

That index can't be used, because the bitwise expression is to the left of the greater-than operator. Nor could this expression be written in a different way. This is known as a non-SARGable expression (SARG = search argument). A SARGable expression places a column value alone on the left side of a comparison operator:

WHERE Level4=1

The optimizer can then look for an index on that column and use it to evaluate the query.

coolerbob
Aged Yak Warrior

841 Posts

Posted - 2006-09-17 : 20:21:00

I've put a little something together. Just paste it into Visual Studio.NET
Any comments anyone?

Module sqlteam_version
'Introduction:
'In T-SQL, bitwise operations are generally not the fastest way to get results. That's because
'you are working with indexes -like phonebooks. When you literally use a phonebook you don't use
'bitwise comparisons. You use the alphabet. Bitwise comparison are fine for a microchip but not
'much good for an index. So the challenge is to translate the bitmask into something than the query
'optimizer can use.
'That is what's done here. The mask is turned into a set of SQL OR statements.
'So "1010" (which is 10 in the enumeration) becomes "WHERE FilterEnum=10 OR FilterEnum=11
'OR FilterEnum=10 OR FilterEnum=14 OR FilterEnum=15".
'That will mean that all Filter SProcs will use dynamic SQL.
'This example uses 16 bits. But you will probably use 64 or more in the real world.
'If this approach seems to combersome or it turns out to be too slow, then individual bit
'columns would be the only remaining solution.
'In such a case we would not need a Bit Mask column as well.
'The benefit of one bit mask column is that only one index has to be searched.
'We also still need to decide between having a normal SQL column that all the relevant SProcs update
'or a calculated column that calls a deterministic function. Either will slow down updates and creates.
'Side Point: If your deterministic function needs to use the current date, pick it up from a single-
'record table that has its date value updated every x seconds by a SQL Task on a Schedule.
'If the calculated column with an index on it is not significantly slower (for filters and updates)
'than a normal column, then we will stick with that.

'0 0000000000000000 0 All
'1 0000000000000001 2^0 CurrentEmployee
'2 0000000000000010 2^1 Manager
'3 0000000000000011 2^1+2^0 CurrentEmployee,Manager
'4 0000000000000100 2^2 HomeWorker
'5 0000000000000101 2^2+2^0 HomeWorker,CurrentEmployee
'6 0000000000000110 2^2+2^1 HomeWorker,Manager
'7 0000000000000111 2^2+2^1+2^0 HomeWorker,CurrentEmployee,Manager
'8 0000000000001000 2^3 SpecialNeedsEmployee
'9 0000000000001001 2^3+2^0 SpecialNeedsEmployee,CurrentEmployee
'10 0000000000001010 2^3+2^1 SpecialNeedsEmployee,Manager
'11 0000000000001011 2^3+2^1+2^0 SpecialNeedsEmployee,CurrentEmployee,Manager
'12 0000000000001100 2^3+2^2 SpecialNeedsEmployee,HomeWorker
'13 0000000000001101 2^3+2^2+2^0 SpecialNeedsEmployee,HomeWorker,CurrentEmployee
'14 0000000000001110 2^3+2^2+2^1 SpecialNeedsEmployee,HomeWorker,Manager
'15 0000000000001111 2^3+2^2+2^1+2^0 SpecialNeedsEmployee,HomeWorker,CurrentEmployee,Manager

'If you can't remember your maths from school:
'http://techsupt.winbatch.com/webcgi/webbatch.exe?techsupt/tsleft.web+Tutorials+Boolean~Math~and~Boolean~Algebra~Refresher.txt

'On the filter screen, a case statement will check for one of the combinations in this enumeration by starting from the bottom up.
'It will then pass an enum val to the function.
Public Enum FilterCombination
All
CurrentEmployee
Manager
CurrentEmployee_Manager
HomeWorker
HomeWorker_CurrentEmployee '5
HomeWorker_Manager
HomeWorker_CurrentEmployee_Manager
SpecialNeedsEmployee_CurrentEmployee
SpecialNeedsEmployee_Manager
SpecialNeedsEmployee_CurrentEmployee_Manager '10
SpecialNeedsEmployee_HomeWorker
SpecialNeedsEmployee_HomeWorker_CurrentEmployee
SpecialNeedsEmployee_HomeWorker_Manager
SpecialNeedsEmployee_HomeWorker_CurrentEmployee_Manager
End Enum

Private Function GetSQLForBitmask(ByVal andSelection As FilterCombination, ByVal notSelection As FilterCombination) As String
Dim sAnd As String = ""
Dim sNot As String = ""

Select Case andSelection 'These result in a T-SQL OR
Case 1
sAnd = "(FilterEnum=1 OR FilterEnum=3 OR FilterEnum=5 OR FilterEnum=7 OR FilterEnum=9 OR FilterEnum=11 OR FilterEnum=13 OR FilterEnum=15)"
Case 2
sAnd = "(FilterEnum=2 OR FilterEnum=3 OR FilterEnum=6 OR FilterEnum=7 OR FilterEnum=10 OR FilterEnum=11 OR FilterEnum=14 OR FilterEnum=15)"
Case 3
sAnd = "(FilterEnum=3 OR FilterEnum=7 OR FilterEnum=11 OR FilterEnum=15)"
Case 4
sAnd = "(FilterEnum=4 OR FilterEnum=5 OR FilterEnum=6 OR FilterEnum=12 OR FilterEnum=13 OR FilterEnum=14 OR FilterEnum=15)"
Case 5
sAnd = "(FilterEnum=5 OR FilterEnum=7 OR FilterEnum=13 OR FilterEnum=15)"
Case 6
sAnd = "(FilterEnum=6 OR FilterEnum=7 OR FilterEnum=14 OR FilterEnum=15)"
Case 7
sAnd = "(FilterEnum=7 OR FilterEnum=15)"
Case 8
sAnd = "(FilterEnum=8 OR FilterEnum=9 OR FilterEnum=10 OR FilterEnum=11 OR FilterEnum=12 OR FilterEnum=13 OR FilterEnum=14 OR FilterEnum=15)"
Case 9
sAnd = "(FilterEnum=9 OR FilterEnum=11 OR FilterEnum=13 OR FilterEnum=15)"
Case 10
sAnd = "(FilterEnum=10 OR FilterEnum=11 OR FilterEnum=14 OR FilterEnum=15)"
Case 11
sAnd = "(FilterEnum=11 OR FilterEnum=15)"
Case 12
sAnd = "(FilterEnum=12 OR FilterEnum=12 OR FilterEnum=14 OR FilterEnum=15)"
Case 13
sAnd = "(FilterEnum=13 OR FilterEnum=15)"
Case 14
sAnd = "(FilterEnum=14 OR FilterEnum=15)"
Case 15
sAnd = "(FilterEnum=15)"
End Select

Select Case notSelection 'These result in a T-SQL AND
Case 1
sNot = "(FilterEnum<>1 AND FilterEnum<>3 AND FilterEnum<>5 AND FilterEnum<>7 AND FilterEnum<>9 AND FilterEnum<>11 AND FilterEnum<>13 AND FilterEnum<>15)"
Case 2
sNot = "(FilterEnum<>2 AND FilterEnum<>3 AND FilterEnum<>6 AND FilterEnum<>7 AND FilterEnum<>10 AND FilterEnum<>11 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 3
sNot = "(FilterEnum<>3 AND FilterEnum<>7 AND FilterEnum<>11 AND FilterEnum<>15)"
Case 4
sNot = "(FilterEnum<>4 AND FilterEnum<>5 AND FilterEnum<>6 AND FilterEnum<>12 AND FilterEnum<>13 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 5
sNot = "(FilterEnum<>5 AND FilterEnum<>7 AND FilterEnum<>13 AND FilterEnum<>15)"
Case 6
sNot = "(FilterEnum<>6 AND FilterEnum<>7 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 7
sNot = "(FilterEnum<>7 AND FilterEnum<>15)"
Case 8
sNot = "(FilterEnum<>8 AND FilterEnum<>9 AND FilterEnum<>10 AND FilterEnum<>11 AND FilterEnum<>12 AND FilterEnum<>13 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 9
sNot = "(FilterEnum<>9 AND FilterEnum<>11 AND FilterEnum<>13 AND FilterEnum<>15)"
Case 10
sNot = "(FilterEnum<>10 AND FilterEnum<>11 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 11
sNot = "(FilterEnum<>11 AND FilterEnum<>15)"
Case 12
sNot = "(FilterEnum<>12 AND FilterEnum<>12 AND FilterEnum<>14 AND FilterEnum<>15)"
Case 13
sNot = "(FilterEnum<>13 AND FilterEnum<>15)"
Case 14
sNot = "(FilterEnum<>14 AND FilterEnum<>15)"
Case 15
sNot = "(FilterEnum<>15)"
End Select

If sAnd.Length > 0 Then
If sNot.Length > 0 Then
Return String.Concat(sAnd, " AND ", sNot)
Else
Return sAnd
End If
Else
Return sNot
End If
End Function

Sub Main()
'test
'Normally you would base what parameters you pass in to the function on what the user
'specified on your screen...
Debug.WriteLine(GetSQLForBitmask(FilterCombination.SpecialNeedsEmployee_Manager, FilterCombination.All))
'Required result: (FilterEnum=9 OR FilterEnum=11 OR FilterEnum=13 OR FilterEnum=15)
End Sub

End Module

coolerbob
Aged Yak Warrior

841 Posts

Posted - 2007-05-17 : 12:24:42

If I have an int column as I decribed in my previous post, and I want to unset (set to zero/off) one of the bits, how do I do that?
Setting it on is easy.
update MyTable
set MyCol=MyCol| 2

In the above example, this is the result if 8 was in the MyCol: 1000 OR 0010 = 1010 (8 or 2 = 10)

But if I wanted to switch one bit off, e.g. turn 1010 back into 1000, how do you do that?
I can test wether bit #1 is on or not because (using MyCol & 2):
1101 AND 0010 = 0000
1111 AND 0010 = 0010

But how do I in SQL turn a bit off if it's on? How do I turn 10 into 8, 6 into 4, 14 into 12, 15 into 13, 11 into 9, etc...
It looks like you just subtract two if the Bitwise AND operation is non-zero.
Is that right?

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2007-05-17 : 13:11:25

if you have

0110

and you want to "unset" the second bit (from the right), you just AND it with:

1101

which gives you:

0100

- Jeff
http://weblogs.sqlteam.com/JeffS

jsmith8858
Dr. Cross Join

7423 Posts

Posted - 2007-05-17 : 13:12:28

Let me add: I have no idea why anyone would store data as bits in an INT like this in T-SQL. Why would you want to do this?

- Jeff
http://weblogs.sqlteam.com/JeffS

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2007-05-17 : 14:04:40

flags maybe?

_______________________________________________
Causing trouble since 1980
blog: http://weblogs.sqlteam.com/mladenp

Kristen
Test

22859 Posts

Posted - 2007-05-17 : 14:06:35

I've had situations where I wanted bit-fields of "properties" that I wanted to match on.

Dunno if it was efficient or not, but that's how we did it!

Kristen

coolerbob
Aged Yak Warrior

841 Posts

Posted - 2007-05-18 : 04:22:34

quote:
Originally posted by jsmith8858

Let me add: I have no idea why anyone would store data as bits in an INT like this in T-SQL. Why would you want to do this?

- Jeff
http://weblogs.sqlteam.com/JeffS

Performance boost. Currently I have to do some joins and where clauses to establish this information. Picking up on column from one table is a whole lot faster.

I'm now at the performance tuning part of this particular project. The old database before I arrived was badly de-normalized. I came in and made a normalized one and converted the denormalized data from the old db into the new. They've been running on the new db for owver a year now and all is well. Now we are adding some denormalized bits to add performance gains - while of course leaving the normalized original source data in place.

coolerbob
Aged Yak Warrior

841 Posts

Posted - 2007-05-18 : 04:27:57

quote:
Originally posted by jsmith8858

if you have

0110

and you want to "unset" the second bit (from the right), you just AND it with:

1101

which gives you:

0100

- Jeff
http://weblogs.sqlteam.com/JeffS

Thanks!

update MyTable
set MyCol=MyCol & 14

I was being a little thick there...

coolerbob
Aged Yak Warrior

841 Posts

Posted - 2007-08-10 : 08:23:14

Some of you may have a use for grey codes too.
You can read more about that here:
http://en.wikipedia.org/wiki/Grey_code

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources