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 addition is not allowed.

So we can check the 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);

     }

     static intincrement(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;

     }

}

Output:

21

Swapping of two numbers without using third variable

Approach#1.
Addition and Subtraction Method

Integer a, b

read a and b

a= a+b;

b=a-b;

a=a-b;

Problem:
Incorrect result when sum of numbers will exceed the Integer range.

Approach#2. 
Multiplication and Division Method

Integer a, b

read a and b

a=a*b;

b=a/b;

a=a/b;

Problems:

1. If the value of a*b exceeds the range of integer.

2. If the value of a or b is zero then it will give wrong results.

Approach#3.
XOR Method

Integer a , b

read a and b

a=a^b;

b=a^b;

a=a^b;

Best approach to solve this problem without any pitfalls.

Check Oddity

Check Oddity

Write the precise code to check the number is Odd or not.

Approach#1

Check the module 2 of number is Zero. If it Zero, number is Odd.

public boolean oddOrNot(int num) {

     return num % 2 == 1;

}

Problem: It will not return the correct result for the negative number.

Approach#2

If number is positive/negative, Subtract 2/-2 from number respectively until the number result is Zero or one.

public boolean oddOrNot(intnum) {

     int s = 0;

     if(num>0) {

           s = 2;

     } else {

           s = -2;

     }

     while(num>1) {

           num = num – s;

     }

     if(num==0) {

           return false;

     } else {

           return true;

     }

}

Complexity of given approach is O(num).

Approach#3

Example:Number = 10

Binary representation of 10 = 1010

Binary representation of 1   = 0001

Logical AND of both numbers = 0000.

A number will be Odd iff last bit of binary representation is 1.

public boolean oddOrNot(intnum) {

    return (num & 1) != 0;

}

This is highly optimized code. Since, Arithmetic and Logical operations are much faster compared to division and multiplication.

Find the element that appears once

Find the element that appears once

Given an array where every element occurs two times, except one element which occurs only once. Find the element that occurs once?

Approach#1

By using Brute Force technique, search for element which appeared once using two loops.

Complexity: O (n^2).

Approach#2

1. Sort the number.

2. Search for the element appeared once.

Complexity: O (nLogn).

Approach#3

Make a hashmap which will maintain the count of each digit.

Complexity: Worst case time of hashing may be more than O (n) and hashing requires extra space.

Approach#4

XOR all the elements of the array and the result will be the element which appeared once.

Complexity: O (n).

public class IdentifyNumber {

     public static void main(String[] args) {

           int[] array = {11,3,4,5,4,3,6,7,6,7,5};

           int num = indentifyNum(array);

           System.out.println(num);

     }

     private static int indentifyNum(int[] array) {

           int num = 0;

           for (intelement : array) {

                num = num ^ element;

           }

           return num;

     }

}

Output: 11

How to check the number is power of two?

How to check the number is power of two?

Approach #1:

Divide number by 2 reclusively to check it.

Time complexity : O(log2n).

Approach #2:

Bitwise AND the number with its just previous number should be equal to ZERO.

Example: Number = 8

Binary of 8: 1 0 0 0

Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 0 0 0 0 = 0.

Time complexity : O(1).

Approach #3:

Bitwise XOR the number with its just previous number should be sum of both numbers.

Example: Number = 8

Binary of 8: 1 0 0 0

Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 1 1 1 1 = 15.

Time complexity : O(1).

import java.util.Scanner;

public class PowOfTwo {

      public static void main(String[] args) {

            Scanner scan = new Scanner(System.in);

            int num = scan .nextInt();

            checkUsingANDOperation(num);

            checkUsingXOROperation(num);

            scan.close();

      }

      /**

       * Check Using AND Operation

       */

      private static void checkUsingANDOperation(int num) {

            if((num& (num-1))==0) {

                  System.out.println(num+" is the power of 2");

            } else {

                  System.out.println(num+" is not the power of 2");

            }

      }

      /**

       * Check Using XOR Operation

       */

      private static void checkUsingXOROperation(int num) {

            if((num^ (num-1))==2*num-1) {

                  System.out.println(num+" is the power of 2");

            } else {

                  System.out.println(num+" is not the power of 2");

            }

      }

}

Output:

8

8 is the power of 2

8 is the power of 2