1

如何使用递归函数提升二进制数组。该函数接收二进制数组 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;
}
4

1 回答 1

0

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

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]

编辑：对于您示例中的二维数组，转换为 int 并返回到您的数组格式看起来会有些不同，但我会推荐相同的方法。

于 2012-12-05T09:57:32.727 回答