107 lines
3.1 KiB
Markdown
107 lines
3.1 KiB
Markdown
# 5.2. Binary to string
|
|
|
|
> Given a real number between 0 and 1 (0.72), passed in as a double, print the binary representation. If the number can't be represented with less than 32 characters, print "ERROR"
|
|
|
|
Hints 143, 167, 173, 269, 297
|
|
|
|
How am I supposed to represent a real number in a binary form?
|
|
|
|
## Hint 1
|
|
|
|
> First do it with integers
|
|
|
|
```c++
|
|
str binaryToString(int num) {
|
|
str stringnum = "";
|
|
int biggestexp = 0;
|
|
while (num >= pow(2, biggestexp)) {
|
|
biggestexp += 1;
|
|
}
|
|
while (biggestexp >= 0) {
|
|
if (num >= 0 && num - pow(2, biggestexp) >= 0) {
|
|
num -= pow(2, biggestexp);
|
|
stringnum = "1" + stringnum;
|
|
} else {
|
|
stringnum = "0" + stringnum;
|
|
}
|
|
biggestexp -= 1;
|
|
}
|
|
return stringnum;
|
|
}
|
|
```
|
|
|
|
This should work, takes O(sqrt(num) + sqrt(num)). We need to know the biggest exponent in order to substract it. And then keep substracting it until reaching 0. Maybe some wrong c++ syntax, but should work. Now with decimals??
|
|
|
|
## Hint 2
|
|
|
|
> In a number like .893 (in base 10), what does each digit signify? What then does each digit in .10010 signify in base 2?
|
|
|
|
So just `stringnum = "." + stringnum`?
|
|
|
|
## Hint 3
|
|
|
|
> A number such as .893 (in base 10) indicates 8 \* 10^-1 + 9 \* 10^-2 + 3 \* 10^-3. Translate this system into base 2
|
|
|
|
.10010 = 1 \* 2^-1 + 0 \* 2^-2 + 0 \* 2^-3 + 1 \* 2^-4 + 0 \* 2^-5
|
|
|
|
Ok so stringnum in the opposite way, '.' added to it. Can we reverse dividing by pow(2,i) and go from low to high?
|
|
|
|
```c++
|
|
str binaryToString(int num) {
|
|
str stringnum = "";
|
|
int i = 0;
|
|
num -= pow(2, i);
|
|
while (num > 0) {
|
|
stringnum = "1" ? num % 2 == 0 : "0" + stringnum;
|
|
i += 1;
|
|
num -= pow(2, i);
|
|
}
|
|
return "." + stringnum;
|
|
}
|
|
```
|
|
|
|
This won't work for 11 -> 1011, it will create 111 and then have 6 left and nowhere to put it. So just do the other way and take longer.
|
|
|
|
## Hint 4
|
|
|
|
> How would you get the first digit in .893? If you multiplied by 10, you'd shift the values over to get 8.93. What happens if you multiply by 2?
|
|
|
|
## Hint 5
|
|
|
|
> Think about what happens for values that can't be represented accurately in binary
|
|
|
|
I'm officially lost.
|
|
|
|
## Solution
|
|
|
|
To print the decimal part of the 0.101 number, we multiply by 2 and check if 2n is >= 1. r = 2<sub>10</sub> * n = 1.01<sub>2</sub>. If r >= 1, we know that n had a 1 right after the decimal point. By doing this continuously, we can check every digit.
|
|
|
|
```java
|
|
public static String printBinary(double num) {
|
|
if (num >= 1 || num <= 0) {
|
|
return "ERROR";
|
|
}
|
|
|
|
StringBuilder binary = new StringBuilder();
|
|
binary.append(".");
|
|
while (num > 0) {
|
|
/* Setting a limit on length: 32 characters */
|
|
if (binary.length() > 32) {
|
|
return "ERROR";
|
|
}
|
|
double r = num * 2;
|
|
if (r >= 1) {
|
|
binary.append(1);
|
|
num = r - 1;
|
|
} else {
|
|
binary.append(0);
|
|
num = r;
|
|
}
|
|
}
|
|
return binary.toString();
|
|
}
|
|
```
|
|
|
|
Don't understand this logic at all. Trying with `double num = 0.7`, I get ".1011001001....".
|
|
|
|
[How to convert decimal number to binary](https://stackoverflow.com/a/39947437/4569908). |