C# Bit Tips

Number Bit

Computers do not directly use integers. Instead they use bit patterns that represent integers. Integers are an abstraction on top of lower-level contructs. Bits are closest to the metal. They are important at all levels of optimization.

A typical use case of bitwise logical operators is to implement the notion of a small set (a bit vector). In this case, each bit of an unsigned integer represents one member of the set, and the number of bits limits the number of members. Stroustrup, p.124

Examples

In the C# language you can use bitwise operators on integers. As shown in this program, bitwise operators yield an integer results based on the value of the computed expression. They can be useful for optimizing algorithms and large data structures.

Program that uses bitwise operators [C#]

using System;

class Program
{
    static void Main()
    {
	Console.WriteLine(~1);
	Console.WriteLine(1 & 2);
	Console.WriteLine(1 | 2);
	Console.WriteLine(1 ^ 2);
	Console.WriteLine(1 >> 2);
	Console.WriteLine(1 << 2);
    }
}

Output

-2
0
3
3
0
4

Bitwise operators. The C# language provides all the standard C-style bitwise operators for you to use. These include the exclusive-or, bitwise-and, and shifting operators. They are covered in the linked tutorials.

Binary representation

How can you get the underlying bit representation of an integer in the C# language? This is possible using a variety of bitwise operators and a loop, as we see in the first linked article. Also, you can check out how incrementing an integer affects its bits.

Count bits

Every integer can be represented by a pattern of bits: some are set to one and some to zero. There are many algorithms that can be used to determine the number of bits set to one in any value. We reveal several ways you can count bits.

De Bruijn sequence: This example uses a somewhat obscure algorithm to compute the number of trailing bits on an integer. The information was adapted from a graphics programming page at Stanford University.

Summary

On modern computers, bitwise manipulation often is used as an optimization. You can represent yes or no in one bit, not one byte or more, which greatly reduces memory usage. This makes certain C# algorithms many times more efficient.