C# Divide by Powers of Two

You want to divide integers by powers of two in the C# programming language. Integers are represented by bits and a divisor that is a power of two, such as two, four, or eight, can be replaced with a right shift instruction, using the >> token in high-level C# code.

Note: The right shift operator is >>. The left shift operator is <<.

Example

First, this program demonstrates the use of the shift right operator when being used to shift the bits of an integer one and two places. It compares the result of these right shift computations to the result of using a division by two and division by four. The results show that dividing by two is equivalent in this case to shifting right one place; and that dividing by four is equivalent to shifting right two places.

This C# example program shows how use right shift to divide by powers of two.

Program that divides by powers of two and shifts [C#]

using System;

class Program
{
    static void Main()
    {
	// This program uses division by powers of two and shifts.
	// ... It shows how dividing by powers of two can be done by shifting right.
	// ... The input value is determined at runtime.
	int value = int.Parse("5000");
	int value1div = value / 2;
	int value1shift = value >> 1;

	Console.WriteLine(value1div);
	Console.WriteLine(value1shift);

	int value2div = value / 4;
	int value2shift = value >> 2;

	Console.WriteLine(value2div);
	Console.WriteLine(value2shift);
    }
}

Output

2500
2500
1250
1250

Expressing divisions as right shifts. To use the shift right operator in the C# language, you specify the two angle brackets with the points to the right. The right shift operator points right, while the left shift operator points left. By the way, the left shift operator can be used to divide by powers of two. In this program, the input number 5000 is divided by two to result in 2500, and divided by four to result in 1250.

Benchmark

Let's look at a benchmark program written in the C# language that tests the performance of the shift right operator versus the performance of the divide by four expression. The results in nanoseconds per iteration of each loop are printed below the program text. In the present simulation, the shift right operator was measurably faster, requiring 0.8 nanoseconds versus the 0.95 nanoseconds for the division. Please note that the static variable store instruction is part of this.

Program that benchmarks division by four [C#]

using System;
using System.Diagnostics;

class Program
{
    static int _temp;
    const int _max = int.MaxValue;
    static void Main()
    {
	// This program shows using a right shift to divide by 4.
	// ... It benchmarks this and then regular division.
	var s1 = Stopwatch.StartNew();
	for (int i = 0; i < _max; i++)
	{
	    _temp = i >> 2;
	}
	s1.Stop();
	var s2 = Stopwatch.StartNew();
	for (int i = 0; i < _max; i++)
	{
	    _temp = i / 4;
	}
	s2.Stop();
	Console.WriteLine("{0:0.00} ns", ((s1.Elapsed.TotalMilliseconds * 1000000) /
	    (double)_max));
	Console.WriteLine("{0:0.00} ns", ((s2.Elapsed.TotalMilliseconds * 1000000) /
	    (double)_max));
	Console.Read();
    }
}

Output

0.80 ns
0.95 ns

Summary

We saw the right shift operator and its usage as a way to replace the division operator in the C# language. The first program text showed that you can shift to the right one place to divide by two, and shift right two places to divide by four. The second program's execution showed that using the shift right operator is faster than using the division operator. For the underlying hardware, shifting bits is faster than performing a logical integer operator. The C# compiler was unable to automatically reduce the division operator to a shift right operator.