Positive integers a and b defining an interval of integers [a .. b].
The maximum number of trailing zeros in the binary expansion of any integer in the interval [a .. b].
Input: [17 .. 21] ; Output: 2 ; since 20 corresponds to 10100
Input: [22 .. 37] ; Output: 5 ; since 32 corresponds to 100000
lambda a,b:len(bin(-a&b))-3
Thanks to Albert.Lang for -1 byte from the below, using the fact that a-1==~-a.
28 bytes
lambda a,b:len(bin(a-1^b))-3
Takes the xor of a-1 and b, and outputs its length in binary minus 1. (The code subtracts 3 instead because binary strings in Python are prefixed by 0b.)
37 bytes
f=lambda a,b:-(a>b)or-~f(-~a//2,b//2)
lambda a,b:len(bin(-a&b))-3 appears to work just as well.
\$\endgroup\$
Commented
Apr 13 at 5:32
Port of xnors' answer
v⊻bLv
v⊻bLv
v⊻ # xor(a-1, b)
b # to binary
Lv # length - 1
💎
Created with the help of Luminespire.
ᵛ to M instead of using a mapping lambda: 6 bytes ꜝR2ᵛMG
\$\endgroup\$
Commented
Apr 12 at 22:13
-pl, 23 bytesSame idea as @xnor's answer but uses the power of 2 rather than bitstring length to save bytes.
$_=0|log(--$_^<>)/log 2
/↥⊗1⋯+⇡+1-,
Takes b a and returns the maximum number of trailing zeros.
+1-, # puts b-a+1 and a on stack
⇡ # range [0 ... b-a+1]
+ # add a to get [a ... b]
⋯ # get little-endian binary of each
⊗1 # get index of first 1 in each
/↥ # maximum
-1⧻⋯⍜⋯/≠⊟-1
Direct port of @xnor's answer. Takes a b.
-r, s/(.*) (.*)/dc -e2o{\1..\2}p/e #converts two numbers into a binary range
s/.*1//gm #keep only the last 0s of each line
s/.*/wc -L<<<"&"/e #num of chars in longest line
I feel like if I were smarter about it there should be a way to entierly remove that second line, but this is as good as I'll be able to get it today.
more detailed explanation:
the first swap converts two numbers seperated by a space (eg, '4 9') into
dc -e2o{4..9}p. the e flag means we execute, so bash then expands that into
dc -e2o4p -e2o5p -e2o6p -e2o7p -e2o8p -e2o9p. numbers get put on the stack, o pops one number for the output base and then p prints the top of the stack in that base.
now we have binary numbers seperated by newlines. this next swap is global and multiline. we delete everything up to and including the last 1 of each line.
now we have 0s seperated by newlines. we take the full input and send it to wc(word count). -L gives the longest line, which is our output
equivalently,
-r, s/$/}p/ #append }p
s/(.*) /dc -e2o{\1../e #swaps 'N ' for 'dc -e2o{N..' & executes full line
s/.*1//gm #keep only the last 0s of each line
s/.*/wc -L<<<"&"/e #num chars in longest line
basically the same, but gets rid of an expensive regex grouping.
Prompts for lower then higher integer. Index origin=0
⌈/+⌿~∨⍀⊖((⌈2⍟n)⍴2)⊤m+⍳1+(n←⎕)-m←⎕
rọ2Ṁ
A dyadic Link that accepts two positive integers, \$a\$ and \$b\$, and yields the maximal number of least-significant zeros of the binary representations of the range \$[a, b]\$.
Try it online! Or see a table of results for \$a, b \in [1,48]\$
rọ2Ṁ - Link: positive integer, a; positive integer, b
r - {a} inclusive range {b} -> [a..b]
2 - literal two
ọ - {[a..b]} divisibility count by {2} (vectorises)
Ṁ - maximum
xnor's solution would be five bytes (which would require \$a \le b\$, which is most likely an intended, allowed restriction) and certainly more efficient:
’^BL’
...or, indeed, with Albert.Lang's improvement over there - N&BL’
m;g(a,b){m=0;for(float f;a+~b;m=fmax((*(int*)&f>>23)-127,m))f=a&-a++;a=m;}
Probably suboptimal but I really, really, really wanted to use this hack...
-14 bytes thanks to @corvus_192 and @ceilingcat
f inside the function.
\$\endgroup\$
Commented
Apr 15 at 19:26
=len(base(bitxor(A1-1,B1),2))-1
Put the input in cells A1:B1 and the formula in C1.
Uses xnor's magic.
a, b = 17, 21
max_zeros = 0
for num in range(a, b+1):
num_zeros = (num & -num).bit_length() - 1
max_zeros = max(max_zeros, num_zeros)
print(max_zeros)
The expression num & -num finds the rightmost set bit of num. -num is the 2's complement of num, which flips all the bits of num and adds 1 to it.
Ｉ⌈Ｅ…·ＮＮ⌕⮌⍘ι²1
Try it online! Link is to verbose version of code. Explanation:
…· Inclusive range from
Ｎ First input as a number to
Ｎ Second input as a number
Ｅ Map over values
ι Current value
⍘ Converted to base
² Literal integer `2`
⮌ Reversed
⌕ Find index of
1 Literal string `1`
⌈ Take the maximum
Ｉ Cast to string
Implicitly print
9 bytes if @Albert.Lang's formula is correct:
Ｉ⊖Ｌ↨＆±ＮＮ²
Try it online! Link is to verbose version of code. Explanation:
Ｎ First input as a number
± Negated
＆ Bitwise And
Ｎ Second input as a number
↨ Convert to base
² Literal integer `2`
Ｌ Take the length
⊖ Decremented
Ｉ Cast to string
Implicitly print
ŸÓøнà
Try it online or verify both test cases.
A port of @xnor's Python answer is 5 bytes as well:
(&bg<
Try it online or verify both test cases.
Explanation:
Ÿ # Convert the (implicit) input-pair to a list in that range
Ó # Map each inner value to a list of exponents of its prime factorization
ø # Zip/transpose; swapping rows/columns
н # Pop and only leave the first column (exponents of prime 2)
à # Pop and leave the maximum
# (which is output implicitly as result)
( # Negate the first (implicit) input: -a
& # Bitwise-AND it with the second (implicit) input: -a&b
b # Convert it to binary
g # Pop and push its length
< # Decrease it by 1
# (after which it is output implicitly as result)
DBL:DaBXb
Port of xnor's Python answer.
DBL:DaBXb
Da ; Decrement first command-line input
BXb ; Bitwise XOR with second command-line input
BL: ; Bit length of result
D ; Decrement
$a,$b=180,180
$m=0
for($n=$a;$n-le$b;$n++){$m=[math]::Max($m,([math]::Log($n-band(-$n),2))-1)}
$m
aandbalways be low-high in that order? \$\endgroup\$