Welcome to ZOJ
70 - ZOJ Monthly, September 2008 - 1002
BS Wrong Sample

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge


IEEE 754-1985

The IEEE Standard for Binary Floating-Point Arithmetic (IEEE 754) is the most widely-used standard for floating-point computation, and is followed by many CPU and FPU implementations. The standard defines formats for representing floating-point numbers (including negative zero and denormal numbers) and special values (infinities and NaNs) together with a set of floating-point operations that operate on these values. It also specifies four rounding modes and five exceptions (including when the exceptions occur, and what happens when they do occur).

A single-precision binary floating-point number is stored in 32 bits. In theory, the number is made up of three parts.

  1. 1 bit The sign(s)
  2. 8 bit The exponent(e)
  3. 23 bit The fraction(m)
And the value of the float number is (-1)s * 2e * (1+.m) (Actually, the e is not the 8-bit unsigned integer of the exponent part, see details following).
But IEEE 754 make some special specifications:
  1. The exponent is biased by 127. For example, if you change the exponent part into an unsigned integer, and minus it by 127, the result is the "e" part.
    • if exponent = 128 and fraction is 0, the number is infinity (again depending on the sign bit), and
    • if exponent = 128 and fraction is not 0, the number being represented is not a number (NaN).
The exponent part mentioned here is after biased. It is (11111111)2 in real number.

You can see wikipedia for further details and more pictures :)


Int64 ago, there was an animal named "Fanazhe" in Mars. And you may know, he didn't like to run the sample against his solution, so people gave it a nickname "Fan Notrun" (Do you know "Fan Runrun"?)

And one day, Murphy became angry because of the wrong sample made by Fan, so he hacked the server of the God, and tried to change the RP value of poor Fan.

It is known that the RP value was stored in the server as an IEEE-754 single precision folating point number.

You may know, the internat speed of God is very slow (maybe he live in Lantian^_^), and God's computer is very strange, so Murphy can change one bit at same time, and he can change at most k times.

Murphy want to change Fan's RP as low as possible. He want to know the minimul possible number. Since Murphy don't know programming at all(do you believe?), can you help him?


One case per line.

Each case is a 32-bit integer in binary and a number K. See sample for more details.


Output the minimul possible number. One per line.


  1. The solution always exists.
  2. Any solution which the relative error is less than 1e-6 will be accepted.
  3. Don't assume too much about endianness as it varies among different platforms!

Sample Input

01000000010000000000000000000000 1

Sample Output


Author: SHANG, Zechao

Submit    Status