Sum of two integers without plus operator

Problem:
Calculate the sum of two integers a and b, but you are not supposed to use + operator. For example, given a=1 and b=2, return 3.

Solution:
Given two numbers a and b, a&b returns the number formed by 1 bits on a and b. When it is left shifted by 1 bit, it is the carry.
For example, give a = 101 and b = 111(binary), a&b = 101. a&b << 1 =1010. a^b is the number formed by different bits of a and b. a&b=10.

package com.algorithm.twosum;

public class TwoSumWithoutPlusOperator {

    public static void main(String[] args) {
        System.out.println("Sum of a and b is: " + getSum(1, 2));
    }

    private static int getSum(int a, int b) {
        while (b != 0) {
            int c = a & b;
            a = a ^ b;
            b = c << 1;
        }
        return a;
    }
}

As per the above, the output is like Sum of a and b is: 3

Find 1’s how many times repeated in bits of given number

Problem:
Given a non-negative integer number num. For every number i in the range 0<i<num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num=5, you should return [0,1,1,2,1,2].

1. Native Solution:
We can simply count the bits for each number like below,

package com.algorithm.bitcount;

public class NativeSolution {

    public static void main(String[] args) {
        for (int i : countBits(5)) {
            System.out.println(i);
        }
    }

    public static int[] countBits(int num) {
        int[] result = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            result[i] = countEach(i);
        }
        return result;
    }

    public static int countEach(int num) {
        int result = 0;
        while (num != 0) {
            if (num % 2 == 1) {
                result++;
            }
            num = num / 2;
        }
        return result;
    }
}

2. Improved Solution:
For number 2(10), 4(100),6(1000),8(10000), etc the number of 1’s is 1. Any other can be converted to be 2m+x. For example, 9=8+1,10=8+2. The number of 1’s for any other number is 1+ # of 1’s in x.

package com.algorithm.bitcount;

public class ImprovedSolution {

    public static void main(String[] args) {
        for (int i : countBits(5)) {
            System.out.println(i);
        }
    }

    public static int[] countBits(int num) {
        int[] result = new int[num + 1];
        int p = 1; // p tracks the index for number x
        int pow = 1;
        for (int i = 1; i <= num; i++) {
            if (i == pow) {
                result[i] = 1;
                pow <<= 1;
                p = 1;
            } else {
                result[i] = result[p] + 1;
                p++;
            }
        }
        return result;
    }
}

Maximum product of word lengths in Java

Given string array words, find the maximum value of length(word[i])*length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
 
package com.algorithm.length;

public class WordsLength {

    public static void main(String[] args) {
        String str[] = {"abc","def"};
        System.out.println(maxProduct(str));
    }

    public static int maxProduct(String[] words) {
        if(words==null || words.length==0)
            return 0;
        int[] arr = new int[words.length];
        for(int i=0; i<words.length; i++){
            for(int j=0; j<words[i].length(); j++){
                char c = words[i].charAt(j);
                arr[i] |= (1 << (c-'a'));
            }
        }
        int result = 0;
        for(int i=0; i<words.length; i++){
            for(int j=i+1; j<words.length; j++){
                if((arr[i] & arr[j]) == 0){
                    result = Math.max(result, words[i].length()*words[j].length());
                }
            }
        }
        return result;
    }
}

Test Cases:
1. We have passed two words are “abc” and “def”. Those words don’t have any common letters. So, the output will be 9.
2. If we pass any words which have any common letters, the program has to return 0.