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 2^m+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;
    }
}

Advertisement