Monday, 10 June 2019

Algorithms | Increment a number by one without using addition operator


Write a program to increment a number by one without using operators like ‘+’, ‘-‘, ‘*’, ‘/’, ‘++’, ‘–‘ …etc.

Examples:
Input: 20
Output: 21

We can achieve the functionality using bitwise operators.

Approach:
To increment the bit, we need to add 1 in binary representation. However, the addition is not allowed.
So we can check each bit and flip it using bitwise operators.

Step#1 Flip all the set bits until we find a 0. (Alternate to Carry forward in addition)
Step#2 Flip the rightmost 0 bit (Add the new value at right side).

Bitwise representation of 20 is 10100.

public class IncrementByOne {
     public static void main(String[] args) {
          int value = 20;
          value = increment(20);
          System.out.println(value);
     }

     private static int increment(int number) {
          int one = 1;

          /* Flip all the set bits until we find a 0 */
          while ((number & one) != 0) {
               number = number ^ one;
               one <<= 1;
          }

          /* flip the rightmost 0 bit */
          number = number ^ one;
          return number;
     }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...