John Sample

Bits and Bytes
posts - 103, comments - 354, trackbacks - 16

The beauty of ones, zeros, and powers of two.

One of the most unused features in .NET I have come across is the ORing and ANDing of enum values.

I've been finding myself explaining this technique several times in the last week, so I figured I'd write it all down here.

How many times have you had the need to store non-exclusive boolean values and had to write a tome of .isXXX properties?
For example, a user rights object (isAdmin, isUser, isPowerUser, etc).
Creating and checking a list of related properties, and taking actions on the myriad of combinations quickly becomes tedious and results in unmaintainable code.
This is where ORing and ANDing come in handy. These are bit wise operators, and so operate on the binary representation of numbers. 

If you are unfamiliar with binary numbers, read this next section, otherwise skip it. 


Binary
Binary is read right to left, with each column being a power of 2 of the previous column. The first column is the "ones" column, the second is the "twos" column, the third is the "fours", the fourth is the "eights" etc.
You add the values of the individual columns together for the resultant number. Here are some examples:

00000000 = 0
00000001 = 1
00000010 = 2
00000011 = 3
00001001 = 9

The above are 8 bit integers (8 columns) and thus can store a max value of 255 (11111111)
Bitwise Operators
There are several bit operators (XOR, NOR, etc.) and languages refer to them differently , but we only need 2 for this VB.NET experiment; AND and OR. When you AND or OR at the bit level, we can use a long hand notataion that looks similar to what we learned in grade school, but it operates a little differently because results are all boolean, True (1) or False (0).
AND is true when both bits are true:
1 AND 1 = 1
1 AND 0 = 0
0 AND 0 = 0

OR is true if either is true: 
1 OR 1 = 1
1 OR 0 = 1
0 OR 0 = 0


Lets AND together two 4 bit numbers:
0101 (5)
0011 (3)
---- AND
0001 (1)

Now we'll OR the same 2 numbers.
0101 (5)
0011 (3)
---- OR
0111 (7)

Since all the values in an enum are represented by integers, we can use these techniques to create long lists of non-exclusive boolean values, and store them in one number. All we have to do is treat the individual bits as true/false values.
To make sure we can do this, all the values in the enum need to be powers of 2.
Heres an enum we can use to determine what toppings to put on a pizza:
Public Enum Toppings
     Pepperoni = 1
     Mushrooms = 2
     Onions    = 4
     Anchovies = 8
     Peppers   = 16
     Pineapple = 32
End Enum

If I had a function called MakePizza that took a Toppings enum as an argument:
MakePizza(UseToppings as Toppings)

we can OR all the values we need together:
Dim MyToppings as Toppings
 MyToppings = Mushrooms OR Onions OR Peppers

The value stored in the enum is now 22:

00000010 (Mushrooms - 2)
00000100 (Onions - 4)
00010000 (Peppers - 16)
-------- OR
00010110 (22)


Inside our MakePizza function, we will need to find out the distinct values used to create UseToppings (22)
To do this we will need to AND the UseToppings variable with the values we are testing for.


Any non zero integer will represent a true result.
For example, lets test if Pepperoni was passed in.

If UseToppings AND Toppings.Pepperoni Then
 'Add pepperonis
End If

This evaluates to false (0):
00010110 (UseToppings - 22)
00000001 (Pepperoni - 1)
-------- AND
00000000 (0)
Now lets test for Onions:
If UseToppings AND Toppings.Onions Then
 'Add onions
End If

This evaluates to true (greater than 0):

00010110 (UseToppings - 22)
00000100 (Onions - 4)
-------- AND
00000100 (4) 

We can also eliminate much of the storage associated with representing this object in a database or memory.
Instead of having true/false colums named Pepperoni, Onions, Mushrooms, etc., we can store one number 22.

Although the pizza example is a bit ludicrous, this technique comes in real handy when storing a user's application rights.
You can build an enum of rights values (Edit, ReadOnly, Admin, etc.) and store them in one database column or session variable.


As a side note, the .NET spec says enums to be used this way should carry the < FLAGS() > attribute, however the complier and runtime won't stop you from doing bit operations either way.

posted on Friday, October 29, 2004 6:42 PM

Feedback

# re: The beauty of ones, zeros, and powers of two.

Hi John,

This is cool. We need to use it more in our IT applications. By using it, as u described u can get a very clear and elegant filters/conditions statements

Another, huge advantage of using it is the support for bit operators in any DB query language.

So instead of writing in your SP query like -

SELECT * FROM AUTHORS
WHERE UserRight = Mediator or UserRight = Editor

It could do bit operation like

SELECT * FROM AUTHORS
WHERE UserRight & P_UserRight > 0

Its get better when u have a long set of filters

Guy.
12/29/2004 1:59 AM | Guy S.

# re: The beauty of ones, zeros, and powers of two.

You define values for the toppings enumerator. That is why the FLAGS keyword isn't necessary.

At default the compiler will just increment by 1 for each value of enumerator. By using the flag keyword it will shift instead of add thus assigning values usable as flags for bitwise operations.
12/29/2004 3:08 AM | Ramon 'Exyll' Smits

# re: The beauty of ones, zeros, and powers of two.

There are 10 types of people in the world, those that understand binary and those that don't.

Seasons greetings all
12/29/2004 5:26 AM | Peter

# re: The beauty of ones, zeros, and powers of two.

great idea. easy to understand and implement, but never think abt it before.

pick up sth new today:)
12/29/2004 9:04 AM | tim

# re: The beauty of ones, zeros, and powers of two.

Nice job covering this topic.

I thought this was common topic covered in college, but when I implemented this on a project at a previous job. It took me a lot of time to explain it to the other programmers (one who has CS degree and one who was in CS program). Arrgh! (and not the castle as I am not dictating)

This covers the topic very well.
12/29/2004 9:35 AM | Mike

# re: The beauty of ones, zeros, and powers of two.

Great Article, Very useful and explained very simple. Congrats, that's a very nice feauture we must implement in our it projects.

Regards.

12/29/2004 10:10 AM | Carlos Lone

# The beauty of ones, zeros, and powers of two.

12/29/2004 7:18 AM | -:[web caboodle]:-

# re: The beauty of ones, zeros, and powers of two.

Another important detail about enums in .Net is the member functions ToString() and Parse().
Given the (C#) code:

public class MyClass
{

[Flags]
enum Toppings
{
Pepperoni = 1,
Mushrooms = 2,
Onions = 4,
Anchovies = 8,
Peppers = 16,
Pineapple = 32
}

public static void Main()
{
Toppings top = Toppings.Pepperoni | Toppings.Onions | Toppings.Pineapple;
string strTop = top.ToString();
Console.WriteLine(strTop);

Toppings top2 = (Toppings)Enum.Parse(typeof(Toppings), strTop);
if ((top2 & Toppings.Onions) > 0)
Console.WriteLine("Onions Selected");
}

}

This will print :

Pepperoni, Onions, Pineapple
Onions Selelcted

(without the [Flags] attribute, it would print:

37
Onions Selelcted


12/29/2004 10:46 AM | James Curran

# re: The beauty of ones, zeros, and powers of two.

Great example to explain a wonderful and useful concept.

Good Job!
12/29/2004 12:52 PM | Logic Never Fails

# re: The beauty of ones, zeros, and powers of two.

I want to thank everyone for the great feedback, corrections, and additions.
Thanks!

12/30/2004 4:36 PM | John Sample

# re: The beauty of ones, zeros, and powers of two.

Very good article.
12/31/2004 7:45 AM | Kanaiya Parmar

# This is the type of article which is very helpful

I'm happy to see this type of article. It helps foster longer term thought and mindset, instead of the immediate (and grotesque, imo) plethora of articles like "how to add a select to your datagrid!".

thank you for the concise and clear article.
1/3/2005 7:12 PM | Messy

# re: The beauty of ones, zeros, and powers of two.

It looks like you're site is being blocked at General Electric. It's categorized as "sex" by the filter. I'm working on getting it unblocked.
1/4/2005 7:47 AM | SuperJason

# re: The beauty of ones, zeros, and powers of two.



I'd appreciate it Jason.
Its being blocked a couple of other places for reasons I just can't understand.

Does GE use this software?
http://www.johnsample.com/archive/2004/12/29/239.aspx

1/4/2005 8:48 AM | John Sample

# Bitmasking using .NET enumerations

1/4/2005 8:43 PM | LyphTEC Blogs

# re: The beauty of ones, zeros, and powers of two.

I'm assuming that this would only work for an enumeration of up to 8 items? How would you deal with more than 8 items?
1/5/2005 12:34 AM | roger

# re: The beauty of ones, zeros, and powers of two.

Roger,
Since integers (the underlying type of enums) are 32 bits, you can use 32 values.
The max value of an integer is 2,147,483,647 and you just keep doubling the value until you reach that point.

I've never tried more than 32 items, but its possible they might work if it converts to long values. If anyone has tried, let me know.
1/5/2005 8:07 AM | John Sample

# re: The beauty of ones, zeros, and powers of two.

A little clarification to my last message:

Since we start with 1 and not 0, you can use 31 enum elements.
The maximum value in the enum will be 1,073,741,824 since doubling this value will give you an overflow. 2,147,483,647 is the limit on what the value can be when they are ORed together.
1/5/2005 9:41 AM | John Sample

# re: The beauty of ones, zeros, and powers of two.

You're getting mixed up. You do start with "1", but that translates to "a 1 in bit position 0", or 2 raised to the power of N, where N is the bit position (counting from 0)

Anyway you count it, 32 bits = 32 possible options.

Of course, to expression 2^32 as a signed int, you'll has to set it to -2^31, or -2,147,483,648

Now, to avoid such problems, you can specify the underlying data type of the enum

[Flags]
enum Toppings : uint
{ /* etc */ }

or even
[Flags]
enum Toppings : ulong
{ /* etc */ }

if you wanted 64 options.
1/6/2005 10:51 PM | James Curran

# re: The beauty of ones, zeros, and powers of two.

Good info James.
I forgot about using the signed representation when doubling the 31st element.
1/7/2005 8:56 AM | John Sample

# re: The beauty of ones, zeros, and powers of two.

Yep, GE uses SmartFilter. Very annoying. It took days to get it unblocked. They needed to know my life story and then some.
1/16/2005 9:02 PM | SuperJason

# re: The beauty of ones, zeros, and powers of two.

Is there a SQL Server statement that will let you utilize this concept? For example:

If roles contians all toppings on a single pizza and role_num is the value for one topping. How can I check each pizza for that topping and remove the topping if in the pizza, using a sql server statement. I cannot get (roles and role_num) to do a bitwise comparision in SQL. Thanks


Update table_pizzas
set roles = (roles - role_num)
where pizza_type = @pizza
and (roles and role_num)

3/17/2005 10:49 AM | Brian

# re: The beauty of ones, zeros, and powers of two.

You can use the &, |, and ^ operators in sql server.

In the pizza example if you had an integer column called TOPPINGS with a value of 22, you could use this statement to return the row if it has onions (4)

select row from table where (TOPPINGS & 4 > 0)

To add pineapple to the value, use this:

update row set TOPPINGS = TOPPINGS | 32

To remove the value:

update row set TOPPINGS = TOPPINGS ^ 32

Note that ^ will remove the value if its present, and add it if its not.

Hope that helps.
3/17/2005 11:31 AM | John Sample

# A beleza dos 0s e 1s, e o seu poder.....

4/1/2005 6:01 AM | CreativeMinds

# re: The beauty of ones, zeros, and powers of two.

Fantastic stuff. Simply fantastic! Thank you!
4/28/2005 12:38 PM | Stacy

# re: The beauty of ones, zeros, and powers of two.

This is basic stuff that is no longer taught. (I started my 'bit twiddling'ack in 1983 !)
5/12/2005 4:36 PM | rudy komacasr

# re: The beauty of ones, zeros, and powers of two.

wow this is even better now...

I was going through some items I marked to future reference and checked this one out again. I posted a note back in Dec 2004 and it is still getting comments less than a month ago (rudy - I agree as stated in my first post - I was surprised with my fellow programmers when I implemented this on a project)

The article is even better with some of the great additions added (James Curran - thanks)

And thanks to you John Sample (you ever get your Lowes credit card sign? LOL) for writing this article in the first place as a great starting point for discussion and therefore more learning ([Flags] attribute - I did not know about)
6/8/2005 1:53 PM | Mike

# re: The beauty of ones, zeros, and powers of two.

Just a little update:
Contrary to what some of the posts above say, the Flags attribute does not automatically give the enum ORable values. You still have to add the doubled values by hand.
6/9/2005 11:01 AM | John Sample

# re: The beauty of ones, zeros, and powers of two.

Question:
Since it works in SQLserver and normal VB.NET code, why can't I get it to work in the filterexpression for the Select method of a DataTable? I'm I missing something? Has anyone tried this? I get the following error.

Cannot perform 'And' operation on System.Int32 and System.Int32

Here is the string I am trying.

"HDID = 1 AND ((MaskOn and 0 ) = MaskOn) AND ((MaskOff and 0 ) = 0) and Page > 0"

MaskOn and MaskOff are defined in the SQLserver table as int. In my VB.NET code I already retrieved the table into a DataSet. The "0" after the "and" will not always be a zero. I am using a masking integer to build the string before my select. I have also actually tried it "19" instead of the "0".

7/7/2005 9:48 AM | Dave Birchok

# re: The beauty of ones, zeros, and powers of two.

John,

If MS had people like you writing their examples and deciding content, their help system and web site would be so much more useful and better. Try to find this explanation of bitwise compares in the MS c#.net 2005 Help or web site... It wont happen...

Thank you for this outstanding document.
4/14/2006 1:02 PM | Steve

# re: The beauty of ones, zeros, and powers of two.

Really helpful article! i googled for "arguments oring C#" and this was the first link I opened to get a comprehensive answer to my query :) smart work and keep it up.
7/11/2006 6:48 AM | Mehboob

# re: The beauty of ones, zeros, and powers of two.

Another hint:

Always define a 'None' with the value 0.
If not you will have problems with the .NET initialization system. .NET initalizise value type always to zero. In your case, this is not valid and could lead to errors.

None = 0
Pepperoni = 1
8/2/2006 9:31 AM | Eric

# re: The beauty of ones, zeros, and powers of two.

WHen is someone going to show how to clear a bit flag? Everyone has examples on setting flags and checking flags, but NOT A WORD about how to clear a flag that is already set.
8/28/2006 5:45 PM | Johnny NoGood

# re: The beauty of ones, zeros, and powers of two.

Since you asked so politely:

If its a bit array you can use the Clear method.

If you know the bit is set in an enumeration, just use the xor (^) operator.
8/28/2006 6:27 PM | John Sample

# What do you want on your tombstone? Bitwise Enums!

What do you want on your tombstone? Bitwise Enums!
11/30/2006 9:24 AM | DaveFrank.com

# re: The beauty of ones, zeros, and powers of two.

Nice article, thanks for posting it has helped me quite a bit. I do have one question though and it was almost answered in the comments above.

I see how to create enums with the flags attrib, set, remove and check for a SINGLE value of the enum in a variable set in .Net. I also can query a SINGLE value in sql server using the methods posted in the comments above. But I am not seeing how to search for a combined state.

For example
Mushrooms = 2
Onions = 4
ORed result = 6

So I would save 6 to the db

Now Select * from pizza where (toppings @ 2) = 2

Would return the pizza record with a toppings value of 6 is fine. What if the user wanted to see all records that had mushrooms (2) and Onions (4)?

Because Select * from pizza where (toppings @ 6) = 6 does not return the proper results.

I know i can do this as well
SELECT * FROM Pizza where (state & 2) = 2
union
SELECT * FROM Pizza where (state & 4) = 4

Is there a more elegant method I am missing?

Thanks
2/16/2007 10:19 AM | Pixelect

# re: The beauty of ones, zeros, and powers of two.

Sorry if this is a double post, it didn't say anything when I posted it last time and I think I may have entered the first letter wrong in the CAPTCHA.

To Pixelect, I realize this post is late, but it seems like you are asking for two different things.

Where the Toppings & 6 = 6, the pizza in question at least has BOTH mushrooms and onions. However, selecting (Toppings & 2 = 2) U[nion] (Toppings & 4 = 4) is selecting every pizza that has mushrooms, or onions, but not guaranteed to have both (but could).

For this, you could do "(state & 2 = 2) OR (state & 4 = 4)" to do it in one if statement. To limit it to just the pizzas with both toppings, you could use "(state & 2 = 2) AND (state & 4 = 4)," which is the same as saying "(state & 6 = 6)."

Another person asked how to remove items from a bit flag. A simple way to remove an item from a bit flag is to OR it in, then XOR it. That way, if it was there, it doesn't change, and if it wasn't, then it's added in the OR operation. Then, when you XOR it, it removes it guaranteed since you KNOW it was there now. You could also shift the bits around until you got what you wanted, but that takes more effort (and storage).

Taking the article's example enum:

--------------

// C#; make a pizza with Pepporoni, Mushrooms and Onions as toppings
Toppings tPizza = Toppings.Pepperoni | Toppings.Mushrooms | Topping.Onions;

// remove Onions:
tPizza = (tPizza | Toppings.Onions) ^ Toppings.Onion;

' VB.NET; make a pizza with Pepporoni, Mushrooms and Onions as toppings
Dim tPizza As Toppings = Toppings.Pepperoni Or Toppings.Mushrooms Or Topping.Onions

' remove Onions:
tPizza = (tPizza Or Toppings.Onions) XOr Toppings.Onion

--------------

You can also do it even another way. This way takes a little more thought, which is why I didn't say it first. Anyway, if you have the bit value, and you want remove any value (or sets of values in one sweep, which makes this easier when removing multiple settings at once), then you can flip the bits of the value that you want removed and AND that value with the bit value you want to remove it from.

For example, let's say we have Pizza, Mushrooms, and Onions selected:

7[base 10] = 000111 [All 3 toppings]
4[base 10] = 000100 [Onions]
2[base 10] = 000010 [Mushrooms]
1[base 10] = 000001 [Pepperoni]

Let's say, we want to remove Mushrooms (2) from all three Toppings (7).

000111 [7]
000010 [2]
--------
000101 [5]

Now, without subtraction, how do we get that result? Flip (inverse, otherwise known as the complement) the 2's bits, and AND that with the 7:

000111 [7]
111101 [complement of 2]
-------- (AND)
000101 [5]

How do you write this in code? In C#, the complement unary operator is the '~' operator. In VB.NET, the complement unary operator is the 'Not' operator.

So, working just with numbers:

---------------

// C#
int x = 7;
x &= ~2; // x = x & ~2;

' VB.NET
Dim x As Integer = 7
x = x And (Not 2)

---------------

What if you want to remove multiple values? It is done exactly the same. Let's say you want to remove Onions (4) and Mushrooms (2), which would be (6) for both:

000111 [7]
111001 [complement of 6]
-------- (AND)
000001 [1]

Working with the enum, it's just using the names instead of the integer numbers:

--------------

// C#; make a pizza with Pepporoni, Mushrooms and Onions as toppings
Toppings tPizza = Toppings.Pepperoni | Toppings.Mushrooms | Topping.Onions;

// remove Onions AND Mushrooms:
tPizza &= ~(Toppings.Mushrooms | Toppings.Onions); // tPizza = tPizza & ~(Toppings.Mushrooms | Toppings.Onions);

' VB.NET; make a pizza with Pepporoni, Mushrooms and Onions as toppings
Dim tPizza As Toppings = Toppings.Pepperoni Or Toppings.Mushrooms Or Topping.Onions

' remove Onions AND Mushrooms:
tPizza = tPizza And (Not (Toppings.Mushrooms Or Toppings.Onions))

--------------
3/17/2007 2:20 PM | Picky

# re: The beauty of ones, zeros, and powers of two.

Great post Picky!
Thanks for the info!
-john
3/17/2007 2:44 PM | John Sample

# re: The beauty of ones, zeros, and powers of two.

GR8. The most exhaustive article on this topic I've ever seen ;)
2/11/2008 8:01 AM | ProJee

Post Comment

Title  
Name  
Url
Enter the code you see:
Comment