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.