Bitwise operations may be familiar to developers having formal computer science backgrounds or experience with C-derived languages. Some developers, particularly those coming from Visual Basic or scripting backgrounds, may not have had exposure to the concept. Bitwise operations are very fast and efficient, usually only requiring one CPU cycle to calculate, once the operands are in the registers. I'll attempt to summarize the basics of bitwise operations, and illustrate how they can help simplify your code.
Representing Numbers in Binary Form
Humans work mostly with decimal numbers, in which each digit represents a power of 10. Modern computers work with binary numbers, where each digit represents a power of 2. Before we can understand bitwise operations, we must review the basics of binary numbers.
Let's look at how the integer, 170, is represented in binary form. As a decimal number, 170 is broken down by its powers of 10 as follows:
170
|||
||--10^0
|---10^1
----10^2
Expanding, we get:
(1 * 10^2) + (7 * 10^1) + (0 * 10^0) = (1 * 100) + (7 * 10) + (0 * 1) = 100 + 70 = 170
In binary numbers, each binary digit (or bit) represents a power of 2. 170 would look like:
10101010
||||||||
|||||||--2^0
||||||---2^1
|||||----2^2
||||-----2^3
|||------2^4
||-------2^5
|--------2^6
---------2^7
Expanding, we get:
(1 * 2^7) + (0 * 2^6) + (1 * 2^5) + (0 * 2^4) + (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (0 * 2^0)
Multiplying out, we get:
(1 * 128) + (0 * 64) + (1 * 32) + (0 * 16) + (1 * 8) + (0 * 4) + (1 * 2) + (0 * 1) = 128 + 32 * 8 + 2 = 170
Many modern programming environments use 32 bits of memory to store integer data. This allows representation of numbers as large as 2^32 (4,294,967,296). My example used an 8-bit integer for clarity. A 32-bit representation of the number, 170, would look like:
00000000000000000000000010101010
We'll stick with our 8-bit integer, to keep things simple.
Logical Operators
There is only one thing that can be done to a single bit, and only a few ways that two bits can be compared. These actions are called logical operations, and are considerably less complex than the operations we perform on decimal numbers.
Single Bit Operations
Not
We'll begin with the simplest concept, the logical Not operation. It involves taking the inverse of a bit. If a bit has the value 0, its inverse is 1. Likewise, if a bit has a value 1, its inverse is 0.
Not 1 = 0
Not 0 = 1
Bit Comparisons
We are often concerned with the outcome of combining two bits in an additive or multiplicative manner. When considering two bits, a and b, there four states that can be represented:
a = 0, b = 0
a = 0, b = 1
a = 1, b = 0
a = 1, b = 1
And
A logical And operation is a simple multiplication of the two bits:
0 And 0 = 0
0 And 1 = 0
1 And 0 = 0
1 And 1 = 1
Or
A logical Or operation is a simple addition of the two bits:
0 Or 0 = 0
0 Or 1 = 1
1 Or 0 = 1
1 Or 1 = 1
Xor
A logical Xor operation is like an Or operation, except that the case in which both bits have a value of 1 has a result of 0
0 Xor 0 = 0
0 Xor 1 = 1
1 Xor 0 = 1
1 Xor 1 = 0
Bitwise Operations
Bitwise operations on integers, which are just arrays of bits, involves nothing more than comparing the binary representations, bit by bit.
170: 10101010
Not 170: 01010101
170 And 34
10101010
00100010
--------
00100010
170 Or 34
10101010
00100010
--------
10101010
170 Xor 34
10101010
00100010
--------
10001000
Bitwise operations in the .Net Framework
Most languages and frameworks support bitwise operations. In .Net, the operators are summarized as follows:
C# VB.Net
Not ~ Not
And & And
Or | Or
Xor ^ Xor
Using Bitwise Operations
We sometimes use bitwise operations even when we're unaware we're doing so. Consider the ExecuteReader method of .Net's System.Data.SqlClient.SqlCommand class. One of its overloads has the following signature:
public SqlDataReader ExecuteReader(CommandBehavior behavior);
The CommandBehavior enumeration is a set of flags that can be combined in a bitwise manner, in order to fine-tune the way that the method operates. For instance, let's say that you expect to get a single row of data back (CommandBehavior.SingleRow), and you'd like to close the connection automatically, once the query has completed (CommandBehavior.CloseConnection). The method would be invoked like this (assuming we already have a SqlCommand instance named cmd):
SqlDataReader dr = cmd.ExecuteReader(CommandBehavior.SingleRow | CommandBehavior.CloseConnection);
It's very common to see sets of flags represented as bit enumerations.
Summary
Hopefully, this will be useful to someone. It's goal was to illustrate the basics of bitwise operations, how they work and how they're used. Please email me with any comments, suggestions or corrections. Happy bit flipping!
