C# (C++) Using bitwise operators

Question

I've been studying c# and ran accross some familiar ground from my old work in c++. I never understood the reason for bitwise operators in a real application. I've never used them, and have never been in a reason to use them. I've been studying how they work; example below shows the shift bitwise operator. Could anyone furthur explain the point of bitwise operators, and/or elaborate on there use and how they work. Maybe I'm missing something in bitwise logic.

    byte bitComp = 15;       // bitComp = 15 = 00001111b
byte bresult = (byte) ~bitComp; // bresult = 240 = 11110000b

Heres an example for the ~complement bitwise operator

byte bitComp = 15;       // bitComp = 15 = 00001111b
byte bresult = (byte) ~bitComp; // bresult = 240 = 11110000b

Answer 1

A typical use is manipulating bits that represent mutually exclusive 'flags'

Example from MSDN: Enumeration Types

[Flags]
enum Days2
{
    None = 0x0,
    Sunday = 0x1,
    Monday = 0x2,
    Tuesday = 0x4,
    Wednesday = 0x8,
    Thursday = 0x10,
    Friday = 0x20,
    Saturday = 0x40
}
class MyClass
{
    Days2 meetingDays = Days2.Tuesday | Days2.Thursday;

    Days2 notWednesday = ~(Days2.Wednesday);
}

See also SO question: Most common C# bitwise operations

Answer 2

Another typical (but I think less common) usage is to compose several numbers into one big number. An example for this can be the windows RGB macro:

#define RGB(r, g ,b)  ((DWORD) (((BYTE) (r) | ((WORD) (g) << 8)) | (((DWORD) (BYTE) (b)) << 16)))

Where you take 3 bytes and compose an integer from them the represent the RGB value.

Answer 3

I work in motion control (among other things) and the way you communicate with the drives is usually by using bit sequences. You set one bit pattern in a memory location x to set the motion profile, you set an enable bit at memory location y to start the motion, read a pattern from location z to get the status of the move, etc. The lower you go the more bit twiddling you have to perform.

Answer 4

Except for combining flags, bit logic isn't necessarily something you need in your UI code, but it is still tremendously important. For example, I maintain a binary serialization library, that needs to deal with all sorts of complex bit-packing strategies (variant length base-128 integer encoding, for example). This is one of the implementations (actually, this is a slower/safer version - there are other variants for dealing with buffered data, but they are harder to follow):

    public static bool TryDecodeUInt32(Stream source, out uint value)
    {
        if (source == null) throw new ArgumentNullException("source");

        int b = source.ReadByte();
        if (b < 0)
        {
            value = 0;
            return false;
        }

        if ((b & 0x80) == 0)
        {
            // single-byte
            value = (uint) b;
            return true;
        }

        int shift = 7;

        value = (uint)(b & 0x7F);
        bool keepGoing;
        int i = 0;
        do
        {
            b = source.ReadByte();
            if (b < 0) throw new EndOfStreamException();
            i++;
            keepGoing = (b & 0x80) != 0;
            value |= ((uint)(b & 0x7F)) << shift;
            shift += 7;
        } while (keepGoing && i < 4);
        if (keepGoing && i == 4)
        {
            throw new OverflowException();
        }
        return true;
    }

We have:

• tests to see if the most-significant-bit is set (this changes the meaning of the data)
• shifts-a-plenty
• removal of the most-significant-bit
• bitwise combination of values

This is real code, used in a real (and much used) protocol. In general, bit operations are used a lot in any kind of encoding layer.

It is also hugely important in graphics programming, for example. And lots of others.

There are also some micro-optimisations (maths intensive work etc) that can be done with bit operations.

Answer 5

An example from COM programming:

An HRESULT is an error code consisting of a 32 bit integer. The high bit is a flag indicating whether the code represents success (0) or failure (1). The next 15 bits are an integer representing what sort of error it is -- an ole automation error or a win32 error or whatever. The lower 16 bits are the actual error code.

Being able to shift bits around is quite useful when you want to get information into or out of an HRESULT.

Now, you almost always want to abstract away the bit twiddling. It's much better to have a method (or in C, a macro) that tells you whether the HRESULT is failure, rather than actually twiddling out the bit with (hr & 0x80000000) != 0 right there in your source code. Let the compiler inline it.

There are lots of examples of low-level data structures where information is crammed into words and needs to be extracted with bitwise operations.

Answer 6

Three major uses off of the top of my head:

1) In embedded applications, you often have to access memory-mapped registers, of which individual bits mean certain things (for instance the update bit in an ADC or serial register). This is more relevant to C++ than C#.

2) Calculations of checksums, like CRCs. These use shifts and masks very heavily. Before anybody says "use a standard library", I have come across non-standard checksums too many times, which have had to implemented from scratch.

3) When dealing with data which comes from another platform, which have a diffent bit or byte order (or both) from the one you are executing your code on. This is particularly true when doing software testing of embedded systems, receiving data across a network which has not been converted to network order, or processing bulk data from a data capture system. Check out the Wikipedia article on Endianness. If you are really interested, read the classic article On Holy Wars and a Call for Peace" by Danny Cohen.

Answer 7

A couple of examples:

• Communication stacks: a header attached to data in a layer of a communication stack may contain bytes where individual bits within those bytes signify something, and so have to be masked before they can be processed. Similarly, when assembling the header in the response, individual bits will then need to be set or cleared.

• Embedded software: embedded microcontrollers can have tens or hundreds of hardware registers, in which individual bits (or collections thereof) control different functions within the chip, or indicate the status of parts of the hardware.

Incidentally, in C and C++, bitfields are not recommended where portability is important, as the order of bits in a bitfield is compiler-dependent. Using masks instead guarantees which bit(s) will be set or cleared.

Answer 8

As to 'how they work': bitwise operations are one of the lowest level operations CPUs support, and in fact some bitwise operations, like NAND and NOR, are universal - you can build any operation at all out of a sufficiently large set of NAND gates. This may seem academic, but if you look at how things like adders are implemented in hardware, that's often basically what they boil down to.

As to the 'point': in a lot of higher level applications, of course, there is not much use for bit ops, but at the lowest levels of a system they are incredibly important. Just off the top of my head, things that would be very difficult to write without bit operations include device drivers, cryptographic software, error correction systems like RAID5 or erasure codes, checksums like CRC, video decoding software, memory allocators, or compression software.

They are also useful for maintaining large sets of integers efficiently, for instance in the fd_set used by the common select syscall, or when solving certain search/optimization problems.

Take a look at the source of an MPEG4 decoder, cryptography library, or operating system kernel sometime and you'll see many, many examples of bit operations being used.

Answer 9

Here's an everyday bitwise-op trick not many people have discovered:

When you have an enumerated type representing a bitfield, you need to define each enum entry as a distinct bit value, as in:

enum
{
    Option1 = 1,
    Option2 = 2,
    Option3 = 4,
    Option4 = 8,
    Option5 = 16
};

but it's easy to forget that the next item in the sequence needs to be double the last number. Using bit shifting, it makes the sequence much easier to get right:

enum
{
    Option1 = 1<<0,
    Option2 = 1<<1,
    Option3 = 1<<2,
    Option4 = 1<<3,
    Option5 = 1<<4
};

Answer 10

Left and right shift operators (<< and >>) are often used in performance critical applications which do arithmetic operations and more specifically multiplications and divisions by powers of two.

For example suppose you had to calculate the mathematical expression 5*2^7. A naive implementation would be:

int result = 5 * (int)Math.Pow(2, 7);

Using left shift operator you could write:

int result = 5 << 7;

The second expression will be orders of magnitude faster than the first and yet yielding the same result.

Answer 11

The other answers about where is important to use Bitwise Operators are exhaustive and give a wide range of reasons, all of them very true.

But there is an extra reason that, depending on the kind of person, can be important: cool-iness! ;)

Take this, an algorithm to calculate the absolute value of a number, without using any CONDITIONAL BRANCH instruction:

int abs(const int input) {
   int temp = A >> 31;
   return ( input ^ A ) - A;
}

A reason to avoid CONDITIONAL BRANCHING is that it could stop your processor pre-fetching, waiting for the condition to be verified to know to which value the PROGRAM COUNTER should be set.

So, a part from the joke, there are very good technical reason to do it.