Title: Understand bitwise operators in C#

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⁰, the next digit represents 2¹, the third from the right digit represents 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⁰ = 1, the 2 represents 10¹ = 10, and the 1 represents 10² = 100. So the value 123 equals:

123
    = 1 * 102 + 2 * 101 + 3 * 100
    = 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⁰, 2¹, 2², and 2³. So the value 1101 equals:

1101
    = 1 * 23 + 1 * 22 + 0 * 21 + 1 * 20
    = 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 to experiment with it and to see additional details.