java - 递归函数提升二进制ARRAY

Question

如何使用递归函数提升二进制数组。 该函数接收二进制数组 V 并将 V 表示的数字的值增加到具有相同单位数的后续数字。如果操作可以执行，函数返回 true (java)

示例:

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

我写的是:

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;
}

Answer 1

如果我理解正确的话，您想在二进制表示中找到具有相同数量的设置位的下一个更高的整数，对吗？如果是这样，我建议:

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;
    }
}

输出:

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

编辑:对于像您的示例中这样的 2D 数组，转换为 int 并返回数组格式看起来有点不同，但我建议使用相同的方法。