Java 中的二进制间隙程序

Question

我的问题陈述：

正整数 N 内的二进制间隙是 N 的二进制表示中两端都被 1 包围的连续零的最大序列。例如，数字 9 具有二进制表示 1001 并且包含长度为 2 的二进制间隙。 529 具有二进制表示形式 1000010001，并包含两个二进制间隙：一个长度为 4，一个长度为 3。数字 20 具有二进制表示形式 10100，包含一个长度为 1 的二进制间隙。数字 15 具有二进制表示形式 1111，并且没有二进制间隙。数字 32 的二进制表示形式为 100000，并且没有二进制间隙。

我的代码：

public class Abc {

    static void decToBinary(int n) {

        int[] binaryNum = new int[1000];

        // counter for binary array 
        int i = 0;
        while (n > 0) {
            // storing remainder in binary array 
            binaryNum[i] = n % 2;
            n = n / 2;
            i++;
        }
        int ctr = 0, k = 0;
        ArrayList<Integer> al = new ArrayList<Integer>();

        // printing binary array in reverse order 
        for (int j = i - 1; j >= 0; j--) {
            System.out.print(binaryNum[j]);
            if (binaryNum[j] == 0) {
                k = j;
                do {
                    ctr++;
                    k++;
                } while (binaryNum[k] == 0);
                al.add(ctr);
                ctr = 0;
            }
        }

        for (int ii = 0; ii < al.size(); ii++) {
            System.out.println(al.get(ii));
        }
    }

    // driver program 
    public static void main(String[] args) {
        int n = 1041;
        decToBinary(n);
    }
}

我试图显示存储在 ArrayList 中的二进制间隙的输出。但对于给定的输入 1041，输出却截然不同。我不知道为什么它存储 1,2,3,4；根据我的逻辑，在输入：1041的情况下，它应该只存储间隙值5和3，即使5和3也存储在ArrayList中，但位于其他索引处。

我认为 do-while 循环中有一个问题，尤其是al.add(ctr)但我还没有弄清楚。

Answer 1

如果这是为了家庭作业，那么你的问题就在这里：

    for (int j = i - 1; j >= 0; j--) {
        if (binaryNum[j] == 0) {
            k = j;
            do {
                ctr++;
                k++;
            } while (binaryNum[k] == 0);
            al.add(ctr);
            ctr = 0;
        }
    }

注意：

• 您会随着进行而更新k，但不会更新，因此无论正确的值是什么（而不是） j，您都会得到 1 。[1, 2, 3, 4, 5, 1, 2, 3][5, 3]
• k你根本不需要。

    for (int j = i - 1; j >= 0; j--) {
        if (binaryNum[j] == 0) {
            int ctr = 0;
            while (binaryNum[j] == 0) {
                ctr++;
                j--;
            }
            al.add(ctr);
        }
    }

这在这里被证明是有效的。

如果您这样做不是为了家庭作业，并且需要实际使用的性能，请在类中使用 Java 的内置按位方法，Integer这些方法在具有这些方法的 CPU 上使用非常非常快的 CPU 指令：

import java.util.Arrays;

public class Abc {
    public static final int[] gaps(int n) {
        // The number of gaps is the number of one bits minus one.
        final int[] result = new int[Math.max(0, Integer.bitCount(n) - 1)];
        
        // Remove the last one bit and all bits after to get to first gap.
        n >>>= Integer.numberOfTrailingZeros(n) + 1;
        
        for (int i = result.length - 1; i >= 0; i--) {
            final int gapSize = Integer.numberOfTrailingZeros(n);
            result[i] = gapSize;
            // Remove the last one bit and all bits after to get to next gap.
            n >>>= gapSize + 1;
        }
        
        return result;
    }
    
    // Driver program 
    public static void main(final String[] args) {
        final int n = 1041;
        System.out.println(Integer.toBinaryString(n));
        System.out.println(Arrays.toString(gaps(n)));
    }
}

这在这里被证明是有效的。