Java中的二进制间隙程序 [英] Binary Gap Program in Java

问题描述

我的问题陈述:

正整数 N 中的二进制间隙是 N 的二进制表示中两端被 1 包围的任何连续零的最大序列.例如，数字 9 的二进制表示为 1001，并且包含长度为 2 的二进制间隙. 数字 529 的二进制表示为 1000010001，包含两个二进制间隙:长度为 4 的一个和长度为 3 的一个.数字 20 的二进制表示为 10100，包含一个长度为 1 的二进制间隙.数字 15 的二进制表示为 1111，没有二元差距.数字 32 的二进制表示为 100000，并且没有二进制间隙.

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

我的代码:

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；根据我的逻辑，在 input:1041 的情况下，它应该只存储间隙值 5 和 3，即使 5 和 3 也存储在 ArrayList 中但位于其他索引处.

I am trying to show the output of binary gap that is stored in my ArrayList. But the output is quite different for a given input of 1041. I don't know why it is storing 1,2,3,4; according to my logic it should store only the gap values 5 and 3 in case of input:1041, even though 5 and 3 are also stored in the ArrayList but at some other index.

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

I think there is a problem in the do-while loop especially in al.add(ctr) but I haven't figured it out yet.

推荐答案

如果这是为了作业，你的问题在这里:

If this is for homework, your problem is here:

    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.

• You update k as you go along, but you don't update j, so you get 1 through whatever the proper value is ([1, 2, 3, 4, 5, 1, 2, 3] instead of [5, 3]).
• You don't need k at all.

    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 类，它在 CPU 上使用非常非常快的 CPU 指令拥有它们:

If you're not doing this for homework, and you need performance for a real-world use, use Java's built-in bitwise methods in the Integer class, which use very, very fast CPU instructions on CPUs that have them:

import java.util.Arrays;

public class Abc {
    static final int[] gaps(int n) {
        final int[] untrimmedResult = new int[15];
        int i = 0;

        // Remove trailing zeroes and last one bit to get to first gap.
        n >>>= Integer.numberOfTrailingZeros(n) + 1;
        while (n != 0) {
            final int gapSize = Integer.numberOfTrailingZeros(n);
            untrimmedResult[i++] = gapSize;
            n >>>= gapSize + 1;
        }

        final int[] result = new int[i];
        System.arraycopy(untrimmedResult, 0, result, 0, i);
        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)));
    }
}

这是显示在这里工作，尽管它以相反的顺序给出结果(这很容易通过以相反的顺序填充 untrimmedResult 并正确调整 System.arraycopy 的参数来修复).

This is shown to work here, though it gives results in reverse order (which can be easily fixed by filling untrimmedResult in reverse order and adjusting System.arraycopy's arguments properly).

这篇关于Java中的二进制间隙程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！