Objetivo

Dado um número inteiro não negativo, crie uma função que retorne a posição inicial do número dos maiores 1s consecutivos no valor binário desse número.

Quando receber uma entrada 0, retorne 0.

Se o número tiver várias faixas de igual comprimento, você deverá retornar a posição da última faixa.

Entrada

Um número inteiro maior ou igual a 0.

Saída

Um número inteiro calculado como explicado abaixo.

Regras

• Isso é código-golfe, então o código mais curto em bytes em cada idioma vence.
• As brechas padrão são proibidas.

Exemplos e casos de teste

Exemplo 1

• Sua função passa o número inteiro 142
• 142 é igual a 10001110 em binário
• A sequência mais longa é "111" (uma sequência de três)
• A sequência começa na posição 2 ^ 1
• Sua função retorna 1 como resultado

Exemplo 2

• Sua função passa o número inteiro 48
• 48 é igual a 110000 em binário
• A sequência mais longa é "11" (uma sequência de duas)
• A sequência começa na posição 2 ^ 4
• Sua função retorna 4 como resultado

Exemplo 3

• Sua função é passada o número inteiro 750
• 750 é igual a 1011101110 em binário
• A sequência mais longa é "111" (uma sequência de três)
• Como existem duas faixas de igual comprimento, retornamos a sequência posterior.
• A sequência posterior começa na posição 2 ^ 5
• Sua função retorna 5 como resultado

Geléia , 10 8 bytes

Ba\ÐƤṀċ¬

Experimente online!

Como funciona

Ba\ÐƤṀċ¬  Main link. Argument: n


B         Binary; convert n to base 2.

   ÐƤ     Apply the link to the left to all postfixes of the binary array.
 a\         Cumulatively reduce by logical AND.

          For example, the array

          [1, 0, 1, 1, 1, 0, 1, 1, 1, 0]

          becomes the following array of arrays.

          [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
             [0, 0, 0, 0, 0, 0, 0, 0, 0]
                [1, 1, 1, 0, 0, 0, 0, 0]
                   [1, 1, 0, 0, 0, 0, 0]
                      [1, 0, 0, 0, 0, 0]
                         [0, 0, 0, 0, 0]
                            [1, 1, 1, 0]
                               [1, 1, 0]
                                  [1, 0]
                                     [0]

     Ṁ    Take the lexicographical maximum, i.e., the array with the most 1's at
          the beginning, breaking ties by length.

       ¬  Yield the logical NOT of n, i.e., 0 if n > 0 and 1 if n = 0.

      ċ   Count the occurrences of the result to the right in the one to the left.

JavaScript (ES6), 41 40 36 34 bytes

Guardado 4 bytes graças a @ThePirateBay

f=x=>(k=x&x/2)?f(k):Math.log2(x)|0

Casos de teste

f=x=>(k=x&x/2)?f(k):Math.log2(x)|0

console.log(f(0))
console.log(f(142))
console.log(f(48))
console.log(f(750))

Quão?

Caso geral x> 0

Recursivamente, E a entrada x com x / 2, que reduz progressivamente os padrões de bits consecutivos, até que apenas o bit mais à direita da sequência permaneça. Mantemos uma cópia do último valor diferente de zero e determinamos a posição do seu bit mais significativo arredondando seu logaritmo de base 2 para o piso.

Abaixo estão as etapas que realizamos para x = 750 ( 1011101110 em binário).

    1011101110 --.
,----------------'
'-> 1011101110
AND 0101110111
    ----------
=   0001100110 --.
,----------------'
'-> 0001100110
AND 0000110011
    ----------
=   0000100010 --.  --> output = position of MSB = 5  (0000100010)
,----------------'                                         ^
'-> 0000100010
AND 0000010001
    ----------
=   0000000000

Caixa de borda x = 0

O caso especial x = 0leva imediatamente a Math.log2(0) | 0. O logaritmo de 0avalia para -Infinitye o OR binário bit a bit força uma coerção a um número inteiro de 32 bits. Em conformidade com a especificação da operação abstrata ToInt32 , isso fornece o esperado 0:

Se o número for NaN , +0 , −0 , + ∞ ou −∞ , retorne +0

código de máquina x86, 14 bytes

Usar o algoritmo de @ Arnauldx &= x>>1 e tomar a posição de bit mais alta da etapa anterior xse torna 0.

É possível chamar de C / C ++ com assinatura unsigned longest_set(unsigned edi);no ABI x System- x86-64. Os mesmos bytes de código de máquina decodificarão da mesma maneira no modo de 32 bits, mas as convenções de chamada padrão de 32 bits não colocam o primeiro argumento edi. (Alterar o registro de entrada para ecxou edxpara Windows _fastcall/ _vectorcallou gcc -mregparmpode ser feito sem quebrar nada.)

   address   machine-code
             bytes
                         global longest_set
 1                       longest_set:
 2 00000000 31C0             xor  eax, eax    ; 0 for input = 0
 3                       
 4                       .loop:               ; do{
 5 00000002 0FBDC7           bsr  eax, edi    ;  eax = position of highest set bit
 6                           ;; bsr leaves output unmodified when input = 0 (and sets ZF)
 7                           ;; AMD documents this; Intel manuals say unspecified but Intel CPUs implement it
 8 00000005 89F9             mov  ecx, edi
 9 00000007 D1E9             shr  ecx, 1
10 00000009 21CF             and  edi, ecx
11 0000000B 75F5             jnz .loop        ; } while (x &= x>>1);
12                       
13 0000000D C3               ret

As BSRinstruções do x86 (Bit Scan Reverse) são perfeitas para isso, fornecendo o índice de bits diretamente, em vez de contar zeros à esquerda. ( bsrnão produz 0 diretamente para a entrada = 0 como 32-lzcnt(x)faria, mas precisamos de bsr = 31-lzcnt para entradas diferentes de zero, portantolzcnt que nem salve as instruções, muito menos a contagem de bytes. Zerar o eax antes que o loop funcione devido a bsr' s comportamento semioficial de deixar o destino inalterado quando a entrada é zero.)

Isso seria ainda mais curto se pudéssemos retornar a posição MSB da execução mais longa. Nesse caso, lea ecx, [rdi+rdi](3 bytes) copiaria + shift para a esquerda em vez demov + shr(4 bytes).

Vejo este link TIO para um chamador asm que nãoexit(longest_set(argc-1));

Testando com um loop de shell:

l=(); for ((i=0;i<1025;i++));do 
    ./longest-set-bitrun "${l[@]}";   # number of args = $i
    printf "$i %#x: $?\n" $i; 
    l+=($i); 
done | m

0 0: 0
1 0x1: 0
2 0x2: 1
3 0x3: 0
4 0x4: 2
5 0x5: 2
6 0x6: 1
7 0x7: 0
8 0x8: 3
9 0x9: 3
10 0xa: 3
11 0xb: 0
12 0xc: 2
13 0xd: 2
14 0xe: 1
15 0xf: 0
16 0x10: 4
17 0x11: 4
18 0x12: 4
19 0x13: 0
20 0x14: 4
21 0x15: 4

...

747 0x2eb: 5
748 0x2ec: 5
749 0x2ed: 5
750 0x2ee: 5
751 0x2ef: 0
752 0x2f0: 4
753 0x2f1: 4
754 0x2f2: 4

Geléia , 19 17 11 bytes

HÐĿ&\ḟ0ṪBL’

Experimente online!

-6 (!) Bytes graças às fortes observações de @ Dennis

Como funciona

HÐĿ&\ḟ0ṪBL’
HÐĿ         - halve repeatedly until reaching 0 due to rounding
   &\       - cumulative AND
     ḟ0Ṫ    - final non-zero, or 0 if all elements are 0
        BL  - length of binary representation (log base 2). 0->[0]->1
          ’ - decrement

Python 2 , 45 bytes

f=lambda x:f(x&x/2)if x&x/2else len(bin(x))-3

Experimente online!

Economizou muitos bytes graças a Dennis! (Os heads-up em len(bin(...))-3vez demath.frexp )

Agradecemos ao @xnor por encontrar um bug, que felizmente era facilmente corrigível!

Perl 6 ,45 35 bytes

Esta versão altamente aprimorada é cortesia de @nwellnhof.

{.msb+1-(.base(2)~~m:g/1+/).max.to}

Experimente online!

Python 2 , 89 78 bytes

m=t=i=j=0
for c in bin(input()):
 t=-~t*(c>'0');i+=1
 if t>m:j=i;m=t
print i-j

Experimente online!

EDIT: Economizou 11 bytes graças ao Sr. Xcoder.

05AB1E , 14 12 11 bytes

bDγàŠrkrJgα

Experimente online! ou execute casos de teste .

Explicação

bDγàŠrkrJgα  Implicit input (ex: 750)
bD           Convert input to binary string and duplicate
                 '1011101110', '1011101110'
  γ          Split into groups of 1s or 0s
                 '1011101110', ['1', '0', '111', '0', '111', '0']
   à         Pull out max, parsing each as an integer
                 '1011101110', ['1', '0', '0', '111', '0'], '111'
    Šrk      Rearrange stack and get first index of max run of ones
                 ['1', '0', '0', '111', '0'], 2
       rJg   Reverse stack, join the array to a string, and get its length
                 2, 7
          α  Get absolute difference
                 5

J , 18 17 bytes

(#-0{#\\:#.~\)@#:

Experimente online!

Explicação

(#-0{#\\:#.~\)@#:  Input: integer n
               #:  Binary
     #\            Length of each prefix
       \:          Sorted down using
         #.~\      Mixed base conversion on each prefix
   0{              Get the value at index 0
  -                Subtract from
 #                 Length

C # (.NET Core) , 64 60 bytes

T=a=>(a&a/2)>0?T(a&a/2):Math.Log(a,2)<0?0:(int)Math.Log(a,2)

Experimente online!

Versão do CA # de da resposta @ Arnauld

Agradecimentos

4 bytes salvos graças a Kevin Cruijssen.

C # (.NET Core) , 131 123 + 18 = 141 bytes

a=>{string s=Convert.ToString(a,2),t=s.Split('0').OrderBy(x=>x.Length).Last();return a<1?0:s.Length-s.IndexOf(t)-t.Length;}

Experimente online!

+18 bytes para using System.Linq;

Agradecimentos

8 bytes salvos graças a Grzegorz Puławski.

Degolfed

a=>{
    string s=Convert.ToString(a,2),      // Convert to binary
    t=s.Split('0')                       // get largest group of 1's
       .OrderBy(x=>x.Length)
       .Last();
    return 
        a<1?0:                          // handle 0 case
        s.Length-s.IndexOf(t)-t.Length; // get position in reversed string
}

C # (.NET Core) , 164 161 bytes

a=>{var s=Convert.ToString(a,2);int c=0,l=0,p=0,k=0,j=s.Length-1,i=j;for(;i>=0;i--){if(s[i]>'0'){if(i==j||s[i+1]<'1'){p=i;c=0;}if(++c>=l){l=c;k=p;}}}return j-k;}

Experimente online!

Um nãoLinq solução, que tenho certeza de que poderia ser melhorada, embora nada seja imediatamente aparente.

Degolfed

a=>{
    var s=Convert.ToString(a,2); // Convert to binary
    int c=0,l=0,p=0,k=0,j=s.Length-1,i=j;
    for(;i>=0;i--)               // Loop from end of string
    {
        if(s[i]>'0')             // if '1'
        {
            if(i==j||s[i+1]<'1') // if first digit or previous digit was '0'
            {
                p=i;             // set the position of the current group
                c=0;             // reset the count
            }
            if(++c>=l)           // if count is equal or greater than current largest count
            {
                l=c;             // update largest count
                k=p;             // store position for this group
            }
        }
    }
    return j-k;                  // as the string is reversed, return string length minus position of largest group
}

Casca , 12 bytes

→S§-€¤≠Lo▲gḋ

Experimente online!

Explicação

                 Implicit input, e.g                           750
           ḋ     Convert to binary                             [1,0,1,1,1,0,1,1,1,0]
          g      Group equal elements                          [[1],[0],[1,1,1],[0],[1,1,1],[0]]
        o▲       Maximum                                       [1,1,1]
    €            Index of that substring in the binary number  3
     ¤≠L         Absolute difference of lengths                abs (3 - 10) = 7
 S§-             Subtract the two                              7 - 3 = 4
→                Increment                                     5

Geléia ,  14 13 12  11 bytes

Bµṣ0Ṫ$ƤMḢạL

Um link monádico que recebe e retorna números inteiros não negativos.

Experimente online! ou veja a suíte de testes .

Quão?

Bµṣ0Ṫ$ƤMḢạL - Main link: number, n                   e.g. 750
B           - convert to a binary list                    [1,0,1,1,1,0,1,1,1,0]
 µ          - monadic chain separation, call that b
      Ƥ     - map over prefixes:  (i.e. for [1], [1,0], [1,0,1], [1,0,1,1],...)
     $      -   last two links as a monad:                e.g.: [1,0,1,1,1,0,1,1]
   0        -     literal zero                                   0
  ṣ         -     split (prefix) at occurrences of (0)           [[1],[1,1,1],[1,1]]
    Ṫ       -     tail                                                        [1,1]
       M    - maximal indices                             [5,9]
        Ḣ   - head                                        5
          L - length (of b)                               10
         ạ  - absolute difference                         5

Geléia , 19 bytes

BŒgḄṀB
BwÇɓÇL+ɓBL_‘

Experimente online!

Obrigado a Jonathan Allan por salvar  4  6 bytes!

Eu trabalhei muito para simplesmente abandonar isso, embora seja um pouco longo. Eu realmente queria adicionar uma solução que procure literalmente a substring mais longa do1 s na representação binária ...

Explicação

BŒgḄṀB - Link auxiliar monádico. Será usado com Ç no próximo link.

B - representação binária.
 Œg - execuções em grupo de elementos iguais consecutivos.
   Convert - Converta de binário para inteiro.
    Maximum - valor máximo.
     B - Converta de inteiro para binário.


BwÇɓÇL + ɓBL_ '- Link principal.

B - Representação binária (da entrada).
  Ç - Último link como mônada. Pega o número inteiro de entrada.
 w - Primeiro índice da sub-lista.
   Start - Inicie uma cadeia diádica separada. Inverte os argumentos.
    Ç - Último link como mônada.
     L - comprimento.
      + - Adição
       Start - Inicie uma cadeia diádica separada. Inverte os argumentos.
        B - binário.
         L - comprimento.
          _ '- Subtraia e aumente o resultado (porque o Jelly usa a indexação 1).
              - Saída implícita.

Kotlin , 77 bytes

{val b=it.toString(2)
b.reversed().lastIndexOf(b.split(Regex("0+")).max()!!)}

Embelezado

{
    val b = it.toString(2)
    // Find the left position of the first instance of
    b.reversed().lastIndexOf(
            // The largest group of 1s
            b.split(Regex("0+")).max()!!)
}

Teste

var s:(Int)->Int =
{val b=it.toString(2)
b.reversed().lastIndexOf(b.split(Regex("0+")).max()!!)}
fun main(args: Array<String>) {
    r(0, 0)
    r(142, 1)
    r(48, 4)
    r(750, 5)
}

fun r(i: Int, i1: Int) {
    var v = s(i)
    println("$i -> $v [$i1] ${i1 == v}")
}

Haskell , 101 98 96 75 bytes

snd.maximum.(`zip`[0..]).c
c 0=[0]
c n|r<-c$div n 2=sum[r!!0+1|mod n 2>0]:r

Experimente online! Uso: snd.maximum.(`zip`[0..]).c $ 142rendimentos 1.

Explicação:

• cconverte a entrada em binário e, ao mesmo tempo, conta o comprimento das faixas de uma, coletando os resultados em uma lista. r<-c$div n 2recursivamente calcula o restante rdesta lista, enquanto sum[r!!0+1|mod n 2>0]:radiciona o comprimento atual da sequência a r. A compreensão da lista verifica se mod n 2>0, ou seja, se o dígito binário atual é um e, nesse caso, pega o comprimento da sequência anterior (o primeiro elemento de r) e adiciona uma. Caso contrário, a compreensão da lista estará vazia e sum[]renderá 0. Para a entrada de exemplo, c 142gera a lista [0,3,2,1,0,0,0,1,0].

• (`zip`[0..])adiciona a posição a cada elemento da lista anterior como o segundo componente de uma tupla. Para o exemplo que isso dá [(0,0),(3,1),(2,2),(1,3),(0,4),(0,5),(0,6),(1,7),(0,8)].

• maximumencontra a tupla lexicograficamente máxima nesta lista, ou seja, os comprimentos das faixas são considerados primeiro como o primeiro componente e, no caso de um empate, o segundo componente, ou seja, o índice maior, decide. Isso gera (3,1)no exemplo e sndretorna o segundo componente da tupla.

Python 2 ou 3 , 58 bytes

import math
f=lambda x:x&x>>1and f(x&x>>1)or len(bin(x))-3

Experimente online!

C (gcc) , 81 80 bytes

i,l,c,r;f(n){for(i=l=c=r=0;n;n/=2,i++)c=n&1?c+1:c>=l?r=i-(l=c),0:0;n=c<l?r:i-c;}

Experimente online!

C (gcc) , 43 bytes

Versão CA da resposta de @ Arnauld

k;f(n){n=(k=n&n/2)?f(k):(k=log2(n))<0?0:k;}

Experimente online!

MS SQL Server, 437 426 407 398 bytes

SQL Fiddle

Tenho certeza de que poderia remover quebras de linha, etc., mas isso é tão compacto quanto eu queria:

create function j(@ int)
returns int
as BEGIN
declare @a varchar(max)='',@b int,@c int=0,@d int=0,@e int=0,@f int=0,@g int=0,@h int=0
while @>0 BEGIN SELECT @a=cast(@%2 as char(1))+@a,@=@/2
END
SET @b=len(@a)
while @<@b
BEGIN
select @c=@d,@d=cast(substring(@a,@b-@,1)as int)
IF @d=1
BEGIN IF @c=0
SELECT @e=@,@g=1
else SET @g+=1 END
IF @g>=@h BEGIN select @h=@g,@f=@e END
SET @+=1
END
return @f
END

Aqui está uma versão mais legível:

create function BinaryString(@id int)
returns int
as BEGIN
  declare @bin varchar(max)
  declare @binLen int
  declare @pVal int = 0
  declare @Val int = 0
  declare @stC int = 0 --start of current string of 1s
  declare @stB int = 0 --start of biggest string of 1s
  declare @lenC int = 0 --length of current string of 1s
  declare @lenB int = 0 --length of biggest string of 1s

  set @bin = ''

    while @id>0
      BEGIN
        SET @bin = cast(@id%2 as varchar(1)) + @bin
        SET @id = @id/2
      END

    SET @binLen = len(@bin)

    while @id<@binLen
      BEGIN
        set @pVal = @Val
        set @Val = cast(substring(@bin,@binLen-@id,1) as int)
        IF @Val = 1 and @pVal = 0
          BEGIN 
            SET @stC = @id
            SET @lenC = 1
          END
        IF @Val = 1 and @pVal = 1
          BEGIN 
            SET @lenC = @lenC + 1
          END
        IF @lenC >= @lenB
          BEGIN
            set @lenB = @lenC
            set @StB = @StC
          END

        SET @id = @id + 1 
      END

  return @StB
END

O verdadeiro truque é que, até onde pude encontrar, não há funcionalidade SQL nativa para converter um número de decimal em binário. Como resultado, tive que codificar a conversão para binário manualmente, para poder compará-la como uma sequência, um caractere de cada vez, até encontrar o número certo.

Tenho certeza de que há uma maneira melhor de fazer isso, mas não vi uma resposta (n) SQL, então achei que a lançaria lá.

APL (Dyalog Unicode) , 22 caracteres = 53 bytes

Requer ⎕IO←0qual é o padrão em muitos sistemas.

⊃⌽⍸(∨⌿↑⊆⍨b)⍷⌽b←2⊥⍣¯1⊢⎕

Experimente online!

⎕ solicitação de entrada

⊢ rendimento que (separa ¯1de ⎕)

2⊥⍣¯1 converter para base-2, usando quantas posições forem necessárias

b← armazenar como b(para b inary)

⌽ marcha ré

(… ) Marque as posições iniciais do seguinte:

 ⊆⍨b partição automática b(ou seja, as 1 faixas de b)

 ↑ mix (faça a lista de listas em matriz, preenchendo com zeros)

 ∨⌿ redução OR vertical (produz a maior sequência)

⍸ índices de posições iniciais

⌽ marcha ré

⊃ escolha o primeiro (produz zero se não houver nenhum disponível)

MATL , 15 bytes

`tt2/kZ&t]xBnq&

Experimente online!

Usa a metade e a idéia AND. A ksó é necessário para torná-lo terminar de1 - por algum motivo, 1 e 0,5 devolve 1, fazendo com que num ciclo infinito.

(solução alternativa: BtnwY'tYswb*&X>)-convertendo para codificação binária e de duração)

Planilhas Google, 94 bytes

=Len(Dec2Bin(A1))-Find(MAX(Split(Dec2Bin(A1),0)),Dec2Bin(A1))-Len(MAX(Split(Dec2Bin(A1),0)))+1

Não, não é muito bonito. Seria muito bom poder armazenar Dec2Bin(A1)como uma variável para referência.

Ponto principal: como o Excel, a Dec2Binfunção tem um valor máximo de entrada de 511. Qualquer coisa maior que isso retorna um erro, como mostrado abaixo.

R, 117 bytes

z=rev(Reduce(function(x,y)ifelse(y==1,x+y,y),strtoi(intToBits(scan())),,,T));ifelse(!sum(z),0,33-which.max(z)-max(z))

Excel VBA, ₅₄ 44 bytes

-10 Bytes graças a @EngineerToast

Função de janela imediata VBE anônima que leva a entrada do intervalo [A1]e sai para a janela imediata VBE

?Instr(1,StrReverse([Dec2Bin(A1)]),1)+[A1>0]

APL (Dyalog Classic) , 24 21 bytes

63|-⊃⍒+/×\↑,⍨\⎕⊤⍨64⍴2

Experimente online!

Pitão , 17 bytes

Esta é uma função recursiva. O link inclui ypara chamar a função na entrada fornecida.

L|&K.&b/b2yKsl|b1

Verifique todos os casos de teste.

Pitão , 20 bytes

-lK.B|Q1+xKJeScK\0lJ

Verifique todos os casos de teste.

R, 66 bytes

function(i){a=rle(intToBits(i));max(0,a[[1]][which(a[[2]]==1)])}

Explicação:

function(i){
  a = rle(                  # Run-length encode
    intToBits(i)            # The bits in i
  );                        # And assign it to a.
  max(0,                    # Return the maximum of zero and
      a[[1]][               # The lengths of a,
        which(a[[2]]==1)    # But only those where the repeated bit is 1
        ])
}

Python 2 , 41 bytes

f=lambda n:n/2and(n&n/2<1)+f(n&n/2or n/2)

Experimente online!

Baseado nesta solução pelo Sr. Xcoder .

Javascript, 54 caracteres

f=i=>i.toString(2).split(0).sort().reverse()[0].length

• i.toString(2) obtém a sequência binária do número inteiro.
• O .split(0)obtém cada parte sequencial em um elemento da matriz.
• .sort().reverse() nos dá o maior valor como primeiro.
• O [0].lengthnos dá a duração desse primeiro valor.

Perl 5, 45 + 1 (-p)

(sprintf"%b",$_)=~/(1+)(?!.*1\1)/;$_=length$'

Se você escrever isso na linha de comando da maioria dos shells, talvez seja necessário digitar isso como:

perl -pE'(sprintf"%b",$_)=~/(1+)(?!.*1\1)/;$_=length$'"'"

A dança das aspas no final é apenas para obter perl see a ', que de outra forma seria consumido pela casca.

Retina , 52 43 bytes

Converta em binário e substitua pelo comprimento da sequência maior de unidades.

.*
$*
+`(1+)\1
$+0
01
1

$'¶
O`
A-3`
^1+

.

Experimente online - todos os casos de teste

Economizou 9 bytes graças a Martin.