Java中的Binary Gap程序 [英] 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;根据我的逻辑，在输入:1041的情况下，它应该只存储间隔值5和3，即使ArrayList中也存储了5和3却位于其他索引处.

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

这是显示在此处工作.

如果您不是要做家庭作业，并且需要在实际环境中使用性能，请在

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中的Binary Gap程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！