Divide, powers of two

Integers are represented by bits. Division by powers of 2 can be optimized. In C# this change can lead to improved program performance.

Optimization notes

A divisor that is a power of two—such as two, four, eight—can be replaced with a right shift instruction.

Example

This program shows the use of the bitwise shift right operator. The operator is used to shift the bits of an integer one and two places.

using System;

// 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);
2500
2500
1250
1250

Benchmark

Let's look at a benchmark program written in the C# language. This program tests the performance of the shift right operator versus the performance of the divide by 4 expression.

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));
    }
}
0.80 ns
0.95 ns

Summary

We used the right shift operator to replace the division operator. You can shift to the right one place to divide by two, and shift right two places to divide by four.