C# Divide by Powers of Two (Bitwise Shift)

Use right shift to divide by powers of two. Benchmark a performance optimization.

Divide by powers of two. Division by powers of two can be optimized. Integers are represented by bits. A divisor that is a power of two—such as two, four, eight—can be replaced with a right shift instruction. This uses the >> token in high-level C# code.

Right shift operator: >> Left shift operator: <<

This program shows the use of the bitwise 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 division.Divide

Next: Dividing by 2 is equivalent (in this case) to shifting right one place. Dividing by 4 is equivalent to shifting right two places.

So: The input number 5000 is divided by two to result in 2500, and divided by four to result in 1250.

C# program that divides by powers of two and shifts 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

To use the shift right operator, you specify the two angle brackets with the points to the right. The right shift operator points right. The left shift operator points left. The left shift operator can be used to divide by powers of two.

Benchmark. Is this a worthwhile optimization? 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 four expression.

Result: The shift right operator was measurably faster, requiring 0.8 nanoseconds versus the 0.95 nanoseconds for the division.

Note: The static variable store instruction (stsfld) is part of this. More information on this instruction is available.

IL: stsfld

C# program that benchmarks division by four 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. The first program showed that you can shift to the right one place to divide by two, and shift right two places to divide by four.

Also: The second program's execution showed that using the shift right operator is faster than using the division operator.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Divide by Powers of Two (Bitwise Shift)

Related Links:

.Net

Java

Related Links