Borrar el bit más significativo de un entero

29

Entrada

La entrada es un solo entero positivo n

Salida

La salida está ncon su bit más significativo establecido en 0.

Casos de prueba

1 -> 0
2 -> 0
10 -> 2
16 -> 0
100 -> 36
267 -> 11
350 -> 94
500 -> 244

Por ejemplo: 350en binario es 101011110. Establecer su bit más significativo (es decir, el 1bit más a la izquierda ) para 0convertirlo en un 001011110equivalente al entero decimal 94, la salida. Este es OEIS A053645 .

code-golf sequence binary Marcus Andrews
fuente

19

Borrar el bit más significativo de 10obviamente da 0: D

clabacchio

@clabacchio Yo ... eso ... er ... ¿qué? (agradable)

Baldrickk

12

Me parece que los ceros son tan significativos como los unos. Cuando dices "el bit más significativo" te refieres a "el bit más significativo que se establece en uno".

Michael Kay

Respuestas:

12

C (gcc) , 49 44 40 39 bytes

i;f(n){for(i=1;n/i;i*=2);return n^i/2;}

Pruébalo en línea!

cleblanc
fuente

1

Se puede reemplazar i<=ncon el n/ide -1 bytes. Este no es mi golf, alguien más trató de editarlo en su publicación, pero lo revertí porque las ediciones para publicaciones de golf no se aceptan de acuerdo con las reglas de nuestra comunidad.

HyperNeutrino

1

@HyperNeutrino Vi y aprobé la edición justo ahora. ¡No estaba al tanto de esa regla, pero es un buen consejo de golf!

cleblanc

Ah bien. Sí, por lo general, se supone que las personas deben publicar comentarios para consejos de golf y OP debería hacer las modificaciones, pero si lo acepta, no es realmente un problema. :)

HyperNeutrino

10

Python 2 , 27 bytes

lambda n:n^2**len(bin(n))/8

Pruébalo en línea!

26 bytes

Desafortunadamente, esto no funciona para 1:

lambda n:int(bin(n)[3:],2)

Pruébalo en línea!

FlipTack
fuente

9

05AB1E , 5 bytes

.²óo-

Pruébalo en línea!

Extracción del bit más significativo de un número entero N es equivalente a encontrar la distancia desde N a la potencia entera más alta de 2 menor que N .

Por lo tanto, utilicé la fórmula N - 2 ^{piso (log ₂ N)} :

.²- Logaritmo con base 2 .
ó - Piso a un entero.
o- 2 elevado a la potencia del resultado anterior.
- - Diferencia

Sr. Xcoder
fuente

1

b¦Ctambién funciona ... ¿no? Convertir a binario, MSB siempre está en el índice 1, eliminar MSB, volver a convertir.

Urna mágica de pulpo

2

@MagicOctopusUrn ¡No, eso está mal, falla 1!

Sr. Xcoder

8

Jalea , 3 bytes

BḊḄ

Pruébalo en línea!

Explicación

BḊḄ  Main Link
B    Convert to binary
 Ḋ   Dequeue; remove the first element
  Ḅ  Convert from binary

Hiperneutrino
fuente

2

¿No son Ḅy Ḋpuntos de código de dos bytes? Esto cambiaría el tamaño total a 5 bytes.

Bartek Banachewicz

3

@BartekBanachewicz Jelly usa su propia página de códigos , donde esos caracteres son de solo 1 byte.

steenbergh

1

Gracias por preguntar y responder esto, ¡eso me ha molestado por mucho tiempo!

Ukko

8

C (gcc) - 59 bytes

main(i){scanf("%d",&i);return i&~(1<<31-__builtin_clz(i));}

Esta respuesta de gcc usa solo operaciones enteras de bit a bit y aritméticas. No hay logaritmos aquí! Puede tener problemas con una entrada de 0 y es totalmente no portátil.

Es mi primera respuesta en este sitio, por lo que me encantaría recibir comentarios y mejoras. Me divertí mucho aprendiendo expresiones bit a bit.

Diploma Charles
fuente

1

¡Bienvenido a PPCG, y una excelente primera respuesta! Esperamos que disfrute participando en muchos más desafíos :-)

ETHproductions

No necesita un programa completo main, una función es una presentación válida . Cambiar esto en una función y tomar la entrada como argumento para dicha función ahorra 18 bytes .

Steadybox

1

Incluso podría escribirlo como una macro para guardar dos bytes más .

Steadybox

7

MATL , 8 6 bytes

B0T(XB

Pruébalo en línea!

Guardado dos bytes gracias a Cinaski. Cambiar a la indexación de asignación en lugar de la indexación de referencia fue 2 bytes más corto :)

Explicación:

          % Grab input implicitly: 267
B         % Convert to binary: [1 0 0 0 0 1 0 1 1]
 0T(      % Set the first value to 0: [0 0 0 0 0 1 0 1 1]
    XB    % Convert to decimal: 11

Stewie Griffin
fuente

1

Podría haber utilizado la indexación de referencia (también para 6 bytes), si lo utilizó en 4Llugar de hacerlo [2J]. Otra diversión de 6 bytes: tZlcW-(solo funciona en MATLAB, no en TIO / Octave)

Sanchises

6

Java (OpenJDK 8) , 23 bytes

n->n^n.highestOneBit(n)

Pruébalo en línea!

Lo sentimos, incorporado: - /

Olivier Grégoire
fuente

¿Java con una función incorporada que otros lenguajes populares como .NET y Python no tienen? o.Ô +1 a eso. Estaba a punto de publicar algo más largo sin complementos. El tuyo es 15 bytes más corto. XD

Kevin Cruijssen

@KevinCruijssen Algo así n->n^1<<(int)Math.log2(n)funcionará y es probable que sea más corto que 38 bytes. Era mi segunda idea (aún no probada), si la highestOneBitque no funcionaba correctamente. Por curiosidad, ¿cuál fue su solución?

Olivier Grégoire

La mía fue n->n^1<<(int)(Math.log(n)/Math.log(2))porque Math.log2no existe en Java. ; P Only Math.log, Math.log10y Math.loglpestán disponibles.

Kevin Cruijssen

2

Iba a publicar lo mismo, solo menos en lugar de xor.

Recordaba

1

@KevinCruijssen Vaya, de Math.log2hecho no existe ... Lo malo. ¿Ver? highestOneBitExiste un buen método ( ) pero no otro ( Math.log2). Java es raro ;-)

Olivier Grégoire

6

Casco , 3 bytes

ḋtḋ

Pruébalo en línea!

Explicación:

    -- implicit input, e.g. 350
  ḋ -- convert number to list of binary digits (TNum -> [TNum]): [1,0,1,0,1,1,1,1,0]
 t  -- remove first element: [0,1,0,1,1,1,1,0]
ḋ   -- convert list of binary digits to number ([TNum] -> TNum): 94

Laikoni
fuente

De manera similar a la solución Jelly, parece que en realidad son 5 bytes, no 3.

Bartek Banachewicz

1

@BartekBanachewicz De manera similar a Jelly, Husk usa su propia página de códigos, por lo que en realidad son 3 bytes: P

HyperNeutrino

@BartekBanachewicz Vea aquí la página de códigos: github.com/barbuz/Husk/wiki/Codepage

Laikoni

5

Ohm v2 , 3 bytes

b(ó

Pruébalo en línea!

Cinaski
fuente

5

Python 2 , 27 bytes

lambda n:n-2**len(bin(n))/8

Pruébalo en línea!

Explicación

lambda n:n-2**len(bin(n))/8  # Lambda Function: takes `n` as an argument
lambda n:                    # Declaration of Lambda Function
              len(bin(n))    # Number of bits + 2
           2**               # 2 ** this ^
                         /8  # Divide by 8 because of the extra characters in the binary representation
         n-                  # Subtract this from the original

Hiperneutrino
fuente

... Justo cuando estaba trabajando en las matemáticas bit a bit. : P

totalmente humano

@totallyhuman heh lo siento pero te

gané

2**len(bin(n))/8también se puede deletrear 1<<len(bin(n))-3, y luego funcionará en 2 y 3 (sin bytes guardados / agregados).

Mego

@Mego Cool, ¡gracias por la adición!

HyperNeutrino

5

Python 3 , 30 bytes

-8 bytes gracias a caird coinheringaahing. ^{Escribí eso de memoria. : o}

lambda n:int('0'+bin(n)[3:],2)

Pruébalo en línea!

totalmente humano
fuente

¿Por qué no lambda n:int(bin(n)[3:],2)?

caird coinheringaahing

Bueno, a) eso sería un error en 1 , b) Soy lo suficientemente tonto como para no pensar en eso. Pero lo arreglé con un cambio menor. ¡Gracias!

totalmente humano

He editado el código para que funcione (y ahorre 4 bytes)

caird coinheringaahing

Eso todavía errores en 1 .

totalmente humano

@cairdcoinheringaahing Esa fue mi respuesta original , pero luego me di cuenta de que había un error en 1. La solución termina más tiempo que un simple método XOR

FlipTack

4

Mathematica, 37 bytes

Rest[#~IntegerDigits~2]~FromDigits~2&

Pruébalo en línea!

J42161217
fuente

4

JavaScript, 22 20 bytes

Guardado 2 bytes gracias a ovs

a=>a^1<<Math.log2(a)

Pruébalo en línea!

Otro enfoque, 32 bytes

a=>'0b'+a.toString`2`.slice`1`^0

Pruébalo en línea!

fuente

por qué harías .slice`1`^0cuándo .slice(1)^0funcionaría igual de bien, jaja

ETHproductions

@ETHproductions. Este se ve mejor :)

4

J, 6 bytes

}.&.#:

Bastante simple.

Explicación

}.&.#:
    #:  convert to list of binary digits
  &.    apply right function, then left, then the inverse of right
}.      behead

col
fuente

Iba a publicar esto :(

Cyoce

@Cyoce Yo también ...

Adám

4

APL (Dyalog) , 10 bytes

Función de prefijo tácito.

2⊥1↓2∘⊥⍣¯1

Pruébalo en línea!

2∘⊥... decodificar desde base-2 ...
... ⍣¯1 negativo una vez (es decir, codificar en base-2)

1↓ suelta el primer bit

2⊥ decodificar desde la base-2

Adán
fuente

4

Rubí, 26 bytes

-7 Bytes gracias a Ventero. -2 Bytes gracias a historicrat.

->n{/./=~'%b'%n;$'.to_i 2}

nombre para mostrar
fuente

Puede guardar algunos bytes simplemente omitiendo el primer carácter y soltando paréntesis redundantes:->n{n.to_s(2)[1..-1].to_i 2}

Ventero

->n{/./=~'%b'%n;$'.to_i 2}

histocrat

4

C (gcc), 38 bytes

Incorporado en gcc utilizado.

f(c){return c^1<<31-__builtin_clz(c);}

Colera Su
fuente

Reemplazar 31-con ~debería guardar dos bytes.

@ThePirateBay depende del hardware si el cambio está enmascarado. En mi computadora, saldrá 0.

Colera Su

4

Ensamblaje ARM, 46 43 bytes

(Puede omitir el registro de destino en agregar cuando sea igual que la fuente)

clz x1,x0
add x1,1
lsl x0,x1
lsr x0,x1
ret

Michael Dorgan
fuente

¿Qué sabor tiene la sintaxis de ensamblaje ARM? Mi ensamblador GNU no entiende shr/ shl/ rety quiere algo como lsr/ lsl/ bx lr.

Ruslan

Probablemente mezcle la sintaxis en varias versiones (ret es de aarch64), aunque pensé que el ensamblador podría realizar estas operaciones por usted. Sin embargo, para los propósitos de aquí, el uso de lsl / lsr anterior y directo probablemente sea correcto.

Michael Dorgan

Lo curioso es que puedo hacerlo en 1 operación menos, pero el tamaño del byte aumenta en 2. Ah código golf.

Michael Dorgan

3

Pyth, 5 bytes

a^2sl

Banco de pruebas.

Explicación:

    l   Log base 2 of input.
   s    Cast ^ to integer (this is the position of the most significant bit.)
 ^2     Raise 2 to ^ (get the value of said bit)
a       Subtract ^ from input

Steven H.
fuente

3

Alice , 8 bytes

./-l
o@i

Pruébalo en línea!

Explicación

.   Duplicate an implicit zero at the bottom of the stack. Does nothing.
/   Switch to Ordinal mode, move SE.
i   Read all input as a string.
l   Convert to lower case (does nothing, because the input doesn't contain letters).
i   Try reading all input again, pushes an empty string.
/   Switch to Cardinal mode, move W.
.   Duplicate. Since we're in Cardinal mode, this tries to duplicate an integer.
    To get an integer, the empty string is discarded implicitly and the input is 
    converted to the integer value it represents. Therefore, at the end of this,
    we get two copies of the integer value that was input.
l   Clear lower bits. This sets all bits except the MSB to zero.
-   Subtract. By subtracting the MSB from the input, we set it to zero. We could
    also use XOR here.
/   Switch to Ordinal, move NW (and immediately reflect to SW).
o   Implicitly convert the result to a string and print it.
/   Switch to Ordinal, move S.
@   Terminate the program.

Martin Ender
fuente

3

Japt , 6 bytes

^2p¢ÊÉ

Pruébalo en línea!

Explicación

^2p¢ÊÉ
   ¢     Get binary form of input
    Ê    Get length of that
     É   Subtract 1
 2p      Raise 2 to the power of that
^        XOR with the input

Si la entrada `1`puede fallar: 4 bytes

¢Ån2

Pruébalo en línea!

Explicación : obtenga la entrada binary ( ¢), corte el primer char ( Å), analice como binary nuevamente en un número ( n2).

Justin Mariner
fuente

3

Octava , 20 bytes

@(x)x-2^fix(log2(x))

Pruébalo en línea!

Luis Mendo
fuente

3

APL (Dyalog Unicode) , 9 bytes

⊢-2*∘⌊2⍟⊢

Pruébalo en línea!

-1 byte gracias a Adam

Hiperneutrino
fuente

Completamente correcto, aunque hubiera usado TIO para generar una plantilla para mí. De todos modos, ⊢-2*∘⌊2⍟⊢guarda un byte.

Adám

Me entristeció que APL no estuviera representada, y la hubo, ¡casi perdida en el pergamino! Extraño APL.

cmm

@cmm APL está vivo y bien. No dude en pasar el rato en la sala de chat APL de Stack Exchange .

Adám

3

CJam , 7 bytes

{2b()b}

Pruébalo en línea!

Explicación:

{     }  Block:         267
 2b      Binary:        [1 0 0 0 0 1 0 1 1]
   (     Pop:           [0 0 0 0 1 0 1 1] 1
    )    Increment:     [0 0 0 0 1 0 1 1] 2
     b   Base convert:  11

Reutilice el MSB (que siempre es 1) para evitar tener que eliminarlo; el equivalente sin ese truco sería {2b1>2b}o {2b(;2b}.

Fruta Esolanging
fuente

3

Retina , 15 13 bytes

^(^1|\1\1)*1

Pruébalo en línea!

Entrada y salida en unario (el conjunto de pruebas incluye conversión de y a decimal por conveniencia).

Explicación

Esto es bastante fácil de hacer en unario. Todo lo que queremos hacer es eliminar la mayor potencia de 2 de la entrada. Podemos igualar una potencia de 2 con algunas referencias hacia adelante. En realidad, es más fácil hacer coincidir los valores de la forma 2 ⁿ -1 , así que haremos eso y combinaremos uno 1 por separado:

^(^1|\1\1)*1

El grupo 1coincide con un sencillo 1al principio para comenzar, o coincide con el doble de lo que hizo en la última iteración. Entonces coincide 1, entonces 2, 4y así sucesivamente. Dado que estos se suman, siempre tenemos una potencia de 2, que solucionamos con 1el final.

Debido al avance de línea final, la coincidencia simplemente se elimina de la entrada.

Martin Ender
fuente

3

R , 28 bytes

function(x)x-2^(log2(x)%/%1)

Pruébalo en línea!

Es más fácil calcular el bit más significativo a través 2 ^ floor(log2(x))de conversiones de base en lugar de realizarlas, que son bastante detalladas en R

usuario2390246
fuente

3

PARI / GP, 18 bytes

n->n-2^logint(n,2)

Solución alternativa:

n->n-2^exponent(n)

Charles
fuente

El primero parece dar respuestas incorrectas. Debe ser n->n-2^logint(n,2)? El segundo no es compatible con mi versión de PARI / GP, ni en la versión utilizada por tio.run . ¿Es esa una nueva función?

Jeppe Stig Nielsen

@JeppeStigNielsen Vaya, solucionado, eso es lo que obtengo por enviar desde mi teléfono. Sí, la segunda es una nueva función.

Charles

@JeppeStigNielsen que acabo de comprobar, exponentse agregó hace 5 días, en comparación con este desafío que se agregó ayer. :)

Charles

3

Haskell , 32 29 bytes

(!1)
x!y|2*y>x=x-y|z<-2*y=x!z

Pruébalo en línea!

-3 bytes gracias a @Laikoni

Solución anterior, 32 bytes

f x=last[x-2^i|i<-[0..x],2^i<=x]

Pruébalo en línea!

usuario28667
fuente

1

Se permiten funciones anónimas, por lo que no necesita f=la primera variante. Además z<-2*y=x!zguarda un byte: ¡ Pruébelo en línea!

Laikoni

3

Excel, 20 bytes

=A1-2^INT(LOG(A1,2))

IanM_Matrix1
fuente

Bienvenido al sitio! :)

DJMcMayhem

3

Excel, 36 31 bytes

-5 bytes gracias a @ IanM_Matrix1

=BIN2DEC(MID(DEC2BIN(A1),2,99))

Nada interesante.

Wernisch
fuente

Reduzca el tamaño a 31 bytes reemplazando REPLACE por un MID: = BIN2DEC (MID (DEC2BIN (A1), 2,99))

IanM_Matrix1