Bitwise operators

Bitwise operators work on individual bits inside of a variable.

NameSymbolDescription
And&Both
Or|Either
Xor^Exclusive or different
Not~Invert

And (&)

ABResult
000
010
100
111

C# Implementation of Bitwise And

var result = first & second;

Or (|)

ABResult
000
011
101
111

C# Implementation of Bitwise Or

var result = first | second;

Xor (^)

ABResult
000
011
101
110

C# Implementation of Bitwise Xor

var result = first ^ second;

Not (~)

AResult
01
10

C# Implementation of Bitwise Not

var result = ~first;

Bitwise Shifting

Moves (shifts) all of the bits over in one direction

Left<<
Right>>

C# Implementation of Left Shift

The left-shift operation discards the high-order bits that are outside the range of the result type and sets the low-order empty bit positions to zero.

var result = first << 1;

C# Implementation of Right Shift

If the left-hand operand is of type int or long, the right-shift operator performs an arithmetic shift: the value of the most significant bit (the sign bit) of the left-hand operand is propagated to the high-order empty bit positions. That is, the high-order empty bit positions are set to zero if the left-hand operand is non-negative and set to one if it’s negative.

If the left-hand operand is of type uint or ulong, the right-shift operator performs a logical shift: the high-order empty bit positions are always set to zero.

var result = first >> 1;

Types of Bitwise Shifts

Arithmetic Shift

In an arithmetic shift, the bits that are shifted out of either end are discarded. In a left arithmetic shift, zeros are shifted in on the right; in a right arithmetic shift, the sign bit (the MSB in two’s complement) is shifted in on the left, thus preserving the sign of the operand.

   00010111 (decimal +23) LEFT-SHIFT
=  00101110 (decimal +46)
   10010111 (decimal −105) RIGHT-SHIFT
=  11001011 (decimal −53)

Logical Shift

In a logical shift, zeros are shifted in to replace the discarded bits. Therefore, the logical and arithmetic left-shifts are exactly the same.

However, as the logical right-shift inserts value 0 bits into the most significant bit, instead of copying the sign bit, it is ideal for unsigned binary numbers, while the arithmetic right-shift is ideal for signed two’s complement binary numbers.

Circular Shift

Rotate

The value that is shifted into the right during a left-shift is whatever value was shifted out on the left, and vice versa for a right-shift operation. This is useful if it is necessary to retain all the existing bits, and is frequently used in digital cryptography.

Rotate through Carry

Rotate through carry is a variant of the rotate operation, where the bit that is shifted in (on either end) is the old value of the carry flag, and the bit that is shifted out (on the other end) becomes the new value of the carry flag. This can simulate logical or arithmetic shift. Rotate through carry is especially useful when performing shifts on numbers larger than the processor’s native word size.

Usage

Toggling boolean

public static bool ToggleBool(bool value)
{
    value ^= true;
    return value;
}

Enum Flags

We can store multiple enum values or flags inside of a singe value

public static void EnumFlags()
{
    // setting one value
    var colors = Colors.Blue;
    Console.WriteLine(ConvertToBinaryString((byte)colors));

    // setting multiple enums at once
    colors = Colors.Blue | Colors.White;
    Console.WriteLine(ConvertToBinaryString((byte)colors));

    // validating a particular enum has been set
    if ((colors & Colors.Blue) == Colors.Blue)
    {
        // we have blue
        Console.WriteLine("Contains blue");
    }
}

[Flags]
public enum Colors
{
    Red = 1,
    Blue = 2,
    Green = 4,
    Black = 8,
    White = 16,
    Orange = 32,
    Yellow = 64,
    Pink = 128
}

Masking

Masking is a similar concept to binary enums.

public static void Masking()
{
    // 0011100 Input
    // 0000100 Important bit
    // 0000100 Result
    var input = Colors.Blue;
    var mask = Colors.White;
    var result = input & mask;
}

[Flags]
public enum Colors
{
    Red = 1,
    Blue = 2,
    Green = 4,
    Black = 8,
    White = 16,
    Orange = 32,
    Yellow = 64,
    Pink = 128
}

Further example of masking operations. Examples from stackoverflow:

// The casts to object in the below code are an unfortunate necessity due to
// C#'s restriction against a where T : Enum constraint. (There are ways around
// this, but they're outside the scope of this simple illustration.)
public static class FlagsHelper
{
    public static bool IsSet<T>(T flags, T flag) where T : struct
    {
        int flagsValue = (int)(object)flags;
        int flagValue = (int)(object)flag;

        return (flagsValue & flagValue) != 0;
    }

    public static void Set<T>(ref T flags, T flag) where T : struct
    {
        int flagsValue = (int)(object)flags;
        int flagValue = (int)(object)flag;

        flags = (T)(object)(flagsValue | flagValue);
    }

    public static void Unset<T>(ref T flags, T flag) where T : struct
    {
        int flagsValue = (int)(object)flags;
        int flagValue = (int)(object)flag;

        flags = (T)(object)(flagsValue & (~flagValue));
    }
}

C# Notes

  • Bitwise and shift operations never cause overflow.

Additional Resources

Problems

  • Count 1 Bits