7
\$\begingroup\$

I have completed my homework with directions as follows:

Declare and implement a class named Binary. This class will have a method named printB(int n) that prints all binary strings of length n. For n = 3, it will print

000
001
010
011
100
101
110
111

in this order.

Here is my code:

import java.util.Scanner;
class Binary
{

    String B;
    int temp;

    void printB(int n)
    {
        for(int i = 0; i < Math.pow(2,n); i++)
        {
            B = "";
            int temp = i;
            for (int j = 0; j < n; j++)
            {
                if (temp%2 == 1)
                    B = '1'+B;
                else
                    B = '0'+B;
                    temp = temp/2;
            }
            System.out.println(B);
         }
    } 
}

class Runner
{
    public static void main(String [] args)
    {
        Scanner in = new Scanner(System.in);

        System.out.print("Enter n:");
        int n = in.nextInt();

        Binary myB = new Binary();

        myB.printB(n);
    }
}

My question is...is there anyway to make this shorter or more efficient?

\$\endgroup\$

migrated from stackoverflow.com Apr 6 '13 at 3:33

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ +1 for posting your code and not just the assignment. Nice to see someone actually trying to do the work before asking here. :-) \$\endgroup\$ – Ken White Apr 4 '13 at 1:51
  • \$\begingroup\$ Taking Math.pow() out of the header will give an optimization when n starts to get large. \$\endgroup\$ – Doug Ramsey Apr 4 '13 at 2:18
4
\$\begingroup\$

Speaking from a straight Java perspective, one thing you can do is change your loop header. You evaluate the power every iteration and could do something like:

for (int i = 0, end = Math.pow(2, n); i < end; i++)

You also use standard String concatenation which is slow because once compiled, when you concatenate two strings a StringBuffer is created, and both strings are added to it, and then resulting string is returned. You save a step by using a StringBuffer from the get go which would you replace B = ""; with B = new StringBuffer(); (of course changing it's type accordingly). Instead of adding strings to you call insert (which can be chained) like B.insert(0, "1")

You're appending a char ('0' or '1') which you evaluate with modular division, you can just prepend it like B.insert(0, (temp % 2)) and save that entire if.

I probably said more than I should have for homework, but you appear to have already solved your problem and so I was just giving advice in addition to that.

EDIT

My solution would be as follows:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter number >> ");
        int value = in.nextInt();
        in.close();
        Binary binary = new Binary(value);
        System.out.println(binary.getResult());
    }
}

class Binary {
    private int value = 0;
    private StringBuilder binaryValues;

    public Binary(int value) {
        this.value = value;
        this.binaryValues = new StringBuilder();
        this.process();
    }

    private void process() {
        for (int i = 0, end = (1 << this.value); i < end; i++) {
            StringBuilder binary = new StringBuilder(Integer.toString(i, 2));
            while (binary.length() < this.value)
                binary.insert(0, 0);
            this.binaryValues.append(binary).append("\n");
        }
    }

    public String getResult() {
        return this.binaryValues.toString();
    }
}

Maybe not shorter but no need to rewrite binary number generation when it's built in.

\$\endgroup\$
  • \$\begingroup\$ Actually, it may be a good idea to take Math.pow() out of the header. I'm not sure if this is true in Java, but in some languages, having something like this in the header will be evaluated after every loop iteration. Assigning it to a variable and then placing the variable in the loop header may be an optimization. \$\endgroup\$ – Doug Ramsey Apr 4 '13 at 1:56
  • 1
    \$\begingroup\$ @DougRamsey Last I checked the initialization step is only executed once, at loop start. From then the conditional is evaluated each loop and upon completion the increment step is executed. \$\endgroup\$ – izuriel Apr 4 '13 at 1:58
  • 2
    \$\begingroup\$ You can use 1 << n instead. \$\endgroup\$ – arshajii Apr 4 '13 at 1:58
  • \$\begingroup\$ @izuriel: Math.pow() is being evaluated on every loop iteration. This can become drastically inefficient (in general terms, but for specifically relatively large n the pow function can take a while to return) \$\endgroup\$ – Doug Ramsey Apr 4 '13 at 2:14
  • 1
    \$\begingroup\$ @DougRamsey As I said before (and in the post) moving that to the initialization steps it is only executed once. You check here to see when and how often each phase is executed. I do not evaluate Math.pow every step (and I warned against that in the post itself). \$\endgroup\$ – izuriel Apr 4 '13 at 2:34
1
\$\begingroup\$

There's a couple of things you could do to make it shorter (not more efficient). One thing is you could make

    String B;

    int temp;

non-global in the class. Also, you declared temp twice, once above the function and once in the function. Another thing to shorten it is, when you create the object "myB", you could exempt the creation of the variable.

    new Binary().printB(n);

Finally, you could shorten up the for loop with a tertiary operator like so:

    B = temp % 2 == 1 ? '1' + B : '0' + B; //instead of using if : else

I also wanted to point out that you didn't close the scanner. It's a good habit to build to always close your scanner objects. This is all just shortening code; I'm not sure if it's more efficient or not.

\$\endgroup\$
1
\$\begingroup\$

This is pretty fast and concise:

void printB(int n)    
{
    int len = (int) Math.pow(2, n);
    for(int count = 0; count < len; count++)
        System.out.println(Integer.toBinaryString(count));
}
\$\endgroup\$
  • \$\begingroup\$ Nice and clean. \$\endgroup\$ – assylias Apr 9 '13 at 9:15
0
\$\begingroup\$

This is how I would do it personally:

public static void printB(int n) {
    StringBuilder bin = new StringBuilder(n);  // represents our binary number

    for (int i = 0; i < n; i++)  // initialize to all 0s
        bin.append('0');

    int r = (1 << n);  // number of times we will iterate (2^n)
    for (int i = 0; i < r; i++) {  // iterate 2^n times
        System.out.println(bin);
        increment(bin, n - 1);
    }
}

private static void increment(StringBuilder bin, int loc) {
    if (loc < 0)  // avoids StringIndexOutOfBoundsException
        return;
    if (bin.charAt(loc) == '1') {  // bit at loc is already 1
        bin.setCharAt(loc, '0');  // set bit to 0
        increment(bin, loc - 1);  // increment at loc-1
    } else {  // bit at loc is 0, all we have to do is set it to 1
        bin.setCharAt(loc, '1');
    }
}

The increment method takes a StringBuilder representing a binary string and 'increments' it starting at loc.

\$\endgroup\$
  • \$\begingroup\$ Your binary shift is happening each iteration, probably meaningless gain but as far as efficiency goes it's not as efficient as it could be. \$\endgroup\$ – izuriel Apr 4 '13 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.