16
\$\begingroup\$

Input

Positive integers a and b defining an interval of integers [a .. b].

Output

The maximum number of trailing zeros in the binary expansion of any integer in the interval [a .. b].

Examples

Input: [17 .. 21] ; Output: 2 ; since 20 corresponds to 10100

Input: [22 .. 37] ; Output: 5 ; since 32 corresponds to 100000

\$\endgroup\$
3
  • 7
    \$\begingroup\$ Will a and b always be low-high in that order? \$\endgroup\$ Apr 12 at 17:19
  • 10
    \$\begingroup\$ I'd suggest including more test cases, in particular where it matters that the interval includes its endpoints. \$\endgroup\$
    – xnor
    Apr 12 at 17:30
  • 1
    \$\begingroup\$ Welcome to the CGCC stack, nice question! +1 on both of the above. I imagine "yes" to the first (otherwise nice solutions like xnor's will have to reorder appropriately, which does not seem core to the challenge). \$\endgroup\$ Apr 12 at 20:03

17 Answers 17

16
\$\begingroup\$

Python, 27 bytes

lambda a,b:len(bin(-a&b))-3

Try it online!

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

Try it online!

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)

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ lambda a,b:len(bin(-a&b))-3 appears to work just as well. \$\endgroup\$ Apr 13 at 5:32
4
\$\begingroup\$

Vyxal 3, 5 bytes

Port of xnors' answer

v⊻bLv

Try it Online!

v⊻bLv­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏⁠‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌­
v⊻     # ‎⁡xor(a-1, b)
  b    # ‎⁢to binary
   Lv  # ‎⁣length - 1
💎

Created with the help of Luminespire.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ @JonathanAllan The input has to be taken with the larger number on the first line and the smaller on the second line. \$\endgroup\$
    – noodle man
    Apr 12 at 22:11
  • \$\begingroup\$ You can save a byte by applying to M instead of using a mapping lambda: 6 bytes ꜝR2ᵛMG \$\endgroup\$
    – noodle man
    Apr 12 at 22:13
  • \$\begingroup\$ (So the input in the Try it Online! link needs reversing) \$\endgroup\$ Apr 13 at 0:23
  • \$\begingroup\$ Port of xnor's solution is 5 bytes \$\endgroup\$ Apr 13 at 2:57
3
\$\begingroup\$

Perl 5 -pl, 23 bytes

Same idea as @xnor's answer but uses the power of 2 rather than bitstring length to save bytes.

$_=0|log(--$_^<>)/log 2

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Uiua 0.11.0, 11 bytes SBCS (updated)

/↥⊗1⋯+⇡+1-,

Try on Uiua Pad!

Takes b a and returns the maximum number of trailing zeros.

Explanation

+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

Also 11 bytes

-1⧻⋯⍜⋯/≠⊟-1

Direct port of @xnor's answer. Takes a b.

\$\endgroup\$
0
3
\$\begingroup\$

sed -r, 72 69 66 59 bytes

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

Try it online!

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,

sed -r, 66 59 bytes

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

Try it online!

basically the same, but gets rid of an expensive regex grouping.

\$\endgroup\$
2
\$\begingroup\$

APL+WIN, 33 bytes.

Prompts for lower then higher integer. Index origin=0

⌈/+⌿~∨⍀⊖((⌈2⍟n)⍴2)⊤m+⍳1+(n←⎕)-m←⎕

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 31 bytes

f=(a,b)=>a>b?-1:1+f(a+1>>1,b/2)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 4 bytes

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]\$

How?

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’

TIO

...or, indeed, with Albert.Lang's improvement over there - N&BL’

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 99 98 89 88 74 bytes

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

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can remove the cast to float, because C. \$\endgroup\$
    – corvus_192
    Apr 15 at 19:11
  • 1
    \$\begingroup\$ And move the declaration of f inside the function. \$\endgroup\$
    – corvus_192
    Apr 15 at 19:26
1
\$\begingroup\$

Google Sheets, 31 bytes

=len(base(bitxor(A1-1,B1),2))-1

Put the input in cells A1:B1 and the formula in C1.

Uses xnor's magic.

trailingzeros.png

\$\endgroup\$
1
\$\begingroup\$

Zsh, 28 bytes

Port of @xnor's Python solution. Returns via exit code.

l=$[[#2]($1-1)^$2]
bye $#l-3

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python, 160 bytes

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Good first attempt. The goal is to write the shortest code possible. Can you try and see if there's a way to shorten your code? \$\endgroup\$
    – Mohammad
    Apr 15 at 11:00
1
\$\begingroup\$

Charcoal, 13 bytes

I⌈E…·NN⌕⮌⍘ι²1

Try it online! Link is to verbose version of code. Explanation:

   …·           Inclusive range from
     N          First input as a number to
      N         Second input as a number
  E             Map over values
          ι     Current value
         ⍘      Converted to base
           ²    Literal integer `2`
        ⮌       Reversed
       ⌕        Find index of
            1   Literal string `1`
 ⌈              Take the maximum
I               Cast to string
                Implicitly print

9 bytes if @Albert.Lang's formula is correct:

I⊖L↨&±NN²

Try it online! Link is to verbose version of code. Explanation:

      N     First input as a number
     ±      Negated
    &       Bitwise And
       N    Second input as a number
   ↨        Convert to base
        ²   Literal integer `2`
  L         Take the length
 ⊖          Decremented
I           Cast to string
            Implicitly print
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 5 bytes

ŸÓøнà

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)
\$\endgroup\$
0
\$\begingroup\$

Pip, 9 bytes

DBL:DaBXb

Try It Online!

Explanation

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
\$\endgroup\$
0
\$\begingroup\$

PowerShell, 97 bytes

$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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 33

Port of xnor's answer.

f(a,b){a=31-__builtin_clz(-a&b);}

Try it online!

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.