Introducción

Este desafío requiere que establezca los ceros finales de una representación binaria entera 010101…, esto se explica mejor con un ejemplo:

Dado el entero 400, el primer paso es convertirlo a binario:

110010000

Como podemos ver, el quinto bit es el bit menos significativo 1, por lo que a partir de ahí reemplazamos los ceros inferiores por 0101:

110010101

Finalmente convertimos eso a decimal: 405

Desafío

Dado un retorno / salida entero positivo, el valor resultante correspondiente del proceso definido anteriormente.

Reglas

Esta secuencia solo se define para enteros con al menos un 1bit, por lo que la entrada siempre será ≥ 1
En su lugar, puede tomar la entrada como una cadena, lista de dígitos (decimal)
No tiene que manejar entradas inválidas

Casos de prueba

Aquí hay más casos de prueba con los pasos intermedios (no es necesario imprimirlos / devolverlos):

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

code-golf sequence binary bitwise ბიმო
fuente

¿Podemos suponer un número entero de 32 bits?

Arnauld

@Arnauld: ¡Claro!

ბიმო

99

Alguna idea de golf: si nes la potencia máxima de 2 que divide la entrada, entonces la respuesta es simplemente(input) + ceil((2^n - 2)/3)

JungHwan Min

12

Python 3 , 20 bytes

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

Pruébalo en línea!

Explicación

Toma 192como ejemplo. Su forma binaria es 11000000, y necesitamos convertirla a 11010101.

Notamos que necesitamos agregar 10101al número. Esta es una serie geométrica ( 4^0 + 4^1 + 4^2), que tiene una forma cerrada como (4^3-1)/(4-1). Esto es lo mismo que 4^3//3donde //denota división entera.

Si lo fuera 101010, entonces todavía sería una serie geométrica ( 2×4^0 + 2×4^1 + 2×4^2), que es 2×4^3//3por las razones anteriores.

De todos modos, 4^3y 2×4^3sería el bit menos significativo, que obtenemos por n&-n:

Notamos que el complemento de nes 00111111. Si agregamos uno, se convierte 01000000, y solo se superpone con n=11000000el dígito menos significativo. Tenga en cuenta que "complementar y agregar uno" es solo una negación.

Monja permeable
fuente

66

@ Mr.Xcoder buen espíritu deportivo

Leaky Nun

1

Posiblemente lambda n:(n&-n)//3+nfunciona también? Pasa todos los casos de prueba de muestra , pero según mi intuición no debería ser válido, ¿verdad?

Sr. Xcoder

@ Mr.Xcoder es realmente válido.

Leaky Nun

1

¿Por qué no usar Python 2 para guardar un byte? TIO

FlipTack

44

@FlipTack Odio Python 2

Leaky Nun

8

Jalea , 5 bytes

&N:3+

Pruébalo en línea!

Esta vez, un enfoque de puerto de Leaky Nun (al menos lo ayudé a jugar golf un poco: P)

Jalea , 7 bytes

^N+4:6ạ

Pruébalo en línea!

Utiliza el fantástico enfoque de JungHwan Min , con la ayuda indirecta de Martin Ender .

Sr. Xcoder
fuente

Dennis publicó, luego eliminó, una solución muy similar de 5 bytes justo después de que hiciste esa edición. Algo así como &N:3|. Felicidades; venciste a Dennis en gelatina! (Pero no del todo fuera de juego.)

wizzwizz4

@ wizzwizz4 Realmente no hice mucho, aparte de sugerir un pequeño golf al enfoque de Leaky y luego portarlo. Pero eh :-)

Sr. Xcoder

Esta es la primera respuesta Jelly solo ASCII que he visto.

MD XF

6

Wolfram Language (Mathematica) , 36 28 26 24 bytes

^{-8 bytes gracias a @MartinEnder y -2 bytes gracias a @ Mr.Xcoder}

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

Pruébalo en línea!

Solo necesitamos encontrar el número de ceros finales en la entrada, y encontrar el número alternando 0s y 1s con una longitud menor que eso, y agregarlo a la entrada.

Entonces, 400 -> 11001000 -> 110010000 + 0000 -> 110010101 + 101 -> 405

La fórmula explícita para nésimo número con alterna 1s y 0s se dio en A000975 en OEIS. Podemos usar el nnúmero th ya que no hay dos números diferentes que puedan tener la misma longitud en binario y tengan dígitos alternos.

JungHwan Min
fuente

1

2^#~IntegerExponent~2es(BitXor[#,#-1]+1)/2

Martin Ender

@MartinEnder wow! Y luego puedo combinar las fracciones para reducir más bytes

JungHwan Min

1

24 bytes . Puedes usar #+⌊(#~BitAnd~-#)/3⌋&en su lugar.

Sr. Xcoder

@ Mr.Xcoder editado :)

JungHwan Min

5

J , ₁₉ 18 bytes

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

Pruébalo en línea!

Explicacion rapida

Esta es una respuesta antigua, pero es muy similar en naturaleza a la actual, solo cuenta los ceros finales de manera diferente. Vea los comentarios para un enlace que explica cómo 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

Otras respuestas:

Respuesta anterior (19 bytes).

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

Más largo de lo que debería ser porque \va de derecha a izquierda.

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

col
fuente

1

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

millas

@miles ¿te importaría explicar qué está pasando con la conversión de base allí? Supongo que tiene algo que ver con los ceros, pero no estoy seguro.

cole

#.~ cuenta el número de verdades finales , así que lo que necesitamos es #.~ -. #:contar el número de ceros finales

millas

@miles Ah! Eso es muy, muy inteligente.

cole

4

Julia 0.6 , 12 bytes

!n=n|n&-n÷3

Pruébalo en línea!

Dennis
fuente

Esto parece un método eficiente, ¿puede explicar la precedencia del operador? Por ejemplo, no puedo decir si se evalúa como ((!n=(n|n))&-n)/3, o !n=(((n|n)&(-n))/3), etc.

MD XF

En Julia, los operadores bit a bit tienen las mismas precedencia que sus contrapartes aritméticas, por lo que |es como +y &es como *. Por lo tanto, n|n&-n÷3se analiza como n | ((n&-n) ÷3).

Dennis

3

JavaScript (ES6), 40 39 bytes

Toma la entrada como un entero de 32 bits.

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

Casos de prueba

Mostrar fragmento de código

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

Expandir fragmento

Arnauld
fuente

2

05AB1E , 13 8 5 bytes

Ahorré 5 bytes gracias a la fórmula ordenada del Sr. Xcoder y JungHwan Min. Ahorré
otros 3 gracias al Sr. Xcoder

(&3÷+

Pruébalo en línea!

Explicación

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

Emigna
fuente

1

Quizás valga la pena mencionar que portar la respuesta de Mathematica le da 8 bytes

Sr. Xcoder

@ Mr.Xcoder: Ooh, esa es una buena fórmula.

Emigna

1

¿Tiene 05ab1e bit a bit Y? Si es así, (<bitwise and here>3÷+debería funcionar para ~ 5 bytes.

Sr. Xcoder

2

R , 71 58 bytes

gracias a NofP por -6 bytes

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

Pruébalo en línea!

Asume que la entrada es un entero de 32 bits. R solo tiene enteros de 32 bits firmados (conversión a doublecuando un entero se desborda) de todos modos y no hay entradas de 64 bits o sin signo.

Giuseppe
fuente

Puede convertir el which.max(n):1-1a !cumsum(n)para obtener una solución de 65 bytes

NofP

@NofP gracias! Es una gran idea.

Giuseppe

2

brainfuck , 120 bytes

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

¡Pruébelo en línea!

Comienza con el valor en la celda actual y termina en la celda con el valor de salida. Obviamente, no funcionará en números superiores a 255, ya que ese es el límite de la celda para un ataque mental típico, pero funcionará si asume un tamaño de celda infinito.

Jo King
fuente

1

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}

Pruébalo en línea!

Ay. La conversión a / desde binario y el corte de matriz no son realmente los puntos fuertes de PowerShell.

Toma la entrada $ncomo un número. Inmediatamente converteso a la base binaria 2y lo almacenamos en $a. A continuación tenemos una construcción if / else. La cláusula if comprueba si a regex Matchcontra 1 o más 0s al final de la cadena ( '0+$') tiene indexuna ubicación mayor que 0(es decir, el inicio de la cadena binaria). Si es así, tenemos algo con lo que trabajar, elsesolo mostramos el número.

En el interior if, cortamos los xprimeros dígitos y concatenamos +los que tienen los dígitos restantes. Sin embargo, para los dígitos restantes, se bucle a través de ellos y seleccionar una 0o 1a emitir en su lugar, utilizando $i++%2para elegir. Esto nos da el 010101...patrón en lugar de 0s al final. Luego -joinvolvemos a formar una cadena y la $cvolvemos a convertir en una Int32base 2.

En cualquier situación, el número se deja en la tubería y la salida es implícita.

AdmBorkBork
fuente

1

APL + WIN, 43 bytes

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

Solicita entrada de pantalla

Graham
fuente

1

PowerShell , 41 36 bytes

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

Pruébalo en línea! o Verificar todos los casos de prueba

Port of Leaky Nun's Python answer .

Guardado 5 bytes gracias a Leaky Nun

AdmBorkBork
fuente

1

PHP , 47 bytes

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

Pruébalo en línea!

Realmente solo otro puerto de la solución de @Leaky Nun

NK1406
fuente

1

Perl 5 , 54 bytes

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

Pruébalo en línea!

Xcali
fuente

1

Python 3 , 56 bytes

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

Pruébalo en línea!

Todavía no estoy contento con esto, pero realmente no quería usar la fórmula ... -2 gracias a Rod . -1 gracias a Jonathan Frech .

Sr. Xcoder
fuente

eval(...)en lugar de int(...,2)podría guardar un byte.

Jonathan Frech

1

Rubí , 15 bytes

Otro puerto de aproximación de Leaky Nun.

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

Pruébalo en línea!

Tom Lazar
fuente

1

Óxido , 18 bytes

Un enfoque de puerto de Leaky Nun

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

Pruébalo en línea!

Noskcaj
fuente

1

AWK , 24 bytes

Un puerto de respuesta Mathmatica de JungHwan Min

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

Pruébalo en línea!

Noskcaj
fuente

1

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));

Expandir fragmento

l4m2
fuente

1

C, 56 bytes

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

Pruébalo en línea!

C (gcc), 50 bytes

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

Pruébalo en línea!

51 48 bytes usando la solución de Arnauld :

¡Gracias a @ l4m2 por guardar tres bytes!

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

Pruébalo en línea!

43 con gcc:

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

Pruébalo en línea!

Steadybox
fuente

0xAAAAAAAA=>-1u/3*2

l4m2

1

Pari / GP , 19 bytes

Un puerto del acercamiento de Nun Leaky.

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

Pruébalo en línea!

alephalpha
fuente

0

Jalea , 13 bytes

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

Pruébalo en línea!

Explicación

Tome 24 como entrada de ejemplo.

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

dylnan
fuente

Un poco de mancha alterna

Introducción

Desafío

Reglas

Casos de prueba

Respuestas:

Python 3 , 20 bytes

Explicación

Jalea , 5 bytes

Jalea , 7 bytes

Wolfram Language (Mathematica) , 36 28 26 24 bytes

J , ₁₉ 18 bytes

Explicacion rapida

Otras respuestas:

Julia 0.6 , 12 bytes

JavaScript (ES6), 40 39 bytes

Casos de prueba

05AB1E , 13 8 5 bytes

R , 71 58 bytes

brainfuck , 120 bytes

PowerShell , 168 bytes

APL + WIN, 43 bytes

PowerShell , 41 36 bytes

PHP , 47 bytes

Perl 5 , 54 bytes

Python 3 , 56 bytes

Rubí , 15 bytes

Óxido , 18 bytes

AWK , 24 bytes

JavaScript ES6, 13 bytes

C, 56 bytes

C (gcc), 50 bytes

Pari / GP , 19 bytes

Jalea , 13 bytes

Un poco de mancha alterna

Introducción

Desafío

Reglas

Casos de prueba

Respuestas:

Python 3 , 20 bytes

Explicación

Jalea , 5 bytes

Jalea , 7 bytes

Wolfram Language (Mathematica) , 36 28 26 24 bytes

J , 19 18 bytes

Explicacion rapida

Otras respuestas:

Julia 0.6 , 12 bytes

JavaScript (ES6), 40 39 bytes

Casos de prueba

05AB1E , 13 8 5 bytes

R , 71 58 bytes

brainfuck , 120 bytes

PowerShell , 168 bytes

APL + WIN, 43 bytes

PowerShell , 41 36 bytes

PHP , 47 bytes

Perl 5 , 54 bytes

Python 3 , 56 bytes

Rubí , 15 bytes

Óxido , 18 bytes

AWK , 24 bytes

JavaScript ES6, 13 bytes

C, 56 bytes

C (gcc), 50 bytes

Pari / GP , 19 bytes

Jalea , 13 bytes

J , ₁₉ 18 bytes