## Bitwise operators

Bitwise operators work on individual bits inside of a variable.

Name | Symbol | Description |

And | & | Both |

Or | | | Either |

Xor | ^ | Exclusive or different |

Not | ~ | Invert |

### And (&)

A | B | Result |

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

#### C# Implementation of Bitwise And

`var result = first & second;`

### Or (|)

A | B | Result |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

#### C# Implementation of Bitwise Or

`var result = first | second;`

### Xor (^)

A | B | Result |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

#### C# Implementation of Bitwise Xor

`var result = first ^ second;`

### Not (~)

A | Result |

0 | 1 |

1 | 0 |

#### 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

- Bitwise and shift operators (C# reference)
- Boolean logical operators (C# reference)
- CTCI – Chapter 5 – Bit Manipulation
- EPI – Chapter 4 – Primitive Types
- YouTube – C# Bitwise Examples
- Binary Multiplication

## Problems

- Count 1 Bits