Recursive function to promote binary ARRAY

Question

How can I promote binary array using recursion func. The function receives binary array V and increases the value of the number represented by V the following number with the same number of unity. Function returns true if the operation can be performed (java)

Example:

v = {0,0,0,1,1,0,0,1,1} => return true, v = {0,0,0,1,1,0,1,0,1}

i write this:

public static boolean incrementSameOnes(int[] vec)  {
    boolean succ=false;
    int[] v=new int[vec.length-1];
    if(vec.length==1){
        return false;
    }
    if (vec[vec.length-1]==1 && vec[vec.length-2]==0)
    {
        vec[vec.length-2] = 1;
        vec[vec.length-1] = 0;
        System.out.print(Arrays.toString(vec));
        return true;
    }else {
        for(int j=0;j<vec.length-1;j++)
            v[j]=vec[j];
        succ=incrementSameOnes(v);  
        }
    return succ;
}

I wrote another function that simply promotes the array one regardless of the number of unity then using recursive function I used it but I can not make a stop condition — niros, Dec 04 '12 at 07:24
What does the word _"promote"_ mean in this context? If it is _increment_, your example is incorrect. — Jim Garrison, Dec 04 '12 at 07:32
The intention is that the function increases the array but retains the same number of Unity — niros, Dec 04 '12 at 08:28
Thank you The problem is not for a bit but for representation of 0 and 1 For example the following matrix:{{101},{1,1,0},{1,1,0}} -->return{{1,0,1}{1,1,1},{0,0,1}} — niros, Dec 05 '12 at 21:29

brimborium · Answer 1 · 2012-12-06T10:06:26.200

If I understand you correctly, you want to find the next higher integer with the same amount of set bits in the binary representation, correct? If so, I propose:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] x = { 1, 1, 1, 0, 1, 1, 0 };
        System.out.println("original: " + Arrays.toString(x));
        if (promote(x)) System.out.println("promoted: " + Arrays.toString(x));
        else System.out.println("not promotable");
    }

    private static boolean promote(int[] x) {
        // convert to integer value
        int value = 0;
        for (int i = 0; i < x.length; i++) {
            value += x[x.length - 1 - i] * (1 << i);
        }
        int newValue = value + 1, maxValue = 1 << x.length;
        int nBits = getNumberOfSetBits(value);

        // increase value until same amount of set bits found
        while (newValue < maxValue && getNumberOfSetBits(newValue) != nBits)
            newValue++;

        // convert back to array
        if (newValue < maxValue) {
            for (int i = 0; i < x.length; i++) {
                x[x.length - 1 - i] = (newValue & (1 << i)) >> i;
            }
            return true;
        } else {
            return false;
        }
    }

    // kung fu magic to get number of set bits in an int
    // see http://stackoverflow.com/a/109025/1137043
    private static int getNumberOfSetBits(int i) {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }
}

output:

original: [1, 1, 1, 0, 1, 1, 0]
promoted: [1, 1, 1, 1, 0, 0, 1]

EDIT: For a 2D array like in your example, the conversion to int and back to your array format would look a bit different but I would recommend the same approach.

Thank you The problem is not for a bit but for representation of 0 and 1 For example the following matrix:{{101},{1,1,0},{1,1,0}} -->return{{1,0,1}{1,1,1},{0,0,1}} — niros, Dec 06 '12 at 07:03
I don't understand your "promotion". Can you explain that in more detail? — brimborium, Dec 06 '12 at 08:44
I just added an example for `int` arrays. Hope this is what you were looking for. ;) — brimborium, Dec 06 '12 at 09:10
And as my old implementation with integers was wrong anyway, I hereby shall delete it (it didn't help you anyway ^^) — brimborium, Dec 06 '12 at 09:12

Recursive function to promote binary ARRAY

1 Answers1