Introdução

Esse desafio exige que você defina os zeros à direita de uma representação binária de números inteiros 010101…, isso é melhor explicado com um exemplo:

Dado o número inteiro 400, o primeiro passo é convertê-lo em binário:

110010000

Como podemos ver, o quinto bit é o menos significativo 1; portanto, a partir daí, substituímos os zeros inferiores por 0101:

110010101

Finalmente, convertemos isso de volta para decimal: 405

Desafio

Dado um retorno / saída inteiro positivo, o valor resultante correspondente do processo acima definido.

Regras

• Essa sequência é definida apenas para números inteiros com pelo menos um 1bit, portanto a entrada sempre será ≥ 1
• Você pode usar a entrada como uma sequência de caracteres, lista de dígitos (decimal)
• Você não precisa lidar com entradas inválidas

Casos de teste

Aqui estão mais alguns casos de teste com as etapas intermediárias (você não precisa imprimi-las / devolvê-las):

In -> … -> … -> Out
1 -> 1 -> 1 -> 1
2 -> 10 -> 10 -> 2
3 -> 11 -> 11 -> 3
4 -> 100 -> 101 -> 5
24 -> 11000 -> 11010 -> 26
29 -> 11101 -> 11101 -> 29
32 -> 100000 -> 101010 -> 42
192 -> 11000000 -> 11010101 -> 213
400 -> 110010000 -> 110010101 -> 405
298 -> 100101010 -> 100101010 -> 298

Python 3 , 20 bytes

lambda n:(n&-n)//3+n

Experimente online!

Explicação

Tome 192como exemplo. Sua forma binária é 11000000e precisamos convertê-la para 11010101.

Observamos que precisamos adicionar 10101ao número. Esta é uma série geométrica ( 4^0 + 4^1 + 4^2), que tem uma forma fechada como (4^3-1)/(4-1). É o mesmo que 4^3//3onde //denota divisão inteira.

Se fosse 101010, ainda seria uma série geométrica ( 2×4^0 + 2×4^1 + 2×4^2), 2×4^3//3pelas razões acima.

Enfim, 4^3e 2×4^3seria apenas o bit menos significativo que obtemos por n&-n:

Percebemos que o complemento de né 00111111. Se adicionarmos um, ele se tornará 01000000e só se sobrepõe n=11000000ao dígito menos significativo. Observe que "complementar e adicionar um" é apenas negação.

Gelatina , 5 bytes

&N:3+

Experimente online!

Desta vez, um porto da abordagem de Leaky Nun (pelo menos eu o ajudei a jogar um pouco: P)

Geléia , 7 bytes

^N+4:6ạ

Experimente online!

Utiliza a abordagem fantástica de JungHwan Min , com a ajuda indireta de Martin Ender .

Wolfram Language (Mathematica) , 36 28 26 24 bytes

^{-8 bytes graças a @MartinEnder e -2 bytes graças a @ Mr.Xcoder}

#+⌊(#~BitAnd~-#)/3⌋&

Experimente online!

Precisamos apenas encontrar o número de zeros à direita na entrada e encontrar o número com 0s e s alternados 1com comprimento um menor que isso e adicioná-lo à entrada.

Então, 400 -> 11001000 -> 110010000 + 0000 -> 110010101 + 101 -> 405

A fórmula explícita para o nnúmero com 1s e s alternados 0foi dada em A000975 no OEIS. Podemos usar o nnúmero th, já que dois números diferentes não podem ter o mesmo comprimento em binário e ter dígitos alternados.

J , ₁₉ 18 bytes

+(2|-.i.@#.-.)&.#:

Experimente online!

Explicação Rápida

Esta é uma resposta antiga, mas é muito semelhante à atual, mas conta os zeros à direita de maneira diferente. Veja os comentários para um link explicando como funciona.

+(2|i.@i.&1@|.)&.#:
                 #:  Convert to binary list
       i.&1@|.       Index of last 1 from right
            |.         Reverse
       i.&1            Index of first 1
    i.               Range [0, index of last 1 from right)
  2|                 That range mod 2
               &.    Convert back to decimal number
+                    Add to the input

Outras respostas:

Resposta anterior (19 bytes).

+(2|i.@i.&1@|.)&.#:

Mais do que deveria, porque \vai da direita para a esquerda.

+(2|#*-.#.-.)\&.(|.@#:)

Julia 0,6 , 12 bytes

!n=n|n&-n÷3

Experimente online!

JavaScript (ES6), 40 39 bytes

Recebe a entrada como um número inteiro de 32 bits.

n=>n|((n&=-n)&(m=0xAAAAAAAA)?m:m/2)&--n

Casos de teste

let f =

n=>n|((n&=-n)&(m=0xAAAAAAAA)?m:m/2)&--n

console.log(f(1))   // 1 -> 1 -> 1
console.log(f(2))   // 10 -> 10 -> 2
console.log(f(3))   // 11 -> 11 -> 3
console.log(f(4))   // 100 -> 101 -> 5
console.log(f(24))  // 11000 -> 11010 -> 26
console.log(f(29))  // 11101 -> 11101 -> 29
console.log(f(32))  // 100000 -> 101010 -> 42
console.log(f(192)) // 11000000 -> 11010101 -> 213
console.log(f(400)) // 110010000 -> 110010101 -> 405
console.log(f(298)) // 100101010 -> 100101010 -> 298

05AB1E , 13 8 5 bytes

Economizou 5 bytes graças à fórmula pura do Sr. Xcoder e JungHwan Min
Economizou outros 3 graças ao Sr. Xcoder

(&3÷+

Experimente online!

Explicação

(      # negate input
 &     # AND with input
  3÷   # integer divide by 3
    +  # add to input

R , 71 58 bytes

graças ao NofP por -6 bytes

function(n){n=n%/%(x=2^(0:31))%%2
n[!cumsum(n)]=1:0
n%*%x}

Experimente online!

Assume que a entrada é um número inteiro de 32 bits. R só assinou números inteiros de 32 bits (convertidos para doublequando um número inteiro excede) de qualquer maneira e nenhuma entrada de 64 bits ou não assinada.

brainfuck , 120 bytes

>+<[[>-]++>[[>]>]<[>+>]<[<]>-]>[-<+>[-<[<]<]>]>[>]<[>+<[->+<]<[->+<]<]>>[<]+>[-[-<[->+<<+>]>[-<+>]]<[->++<]<[->+<]>>>]<<

Experimente Online!

Inicia com o valor na célula atual e termina na célula com o valor de saída. Obviamente, não funcionará em números acima de 255, já que esse é o limite de células para um típico ataque cerebral, mas funcionará se você assumir um tamanho infinito de células.

PowerShell , 168 bytes

param($n)$a=($c=[convert])::ToString($n,2);if(($x=[regex]::Match($a,'0+$').index)-gt0){$c::ToInt32(-join($a[0..($x-1)]+($a[$x..$a.length]|%{(0,1)[$i++%2]})),2)}else{$n}

Experimente online!

Ai. A conversão de / para fatias binárias e de array não é realmente o ponto forte do PowerShell.

Recebe a entrada $ncomo um número. Nós imediatamente convertque a base binária 2e armazenar isso em $a. Em seguida, temos uma construção if / else. A cláusula if testa se um regex Matchcontra 1 ou mais 0s no final da string ( '0+$') tem indexum local maior que 0(isto é, o início da string binária). Se isso acontecer, temos algo para trabalhar, elseapenas fornecemos o número.

Dentro do if, dividimos os xprimeiros dígitos e os concatenamos +com os dígitos restantes. No entanto, para os dígitos restantes, passamos por eles e selecionamos um 0ou 1a ser produzido, usando $i++%2para escolher. Isso nos dá o 010101...padrão em vez de 0s no final. Nós, então -join, $cvoltamos a formar uma string e a revertemos para uma Int32base 2.

Em qualquer das situações, o número é deixado no pipeline e a saída é implícita.

APL + WIN, 43 bytes

p←+/^\⌽~n←((⌊1+2⍟n)⍴2)⊤n←⎕⋄2⊥((-p)↓n),p⍴0 1

Solicita entrada de tela

PowerShell , 41 36 bytes

param($n)$n+(($x=$n-band-$n)-$x%3)/3

Experimente online! ou Verifique todos os casos de teste

Resposta Python do Porto da Freira Furada .

Economizou 5 bytes graças a Leaky Nun

PHP , 47 bytes

<?php function b($a){echo(int)(($a&-$a)/3)+$a;}

Experimente online!

Realmente apenas mais uma porta da solução da @Leaky Nun

Perl 5 , 54 bytes

$_=sprintf'%b',<>;1while s/00(0*)$/01$1/;say oct"0b$_"

Experimente online!

Python 3 , 56 bytes

lambda n:eval((bin(n).rstrip("0")+"01"*n)[:len(bin(n))])

Experimente online!

Ainda não estou feliz com isso, mas não queria usar a fórmula ... -2 graças a Rod . -1 graças a Jonathan Frech .

Ruby , 15 bytes

Outro porto da abordagem de Leaky Nun.

->k{(k&-k)/3+k}

Experimente online!

Ferrugem , 18 bytes

Um porto da abordagem de Leaky Nun

|n:i32|(n&-n)/3+n;

Experimente online!

AWK , 24 bytes

Um porto da resposta Mathmatica de JungHwan Min

$0=int(and($0,-$0)/3+$0)

Experimente online!

JavaScript ES6, 13 bytes

n=>(n&-n)/3|n

f = 
n=>(n&-n)/3|n
;
console.log (f(8));
console.log (f(243));
console.log (f(1048576));
console.log (f(33554432));

C, 56 bytes

i,k;f(n){for(k=i=1;n>>i<<i==n;k+=++i&1)k*=2;return n|k;}

Experimente online!

C (gcc), 50 bytes

i,k;f(n){for(k=i=1;n>>i<<i==n;k+=++i&1)k*=2;k|=n;}

Experimente online!

 51  48 bytes usando a solução de Arnauld :

Obrigado a @ l4m2 por salvar três bytes!

m;f(n){return n|((n&-n)&(m=-1u/3*2)?m:m/2)&n-1;}

Experimente online!

43 com o gcc:

m;f(n){m=n|((n&-n)&(m=-1u/3*2)?m:m/2)&n-1;}

Experimente online!

Pari / GP , 19 bytes

Um porto da abordagem de Leaky Nun.

n->n+bitand(n,-n)\3

Experimente online!

Gelatina , 13 bytes

BŒgṪµ2Ḷṁ×CḄ+³

Experimente online!

Explicação

Tome 24 como exemplo de entrada.

BŒgṪµ2Ḷṁ×CḄ+³
B                Binary representation of the input → 11000
 Œg              Group runs of equal length → [[1,1],[0,0,0]]
   Ṫ             Tail → [0,0,0]
    µ            New monadic link
     2Ḷ          [0,1] constant
       ṁ         Mold [0,1] to the shape of [0,0,0] → [0,1,0]
        ×        Multiply [0,1,0] by...
         C       1-[0,0,0]. If last bit(s) of the original input are 1 this will add nothing to the original input
          Ḅ      Convert to decimal from binary → 2
           +³    Add this with the original input → 26