Convert String binary to integer Java

Question

While reading this book I came across converting binary to integer. The code that is given by the book is:

 // convert a String of 0's and 1's into an integer
    public static int fromBinaryString(String s) {
       int result = 0;
       for (int i = 0; i < s.length(); i++) {
          char c = s.charAt(i);
          if      (c == '0') result = 2 * result;
          else if (c == '1') result = 2 * result + 1;
       }
       return result;
    }

and the way I solved the problem is:

public static int fromBinary(String s) {
        int result = 0;
        int powerOfTwo = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if ('1' == s.charAt(i)) {
                result += Math.pow(2, powerOfTwo);
            }
            powerOfTwo++;
        }
 return result;
    }

I know my code has an extra counter and it is probably a bit slowly but the way I implement the solution is by following the polynomial definition

x = xn b^n + xn-1 b^n-1 + ... + x1 b^1 + x0 b^0.

What I don't understand is how their's solution works ? I've already debugged but still can't find what is key. Can someone explain ?

Anything wrong with Integer.parseInt(s, 2)? They simply set each "bit" of the int manually, so either 1 or 0 and bitshift. — Boris the Spider
– Boris the Spider, Commented Feb 24, 2016 at 14:41
Sidenote: the code above misses the else case which probably should be used to detect non-binary strings, i.e. characters that aren't 0 or 1. — Thomas
– Thomas, Commented Feb 24, 2016 at 14:52
@BoristheSpider it's probably more for teaching the conversion and binary itself. :) — Thomas
– Thomas, Commented Feb 24, 2016 at 14:53

Thomas · Accepted Answer · 2016-02-24 14:50:35Z

5

They basically shift the result with 2 * result and add 1 if the bit is set.

Example: 01101

1. iteration: result = 0 -> result * 2 = 0      (same as binary 00000)
2. iteration: result = 0 -> result * 2 + 1 = 1  (same as binary 00001)
3. iteration: result = 1 -> result * 2 + 1 = 3  (same as binary 00011)  
4. iteration: result = 3 -> result * 2 = 6      (same as binary 00110)
5. iteration: result = 6 -> result * 2 + 1 = 13 (same as binary 01101)

In terms of bits: 8 + 4 + 1 = 13

Alternatively you could replace result = result * 2 with result <<= 1 but adding 1 in a single statement would not work then. You could write result = (result << 1) + 1 but that's longer and harder to read than the multiplication.

edited Feb 24, 2016 at 14:50

answered Feb 24, 2016 at 14:44

Thomas

88.9k13 gold badges126 silver badges162 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Boris the Spider Over a year ago

I suppose one could first <<= in either case then add 1 if c == 1. That would save you the else, and would make it clear that the shifting always happens.

Radu Ionescu · Accepted Answer · 2016-02-24 15:16:22Z

Copying your polynomial definition x = xn b^n + xn-1 b^n-1 + ... + x1 b^1 + x0 b^0 you can rewrite this to

x = ((((...(((( xn * b + xn-1 ) * b + ...  )* b + x1 ) * b + x0

where you have b=2 for binary representation and you have n-1 parenthesis opening on the left most side.

For n=4 this reads like

x = ((((x3*2)+x2)*2+x1)*2+x0 = x3 * 2^3 + x2 * 2^2 + x1 * 2^1 + x0 * 2^0

If you are parsing the string begining with the MSB (x_n) towards LSB (x_0), when reading x_i you will have to execute

 result = result * 2 + x_i

Before executing this result would have stored the value

((...(((( xn * b + xn-1 ) * b + ...  )* b + x_(i+1) )

After executing this result would have stored the value

((...(((( xn * b + xn-1 ) * b + ...  )* b + x_i )

Reasoning by induction you can prove you compute the correct answer in the end.

Collectives™ on Stack Overflow

Convert String binary to integer Java

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related