时间戳

首页 > 解决方案 > Java中的二进制间隙程序

java - Java中的二进制间隙程序

问题描述

我的问题陈述：

正整数 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)但我还没有弄清楚。

标签： javaloopsarraylist

解决方案

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

    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, 2, 3, 4, 5, 1, 2, 3]而不是[5, 3]），您都会得到 1 。
  • 你根本不需要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);
        }
    }

这显示在这里工作。

如果您不是为了家庭作业而这样做，并且您需要性能以供实际使用，请在Integer类中使用 Java 的内置按位方法，它在具有它们的 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)));
    }
}

这显示在这里工作。

推荐阅读