Different ways to add 1 to a number
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
Reading time: 30 minutes | Coding time: 5 minutes
We compared 8 different techniques to increment a number by 1 by generating the assembly code. It depends on the compiler and language as well.
The 8 different ways to increment a given variable by one (1) are:
- a = a + 1
- a++ (post increment)
- ++a (pre increment)
- a += 1
- a -=-1
- a += a/a
- a += power(a, 0)
- Increment a using bitwise operators
Following table summarizes the entire knowledge (less number of instructions mean better performance):
| # | Method | # Instructions* | Details |
|---|---|---|---|
| 1 | opengenus = opengenus + 1 | 3 | 2 MOV, 1 ADD |
| 2 | opengenus++ | 3 | 2 MOV, 1 ADD |
| 3 | ++opengenus | 1 | 1 ADD |
| 4 | opengenus += 1 | 3 | 2 MOV, 1 ADD |
| 5 | opengenus -=-1 | 3 | 2 MOV, 1 SUB |
| 6 | opengenus += opengenus/opengenus | 7 | 4 MOV, 1 CDQ, 1 DIV, 1 ADD |
| 7 | opengenus += power(opengenus, 0) | 15 | 10 MOV, 1 ADD and others |
| 8 | Bitwise | 19 | 5 MOV and others |
Hence, ++opengenus is the fastest method and using bitwise is the slowest method.
In terms of performance, following points need to be noted:
- the performance of each approach will depend on the compiler as each compiler has different approach of mapping code to instructions and internal optimizations.
- In general, ++opengenus should performance best.
- The programming language plays a role as well as each language has a different code flow which can result in one technique to be faster than the other. For example, in earlier versions of Java, subtract was faster than addition so the approach of opengenus -=-1 would have been the faster at that point.
We will try to see all the above techniques from a neutral view by looking at possible instructions and ignoring the optimizations brought in by the compiler and the programming language.
It is safe to say that all the techniques (except bitwise and power) will be equal in a modern compiler as it should be able to optimize it to a single increment operation.
opengenus is the name of our variable. Following is the detailed explanation of each technique:
opengenus = opengenus + 1
This is the most common and straight forward way to increment a number. Ideally, in programming languages, the right hand side expression is evaluated and stored in a temporary variable before assigning it to the left hand side variable.
This results in 2 memory operations and 1 arithmetic operation.
Ideally, this expression results in the following instruction sequence:
mov eax, DWORD PTR [rbp-4]
add eax, 1
mov DWORD PTR [rbp-4], eax
Note that PTR [rbp-4] and PTR [rbp-8] are different memory locations for integer. Ideally, programming languages are able to detect that the memory movements are not necessary and hence, it can be optimized as:
add DWORD PTR [rbp-4], 1
Following is the implementation in Java:
class opengenus
{
public static void main (String[] args)
{
int opengenus = 0;
long startTime = System.nanoTime();
for(int i = 0; i < 1000000; i++)
{
opengenus = opengenus + 1;
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000000.0 + " milliseconds");
}
}
opengenus++
This is same as a = a + 1. a++ will create a copy of variable a and create a temporary variable say b (which is a+1). Once the statement has been processed completely, the value of a is incremented that is b is assigned to a.
Note that in this a temporary variable is created and there are 2 memory operations which makes this costly.
The actual calls are:
mov eax, DWORD PTR [rbp-4]
lea edx, [rax+1]
mov DWORD PTR [rbp-4], edx
Again, in this case, if the variable is not being used with other variables, it will boil down to one instruction:
add DWORD PTR [rbp-4], 1
Following is the implementation in Java:
class opengenus
{
public static void main (String[] args)
{
int opengenus = 0;
long startTime = System.nanoTime();
for(int i = 0; i < 1000000; i++)
{
opengenus++;
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000000.0 + " milliseconds");
}
}
++opengenus (pre increment)
This is an optimal way to increment a variable as it boils down to one instruction in all cases. This is known as pre-increment in the sense that the value is first increment and then, used. It is the opposite of post increment (previous technique).
It includes only 1 ADD instruction. Following is the instruction:
add DWORD PTR [rbp-4], 1
Following is the implementation in Java:
class opengenus
{
public static void main (String[] args)
{
int opengenus = 0;
long startTime = System.nanoTime();
for(int i = 0; i < 1000000; i++)
{
++opengenus;
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000000.0 + " milliseconds");
}
}
opengenus += 1
This is same as "opengenus = opengenus + 1" but compilers usually modify this and it results in one ADD instruction. In general, it is same as our first method.
It will take 2 memory operations and 1 ADD operation.
mov eax, DWORD PTR [rbp-4]
add eax, 1
mov DWORD PTR [rbp-4], eax
In an optimized compiler, it will boil down to:
add DWORD PTR [rbp-4], 1
Following is the implementation in Java:
class opengenus
{
public static void main (String[] args)
{
int opengenus = 0;
long startTime = System.nanoTime();
for(int i = 0; i < 1000000; i++)
{
opengenus += 1;
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000000.0 + " milliseconds");
}
}
opengenus -=-1
It may seem that this technique involves as lot of operations but in reality, it is same as our first technique "opengenus = opengenus + 1".
It involves 2 memory operations and 1 subtract operation.
mov eax, DWORD PTR [rbp-4]
sub eax, -1
mov DWORD PTR [rbp-4], eax
It is, usually, optimized as a single add instruction:
add DWORD PTR [rbp-4], 1
Following is the implementation in Java:
class opengenus
{
public static void main (String[] args)
{
int opengenus = 0;
long startTime = System.nanoTime();
for(int i = 0; i < 1000000; i++)
{
opengenus -=-1;
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000000.0 + " milliseconds");
}
}
opengenus += opengenus/opengenus
This is a costly call as you can understand that it is involving division and adding. In general, it will include 4 memory operation, 1 copy instruction, 1 division operation and 1 addition. This sums to 7 instructions compared to 3 instructions of previous methods.
Following are the instructions:
mov eax, DWORD PTR [rbp-4]
cdq
idiv DWORD PTR [rbp-4]
mov edx, eax
mov eax, DWORD PTR [rbp-4]
add eax, edx
mov DWORD PTR [rbp-4], eax
It is, usually, optimized as a single add instruction in modern compilers:
add DWORD PTR [rbp-4], 1
Following is the implementation in Java:
class opengenus
{
public static void main (String[] args)
{
int opengenus = 0;
long startTime = System.nanoTime();
for(int i = 0; i < 1000000; i++)
{
opengenus += opengenus/opengenus;
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000000.0 + " milliseconds");
}
}
opengenus += power(opengenus, 0)
This is the costliest method.
In general, the statement opengenus += power(opengenus, 0) will evaluated to 5 MOV operations, 1 CALL instruction and 1 ADD instruction.
The CALL instruction, in turn, results in 5 MOV operations, 1 PUSH, 1 POP and 1 return instruction is executed.
In total, there will be 15 instructions.
Following is the instructions for the increment call:
mov eax, DWORD PTR [rbp-4]
mov esi, 0
mov edi, eax
call power(int, int)
mov edx, DWORD PTR [rbp-4]
add eax, edx
mov DWORD PTR [rbp-4], eax
We should take into consider the instructions for the power method as well. In case of an optimized implementation O(log N), following instructions will be generated:
power(int, int):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-20], edi
mov DWORD PTR [rbp-24], esi
mov QWORD PTR [rbp-8], 1
.L4:
cmp DWORD PTR [rbp-24], 0
jle .L2
mov eax, DWORD PTR [rbp-24]
and eax, 1
test eax, eax
je .L3
mov eax, DWORD PTR [rbp-20]
cdqe
mov rdx, QWORD PTR [rbp-8]
imul rax, rdx
mov QWORD PTR [rbp-8], rax
.L3:
mov eax, DWORD PTR [rbp-20]
imul eax, eax
mov DWORD PTR [rbp-20], eax
sar DWORD PTR [rbp-24]
jmp .L4
.L2:
mov rax, QWORD PTR [rbp-8]
pop rbp
ret
In our case where the power is zero, 5 MOV operations, 1 PUSH, 1 POP and 1 return instruction is executed.
This brings the total count to 15 instructions.
Most compilers optimize this to 1 instruction as well.
Following is the implementation in Java:
class opengenus
{
public static void main (String[] args)
{
int opengenus = 0;
long startTime = System.nanoTime();
for(int i = 0; i < 1000000; i++)
{
opengenus += Math.pow(a, 0);
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000000.0 + " milliseconds");
}
}
Increment opengenus using bitwise operators
In general using bitwise operators to increment a variable may seem to be a good approach as it will use bitwise operators which are fast. This is not the case as addition is a single call and using bitwise approach increases the number of instructions.
It involves 19 instructions consisting of 6 MOV instructions. This is the slowest approach and even modern compilers does not optimize this greatly.
Following are the generated instructions for the main code section:
mov DWORD PTR [rbp-8], 1
mov DWORD PTR [rbp-12], 0
.L5:
cmp DWORD PTR [rbp-12], 999999
jg .L2
.L4:
mov eax, DWORD PTR [rbp-4]
and eax, DWORD PTR [rbp-8]
cmp eax, 1
jne .L3
mov eax, DWORD PTR [rbp-8]
not eax
and DWORD PTR [rbp-4], eax
sal DWORD PTR [rbp-8]
jmp .L4
.L3:
mov eax, DWORD PTR [rbp-8]
or DWORD PTR [rbp-4], eax
add DWORD PTR [rbp-12], 1
jmp .L5
.L2:
mov eax, 0
pop rbp
Following is the implementation in Java:
class opengenus
{
public static void main (String[] args)
{
int opengenus = 0;
int mask = 1;
startTime = System.nanoTime();
for(int i = 0; i < 1000000; i++)
{
while ((opengenus & mask) == 1)
{
opengenus &= ~mask;
mask <<= 1;
}
opengenus |= mask;
}
endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1000000.0 + " milliseconds");
}
}
With this, you have the complete knowledge of how to increment a variable. Enjoy and write super optimized codes.
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.