Microsoft Interview Question
Software Engineer / DevelopersHere we could use strings - string representation of the original number and the string representation of the number stored on a computer.
Given the number N, lets just store it using appropriate data type. Then, we get a string of this stored value. Lets now compare this string with the actual number entered as a string. If they equal, then bingo - we can store it accurately.
Just take the fractional part .2782783, multiply it with 2, disregard real part of the result and again multiply with 2, keep doing this untill u get 0.00 or infinite repeated sequence.
If you get 0.00 at the end, then it can be represented accurately in binary, otherwise it can not be.
For example consider .1 case...
Step 1: Begin with the decimal fraction and multiply by 2. The whole number part of the result is the first binary digit to the right of the point.
Because .1 x 2 = 0.2, the first binary digit to the right of the point is a 0.
So far, we have .1 (decimal) = .0??? . . . (base 2) .
Step 2: Next we disregard the whole number part of the previous result (0 in this case) and multiply by 2 once again. The whole number part of this new result is the second binary digit to the right of the point. We will continue this process until we get a zero as our decimal part or until we recognize an infinite repeating pattern.
Because .2 x 2 = 0.4, the second binary digit to the right of the point is also a 0.
So far, we have .1 (decimal) = .00?? . . . (base 2) .
Step 3: Disregarding the whole number part of the previous result (again a 0), we multiply by 2 once again. The whole number part of the result is now the next binary digit to the right of the point.
Because .4 x 2 = 0.8, the third binary digit to the right of the point is also a 0.
So now we have .1 (decimal) = .000?? . . . (base 2) .
Step 4: We multiply by 2 once again, disregarding the whole number part of the previous result (again a 0 in this case).
Because .8 x 2 = 1.6, the fourth binary digit to the right of the point is a 1.
So now we have .1 (decimal) = .0001?? . . . (base 2) .
Step 5: We multiply by 2 once again, disregarding the whole number part of the previous result (a 1 in this case).
Because .6 x 2 = 1.2, the fifth binary digit to the right of the point is a 1.
So now we have .1 (decimal) = .00011?? . . . (base 2) .
Step 6: We multiply by 2 once again, disregarding the whole number part of the previous result. Let's make an important observation here. Notice that this next step to be performed (multiply 2. x 2) is exactly the same action we had in step 2. We are then bound to repeat steps 2-5, then return to Step 2 again indefinitely. In other words, we will never get a 0 as the decimal fraction part of our result. Instead we will just cycle through steps 2-5 forever. This means we will obtain the sequence of digits generated in steps 2-5, namely 0011, over and over. Hence, the final binary representation will be.
.1 (decimal) = .00011001100110011 . . . (base 2) .
One Performance issue is if the last digit in fraction part is 1,2,3,4,6,7,8,9 in this case it cannot be represented accurately in binary form...
only if last digit is 0 or 5 then repeat the process that mentioned above.
int n = (fractional part)
boolean result = false;
while(true){
if(n==0) {
result = true; break;
}
if(n%10!=0 && n%2 ==0){
break;
}
if(n%10==0) n=n/10;
if(n==5) {
result = true; break;
}
n=n*2;
}
Its Working I tested for lot of examples
To convert numbers between 0 and 1, take the decimal expression and repeat-
edly multiply it by 2. At each step, keep track of the integer part of the
result but do not carry it along in subsequent multiplications. For
example, convert decimal 0.7 to binary:
0.7 * 2 = 1.4
0.4 * 2 = 0.8
0.8 * 2 = 1.6
0.6 * 2 = 1.2
0.2 * 2 = 0.4
0.4 * 2 = 0.8
0.8 * 2 = 1.6
0.6 * 2 = 1.2 etc. Note that we have started to repeat previous
results. Now read the integer parts occurring on
the right side, from the top down: the binary
representation of decimal 0.7 is 0.1011001100...
where the "1100" repeats forever.
so whatever number after decimal ends in 5 will become 0 eventually following above procedure and wil not be non-repeating..... therefore can be represented accurately.
319 (or 319.0), 63.5, 1/16(or 0.0625), 5.390625 can be represented accuratley in binary.
A decimal number can be represented accurately in binary if there exists k such that 2^k*number is an integer.
- PP June 15, 2007In our case the number is 0.2782783 (76 can be ignored).
So we can simply loop through k from 1 to 23 (assuming single precision) and see if 0.2782783*2^k is an integer or not or equivalently 2782783*2^k*10^-7 is an integer.
To get over with integer overflow problems, whenever we get k such that 2782783*2^k = p*10^q then the problem reduces to finding if there exists k1 such that p*2^k1*10^(-7+k) is an integer or not.