Shortest binary number in range
Ruby, 138 132 bytes
->x,y{d,*a=->{a.map.with_index{|n,i|n/BigDecimal.new(2)**(i+1)}.inject(:+)||0};[a+=[1],a[-1]=d[]>=y ?0:1]while d[]<x;a}
13 bytes added for the -rbigdecimal flag. Expects input as two BigDecimals.
Sample run:
irb(main):029:0> f=->x,y{d,*a=->{a.map.with_index{|n,i|n/BigDecimal.new(2)**(i+1)}.inject(:+)||0};[a+=[1],a[-1]=d[]>=y ?0:1]while d[]<x;a}
=> #<Proc:0x00000001053a10@(irb):29 (lambda)>
irb(main):030:0> f[BigDecimal.new('0.98983459823945792125172638374187268447126843298479182647'),BigDecimal.new('0.98983459823945792125172638374187268447126843298479182648')]
=> [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1]
Explanation:
->x,y{
d,*a= # sets d to the following, and a to [] with fancy splat operator
->{ # lambda...
a.map.with_index{|n,i| # map over a with indices
n/BigDecimal.new(2)**(i+1) # this will return:
# - 0 [ /2**(i+1) ] if n is 0
# - 1 /2**(i+1) if n is 1
}.inject(:+) # sum
||0 # inject returns nil on empty array; replace with 0
}; # this lambda turns `[0, 1, 1]' into `BigDecimal(0b0.011)'
[ # `[...]while x' is a fancy/golfy way to say `while x;...;end'
a+=[1], # add a digit 1 to the array
a[-1]=d[]>=y ?0:1 # replace it with 0 if we exceeded upper bound
]while d[]<x; # do this while(below the lower bound)
a # return the array of digits
}
Mathematica, 72 bytes
IntegerDigits[#2[[-1,-1]],2,Log2@#]&@@Reap[1//.a_/;Sow@⌈a#⌉>=a#2:>2a]&
Explanation
The method is to find the smallest multiplier of form 2^n that enlarges the gap between two input numbers so that it contains an integer.
For example, 16*{0.4,0.5} = {6.4,8.} contains 7, so the answer is 7/16.
Test case
%[0.4,0.5]
(* {0,1,1,1} *)
CJam, 46
q'.-_,:M;S/{3a.+M'0e]~GM#*AM(#/(2b}/_@.=0#)<2>
Try it online
Explanation:
The general idea is: multiply both numbers by 10some big enough exponent to get integers, multiply again by 2another big enough exponent to "make room" for binary digits in integer form, integer-divide back by 10the first exponent, decrement the numbers (to get to the "x < b ≤ y" case) and convert the results to base 2. Find the first different digit (it will be 0 in the first number and 1 in the second number), and print all the digits from the second number up to and including that one.
Before starting with the multiplications, I'm adding 3 to the integer parts in order to ensure that the results have the same number of binary digits (with no leading zeros) after decrementing. At the end, I am skipping the first 2 binary digits to compensate.
q read the input as a string
'.- remove the dots
_, duplicate and get the string length
:M; store in M and pop; M-1 will be the first exponent
S/ split by space
{…}/ for each number (in string form)
3a.+ add 3 to the first digit (vectorized-add [3] to the string)
M'0e] pad to the right with '0's up to length M
this is like multiplying the decimal number with 10^(M-1)
but done as a string operation
~ evaluate the result as an integer
GM#* multiply by 16^M (G=16) = 2^(4*M) -- 4*M is the second exponent
AM(#/ divide by 10^(M-1) (A=10)
(2b decrement and convert to base 2 (array of digits)
_ duplicate the 2nd array
@ bring the first array to the top
.= vectorized-compare the arrays (digit by digit)
0# find the position of the first 0 (meaning digits are not equal)
)< increment and slice the other copy of the 2nd array before that position
2> discard the first 2 digits