The examples Make an efficient priority queue class in C#, Part 1 and Make an efficient priority queue class in C#, Part 2 explain how to make a heap-based priority queue. Those examples use a `FindMsb` method that uses bitwise operators. This post provides some extra explanation about how bitwise operators work.

# Binary Values

First, how does binary work? When you write a number in binary, suppose its bits are ABC…LMN. Each digit represents a power of 2. The rightmost digit represents 2^{0}, the next digit represents 2^{1}, the third from the right digit represents 2^{2}, and so forth.

This is similar to the way it is in base 10 where digits represent powers of 10. For example, in the number 123, the 3 represents 10^{0} = 1, the 2 represents 10^{1} = 10, and the 1 represents 10^{2} = 100. So the value 123 equals:

123 = 1 * 10^{2}+ 2 * 10^{1}+ 3 * 10^{0}= 1 * 100 + 2 * 10 + 3 * 1 = 123

Now let’s return to binary and consider the value 1101. From right-to-left the digits represent powers of 2: 2^{0}, 2^{1}, 2^{2}, and 2^{3}. So the value 1101 equals:

1101 = 1 * 2^{3}+ 1 * 2^{2}+ 0 * 2^{1}+ 1 * 2^{0}= 1 * 8 + 1 * 4 + 0 * 2 + 1 * 1 = 8 + 4 + 0 + 1 = 13

Because the leftmost digit represents the biggest power of 2, it is called the *most significant digit*. Similarly because the rightmost digit represents the smallest power of 2, it is called the *least significant digit*.

Sometimes we use those terms to mean the most or least *non-zero* significant digit. For example, in C# an int has 32 binary digits. In the value 000…01101, the true most significant digit is the leftmost digit in position 32. The most significant non-zero digit is the leftmost 1 in position 4 (if we number the digits 1, 2, 3, 4 from right-to-left).

# Bitwise Operations

C# has six bitwise operators that manipulate a value’s bits. The &, |, and ^ operators combine two values by comparing them bit-by-bit. For example, if two values have a 1 in their corresponding bits, then the & “and” operator makes the corresponding result bit equal to 1. If either of the values is 0, then the corresponding result bit is 0.

Or | “or” operator sets the result bit if either of the input bits is 1.

The ^ “xor” (exclusive or) operator sets the result bit if exactly one but not both of the input bits is 1.

Here are some examples.

01100101 & 11011001 ---------- 01000001 01100101 | 11011001 ---------- 11111101 01100101 ^ 11011001 ---------- 10111100

The << “left shift” operator shifts the bits in a value a certain number of places to the left. For example, 11011001 << 2 shifts the bits two places to the left to give 01100100. Bits that are shifted off of the left end are discarded and new bits added on the right are set to 0.

The >> “right shift” operator shifts the bits in a value a certain number of places to the right. For example, 11011001 >> 2 shifts the bits two places to the right to give 00110110. Bits that are shifted off of the right end are discarded and new bits added on the left are set to 0.

The final bit operator is the complement operator ~. It flips the bits in the input, replacing 1’s with 0s and vice versa. For example, ~11011001 is 00100110.

# Parsing and Printing Binary Values

C# does not provide easy conversion operators for working with binary values. For example, you can easily convert between strings and integers relatively easily. The operators for working with binary values are about as easy to use, they’re just harder to find because they’re not used as often.

To convert from a binary string of 0s and 1s into an integer data type, you use one of the `Convert` class’s static conversion methods. Different methods convert the string into different integer data types. The methods you can use include `ToByte`, `ToSByte`, `ToInt16`, `ToInt32`, `ToInt64`, `ToUInt16`, `ToUInt32`, and `ToUInt64`.

The second parameter to the convert method indicates the base used by the value. To convert a binary value, this parameter should be 2. (You can also use 16 to convert from hexadecimal.) For example, the following code converts the binary string “101101” into a 16-bit integer.

int value = Convert.ToInt32("101101", 2);

To create a binary string representation of a value, use the `Convert` class’s `ToString` method, giving it the second parameter 2 to indicate that it should use a binary format. (You can use 16 here to display a hexadecimal value.) For example, the following code converts `value` into a binary string.

string result = Convert.ToString(value, 2);

# Masking

Sometimes you may want to set specific bits to 0 or 1 in a value. You can do that by using the & and | operators to combine the value with a *mask*. The mask value defines the bits that will be set or cleared.

For example, suppose the mask has binary value 100. If you use the & operator to combine a value with the mask, then the result has every bit cleared except the third bit. That bit will be 1 if the corresponding bit is 1 in the input value.

Now suppose you use the | operator to combine the same mask with a value. The mask’s third bit is 1, so the third bit of the result will also be 1. Any bits in the input value that are 1 will also remain 1.

The second example (that uses |) shows how to set a specific bit. To clear a specific bit, you use & as in the first technique. Set all of the mask’s bits to 1 except the bit(s) that you want to clear and then use & to combine the mask with the input value.

It’s often inconvenient to specify the mask by giving all of the 1s that you want to preserve. One way to simplify that is to specify the bit that you want to clear and invert the mask. For example, the following pseudocode clears the third bit from the right in the input.

input = input & ~(0100)

This operation takes the mask value 01000, inverts it to get 10111, and then uses the & operator to clear the input’s third bit.

This makes sense when you write the values in binary, but C# doesn’t let you work in binary. (Well, the latest version does let you define constants in binary.) Another technique that is useful for creating mask values is to apply the << operator to the value 1. The << operator shifts the single set bit in the value 1 to the left by the number of positions that you specify.

For example, to place a 1 in the third bit, you can shift the value 1 by 2 digits to the left. The following code clears the input value’s third bit much as the preceding value does but using actual C# code.

input = input & ~(1 << 2)

Those techniques let you set or clear specific bits. You may also want to know whether a specific bit is set. To do that, use & to compare the input to a mask that has a 1 in the bit that you want to check. For example, the following code sets `fifth_bit_set` to indicate whether the input value’s fifth bit is set to 1.

bool fifth_bit_set = (input & (1 << 4)) != 0;

By using these techniques, you should be able to write methods that get, set, or clear specific bits. I’ll leave that as an exercise for you.

# LSB and MSB

Because the leftmost bit in a value represents the largest power of 2, changes to it make the biggest difference to the value. For that reason this bit is called the most significant bit (MSB). Similarly because the rightmost bit represents the smallest power of 2, it is called the least significant bit (LSB).

Note that signed integers use the leftmost bit as the sign bit. If an integer has a 1 in its leftmost bit, then it represents a negative number. That’s important for representing negative numbers, but you can usually ignore this fact when performing bitwise arithmetic. When you’re using bitwise operators, a bit is a bit. You’ll only notice weirdness when you treat the binary values as integers.

Often when we talk about the LSB and MSB we mean the largest or smallest non-zero bit. For example, in the value 00111010, the MSB is in position 6 (as numbered starting with 1 on the right) and the LSB is in position 2.

The examples mentioned earlier use the following method to find a value’s MSB.

// Return the number's most significant bit. private int FindMsb(int number) { for (int i = 31; i >= 0; i--) if ((number & (1 << i)) != 0) return i; return -1; }

By now you should be able to trace through this method to see what it does.

The code first loops from 31 down to 0. For each value, it shifts the value 1 that many places to the left to create a mask with a 1 in the corresponding position. For example, the first time through the loop the 1 is in the 32nd bit at the far left of the 32-bit integer.

The code then uses the & operator to compare the input number to the mask to see if it has a 1 in that position. If the code finds the 1, it returns the bit position. (This time numbered starting with 0 in the rightmost position.)

If you like, you should be able to write a similar method that finds the rightmost non-zero bit in a number. Or you should be able to write a method that makes a list or array containing the positions of all of the non-zero bits.

# The Example

When you change this example’s input values or select a new operator, the following code executes.

private void Calculate() { txtResult.Clear(); txtDecimalOperand2.Clear(); txtDecimalOperand1.Clear(); txtDecimalResult.Clear(); try { // Convert the binary inputs into integers. int operand1 = Convert.ToInt32(txtOperand1.Text, 2); int operand2 = Convert.ToInt32(txtOperand2.Text, 2); // Calculate the result. int result = 0; switch (cboOperator.Text) { case "&": result = (operand1 & operand2); break; case "|": result = (operand1 | operand2); break; case "^": result = (operand1 ^ operand2); break; case "<<": result = (operand1 << operand2); break; case ">>": result = (operand1 >> operand2); break; case "~": result = ~operand1; break; } // Display the result in binary. int len = Math.Max( txtOperand1.Text.Length, txtOperand2.Text.Length); txtResult.Text = Convert.ToString(result, 2).PadLeft(len,'0'); // Show the values in decimal. txtDecimalOperand1.Text = operand1.ToString(); txtDecimalOperand2.Text = operand2.ToString(); txtDecimalResult.Text = result.ToString(); } catch { } }

The method first clears the display text boxes and then uses a `try catch` block to ignore errors. (In case you enter something invalid in the input text boxes.)

The code then uses `Convert.ToInt32` to turn the binary that you entered into integers.

Next the code uses a `switch` statement to determine which operator is should use and it applies the corresponding operator.

Note that the shift operators adjust the bits in the first operand by the value of the second operand. To see a meaningful result, start by setting the shift to something relatively small like 10. Also notice what happens if you make the shift really large. In particular, see what happens when the shift is 32 or 33.

Also note that the ~ operator inverts the first operand and the second operand is ignored.

After it calculates the result, the code uses `Convert.ToString` to display the result in binary.

The method finishes by displaying the operands and result in decimal.

# Conclusion

This post explained the main ideas that you need to know to perform bitwise operations. You can use these techniques to get, set, and clear bits in C# programs.

Download the example and experiment with it to test your understanding and to learn about other details, like what happens if you shift a value by 32 bits.

Hi Rod. I do like the way you explained bitwise operations. It helped me better understand operations on bits. I wonder if the demo could be expanded to seeing what happens to TWO RGB colours, showing the colours produced by XORing, ORing and ANDing? How could the RGB colours be converted to binary?

I also think I picked up a few typos. “righ shift” is missing a t and the << in "For example, 11011001 << 2 shifts the bits two places to the right" are actually pointing to the left and not to the right. Also in the screen shot the 2nd digits from the left in operand 1 and operand 2 are ones, so wouldn't 1 & 1 make the 2nd digit from the left a 1 digit in the result? Thanks for the nice article. See you for now.

Hi Eddie. Thanks for pointing out the typos. I’ve fixed them.

With the last issue, the result was correct but the

ToStringmethod was not displaying the initial 0. The result should have been 01000001 but was displayed as 1000001 so it looked wrong. I’ve changed the code to pad the value on the left with zeros so it is as long as the operands. Look below theswitchstatement.It should not be too hard to make a bitwise RGB example. I’ll add it to my ToDo list. (Feel free to email me if I don’t get to it for a while and it seems like I’ve forgotten.)

Not a problem Rod. Once again thanks for the great explanations to your coded examples. I really enjoy reading them, especially the really technical ones. I read them, then ponder about them and then reread them after I’ve processed the information a bit (that’s probably why I’m getting more aware of things). I made a program in VB6 that makes colourful patterns (uploaded to PlanetVB, Bladed Patterns) and was going to try to reproduce the same thing in C# and freebasic as well. I had a BLACK banding problem for the blue colour which was due to XORing and I fixed it by masking the bits with an & operator. I didn’t understand fully why it worked, but after reading your article I’m starting to understand it better. I didn’t get the black band for the red and green colours, but only the blue colour so that intrigued me to the point that I needed to fix the problem (all be it by trial and error and by reading some of Lavoplve’s older posts on theForumn (a respected graphics guru years ago with lot of great knowledge and wisdom). Take care Rod and thanks for the other codes (pythagoras Tree, Pentagon Fractal) that you created in the past.