Qual é o número de bits reverso (binário)?

33

Então você recebe um número POSITIVO de base 10 (decimal). Seu trabalho é reverter os dígitos binários e retornar esse número base 10.

Exemplos:

1 => 1 (1 => 1)
2 => 1 (10 => 01)
3 => 3 (11 => 11)
4 => 1 (100 => 001)
5 => 5 (101 => 101)
6 => 3 (110 => 011)
7 => 7 (111 => 111)
8 => 1 (1000 => 0001)
9 => 9 (1001 => 1001)
10 => 5 (1010 => 0101)

Este é um desafio do , portanto, a solução que usa menos bytes vence.

Este é o A030101 no OEIS.

juniorRubyist
fonte
2
"Reverter os bits" significa reverter seus dígitos binários? Às vezes, também pode significar inverter tudo .
ETHproductions
Sim. Desculpe por não estar claro.
precisa saber é o seguinte
Isso e isso são muito semelhantes.
Geobits 4/17/17
OEIS A030101 .
orlp
1
"base 10" Alguma razão específica para isso?
CalculadoraFeline

Respostas:

20

Python , 29 bytes

lambda n:int(bin(n)[:1:-1],2)

Experimente online!

Esta é uma função anônima e sem nome que retorna o resultado.


Primeiro, bin(n)converte o argumento em uma cadeia de caracteres binária. Normalmente, reverteríamos isso com a notação de fatia [::-1]. Isso lê a string com um passo de -1 , ou seja, para trás. No entanto, cadeias binárias em Python são prefixadas com an 0be, portanto, damos o segundo argumento do fatiamento como 1 , dizendo ao Python para ler para trás, terminando no índice 1 , não lendo os índices 1 e 0 .

Agora que temos a string binária reversa, passamos para int(...)a segunda com o segundo argumento como 2 . Isso lê a sequência como um número inteiro base 2, que é implícito retornado pela expressão lambda.

FlipTack
fonte
2
Vencê-lo por 9 segundos.
mbomb007
6
@ mbomb007 então minha resposta é inválida porque você clicou no botão de postagem 9 segundos antes da mão? Só porque atingimos o mesmo golfe ao mesmo tempo não significa que precisamos excluir as respostas. Se alguma coisa, culpe a questão do esforço zero.
FlipTack
3
Não é inválido, mas definitivamente inútil. Se eu fosse mais lento, simplesmente excluiria o meu e postaria um comentário sobre o mais rápido que eu fiz.
mbomb007
1
@steenbergh Quem se importa? O mesmo código, a mesma pontuação.
Mbomb007
17

Python, 29 bytes

lambda n:int(bin(n)[:1:-1],2)

Experimente online

mbomb007
fonte
1
Isto é o que eu teria feito. ;)
juniorRubyist
13

JavaScript (ES6), 30 28 bytes

Guardado 2 bytes graças a @Arnauld

f=(n,q)=>n?f(n>>1,q*2|n%2):q

Isso basicamente calcula o inverso um bit de cada vez: Começamos com q = 0 ; enquanto n for positivo, multiplicamos q por 2, separamos o último bit de n com n>>1e o adicionamos a q com |n%2. Quando n atinge 0, o número foi revertido com sucesso e retornamos q .

Graças aos longos nomes internos de JS, resolver esse desafio da maneira mais fácil leva 44 bytes:

n=>+[...n.toString(2),'0b'].reverse().join``

Usando recursão e uma string, você pode obter uma solução de 32 bytes que faz a mesma coisa:

f=(n,q='0b')=>n?f(n>>1,q+n%2):+q
ETHproductions
fonte
f=(n,q)=>n?f(n>>1,q*2|n%2):qquase funciona. Mas infelizmente não n=0.
Arnauld
O @Arnauld OP ainda não respondeu se a entrada sempre será positiva, mas, se for, então 0 não precisa ser tratado.
FlipTack
Esse é um acompanhamento tardio, mas agora se sabe que a entrada é sempre positiva.
Arnauld
@ Arnauld Thanks!
ETHproductions
10

Java 8, 53 47 46 45 bytes

  • -4 bytes graças a Titus
  • -1 byte graças a Kevin Cruijssen

Esta é uma expressão lambda que tem o mesmo princípio que a resposta da ETH (embora a recursão tenha sido muito detalhada em Java, então fazemos um loop):

x->{int t=0;for(;x>0;x/=2)t+=t+x%2;return t;}

Experimente online!

Isso pode ser atribuído com IntFunction<Integer> f = ...e depois chamado com f.apply(num). Expandido, não destruído e comentado, fica assim:

x -> { 
    int t = 0;           // Initialize result holder   
    while (x > 0) {      // While there are bits left in input:
        t <<= 1;         //   Add a 0 bit at the end of result
        t += x%2;        //   Set it to the last bit of x
        x >>= 1;         //   Hack off the last bit of x
    }              
    return t;            // Return the final result
};
FlipTack
fonte
1
Economize 3 bytes em t*2vez de (t<<1), mais um movendo esse cálculo da cabeça do loop para o corpo do loop. Você pode usar em xvez de x>0para a condição?
Titus
2
@Titus não sem uma conversão explícita para um booleano, mas obrigado pelas outras dicas! Também acabei de perceber que x>>=1pode ser substituído por x/=2, pois será automaticamente uma divisão inteira.
FlipTack
45 bytes (Alterado t=t*2+para t+=t+.)
Kevin Cruijssen 25/10
@KevinCruijssen nice one!
FlipTack
9

J, 6 bytes

|.&.#:

|. marcha ré

&. sob

#: base 2

Adão
fonte
8

Gelatina , 3 bytes

BUḄ

Experimente online!

B   # convert to binary
 U  # reverse
  Ḅ # convert to decimal
Riley
fonte
7
Isso é bem curto, BUB
Cyoce
Hmm ... Isso é realmente 3 bytes ?
aioobe
1
@aioobe Yep. O Jelly usa sua própria página de códigos, onde cada um desses caracteres tem 1 byte.
Riley
Legal, obrigado! <pad>
aioobe
8

Mathematica, 19 bytes

#~IntegerReverse~2&
ngenisis
fonte
7

Labirinto, 23 bytes

?_";:_2
  :   %
 @/2_"!

Bem, isso é estranho ... isso retorna o número BINÁRIO reverso ... Obrigado @ Martin Ender por apontar tanto o meu bug quanto o meu ID 10T. Portanto, isso não funciona, vou ter que encontrar outra solução.

C Anderson
fonte
1
Bem-vindo ao PPCG e bom primeiro post! Concluir um desafio em um idioma como o Labyrinth pode ser muito difícil. Por aqui, geralmente prefixamos a primeira linha de uma resposta com um ou dois hashes, para que ela apareça como um cabeçalho:# Labyrinth, 89 bytes
ETHproductions
1
Você acidentalmente omitiu um espaço à esquerda da segunda linha? Tal como está, o programa apenas salta para frente e para trás na primeira linha, porque _estão nos cruzamentos.
Martin Ender
Infelizmente, notei que isso não é válido, independentemente, porque o desafio pede a representação da base 10 do número invertido, não a representação binária.
Martin Ender
6

C, 48 44 43 42 bytes

-1 byte graças a gurka e -1 byte graças a anatolyg:

r;f(n){for(r=n&1;n/=2;r+=r+n%2);return r;}

Solução anterior de 44 bytes:

r;f(n){r=n&1;while(n/=2)r=2*r+n%2;return r;}

Solução anterior de 48 bytes:

r;f(n){r=0;while(n)r=2*(r+n%2),n/=2;return r/2;}

Ungolfed e uso:

r;
f(n){
 for(
  r=n&1;
  n/=2;
  r+=r+n%2
 );
 return r;}
}


main() {
#define P(x) printf("%d %d\n",x,f(x))
P(1);
P(2);
P(3);
P(4);
P(5);
P(6);
P(7);
P(8);
P(9);
P(10);
}
Karl Napf
fonte
rJá não foi inicializado com zero aqui r;f(n){r=0;, por exemplo, o r=0;é desnecessário? Também erro de digitação menor: " Solução anterior de 48 bytes"
simon
1
@ gurka A função deve ser reutilizável.
Karl Napf
1
Eu acho que os forloops são sempre pelo menos tão curtos quanto os whileloops, e geralmente mais curtos.
Anatolyg
@anatolyg algo como r;f(n){for(r=n&1;n/=2;r=2*r+n%2);return r;}:? 1 byte mais curto, mas não tenho certeza se é válido C (C99).
simon
Sim; também, por sua vez, =para +=torná-lo mais curto e mais ofuscado
anatolyg
5

Ruby, 29 28 bytes

->n{("%b"%n).reverse.to_i 2}

"% b"% n formata a entrada n como uma sequência binária, inverta e depois converta novamente em um número

Casos de uso / teste:

m=->n{("%b"%n).reverse.to_i 2}
m[1] #=> 1
m[2] #=> 1
m[3] #=> 3
m[4] #=> 1
m[5] #=> 5
m[6] #=> 3
m[7] #=> 7
m[8] #=> 1
m[9] #=> 9
m[10] #=> 5
Alexis Andersen
fonte
@ Titus Acho que você não entendeu a resposta. 2é a base para a qual ele está convertendo e né a entrada. ->args{return value}é a sintaxe rubi lambda
Cyoce
Você pode remover os parênteses .to_i(2)?
precisa saber é
@ Cyoce com certeza, obrigado.
Alexis Andersen
4

Java (OpenJDK) , 63 bytes

a->a.valueOf(new StringBuffer(a.toString(a,2)).reverse()+"",2);

Experimente online!

Graças a cutucar por -12 bytes e Cyoce por -8 bytes!

Pavel
fonte
Mesmo que submissões REPL são permitidos, eles ainda seguem a regra de que você não pode assumir entrada está em variáveis pré-definidas (como aneste contexto)
FlipTack
@FlipTack Oops. Foi originalmente uma função antes de eu me lembrei do repl existia
Pavel
1
Além disso, no futuro, use printem vez de printlnpara o golfe :)
FlipTack
1
StringBuffersalva um byte sobreStringBuilder
Puxar
1
Você poderia fazer em +""vez de .toString()?
Cyoce 8/17
3

Perl 6 , 19 bytes

{:2(.base(2).flip)}
Sean
fonte
Onde está a entrada?
Titus
Esta é uma função que aceita um único parâmetro $_. Não é mencionado pelo nome, mas o basemétodo é chamado.
Sean
2
@Titus no Perl 6 a Block é um tipo de código, ou seja, é um objeto que pode ser chamado. A descrição acima é uma expressão que você pode pegar e atribuir a uma variável como uma função ou lambda em outro idioma ou ligar diretamente - {:2(.base(2).flip)}(10)no REPL imprimirá 5. Portanto, ele atende aos critérios de código-golfe padrão de uma função.
Hbbs
3

Haskell, 36 bytes

0!b=b
a!b=div a 2!(b+b+mod a 2)
(!0)

O mesmo algoritmo (e comprimento!) Da resposta JavaScript da ETHproductions .

Lynn
fonte
3

Utilitários Bash / Unix, 24 23 bytes

dc -e2i`dc -e2o?p|rev`p

Experimente online!

Mitchell Spector
fonte
Uma visão corajosa de Bash! 😉
juniorRubyist
@juniorRubyist - Obrigado!
Mitchell Spector
3

PHP, 33 bytes

<?=bindec(strrev(decbin($argn)));

converter para base2, string reversa, converter para decimal. Salve em arquivo e execute como pipe com -F.

sem builtins:

iterativo, 41 bytes

for(;$n=&$argn;$n>>=1)$r+=$r+$n%2;echo$r;

Enquanto a entrada tiver definido os bits, saia um pouco da entrada e empurre-a para a saída. Corra como cano com -nR.

recursivo, 52 bytes

function r($n,$r=0){return$n?r($n>>1,$r*2+$n%2):$r;}
Titus
fonte
@ JörgHülsermann Os 44 bytes possuem $r+=$r. Mas na verdade não me lembro por que coloquei isso na frente.
Titus
2

MATL , 4 bytes

BPXB

Experimente online!

Explicação

B     % Input a number implicitly. Convert to binary array
P     % Reverse array
XB    % Convert from binary array to number. Display implicitly
Luis Mendo
fonte
2

Pitão, 6 bytes

i_.BQ2

Conjunto de testes disponível aqui.

Explicação

i_.BQ2
    Q     eval(input())
  .B      convert to binary
 _        reverse
i    2    convert from base 2 to base 10
Mike Bufardeci
fonte
2

Japt , 5 bytes

¢w n2

Experimente Online!

Oliver
fonte
1
Bom, exatamente o que eu tinha. Também )poderia ser um espaço :-)
ETHproductions
2

Scala, 40 bytes

i=>BigInt(BigInt(i)toString 2 reverse,2)

Uso:

val f:(Int=>Any)=i=>BigInt(BigInt(i)toString 2 reverse,2)
f(10) //returns 5

Explicação:

i =>          // create an anonymous function with a parameter i
  BigInt(       //return a BigInt contructed from
    BigInt(i)     //i converted to a BigInt
    toString 2    //converted to a binary string
    reverse       //revered
    ,           
    2             //interpreted as a binary string
  )
corvus_192
fonte
1

Mathematica, 38 bytes

#+##&~Fold~Reverse[#~IntegerDigits~2]&
JungHwan Min
fonte
1

Groovy, 46 bytes

{0.parseInt(0.toBinaryString(it).reverse(),2)}
Urna de polvo mágico
fonte
Isso requer alguma entrada?
Titus
1
@Titus itrefere-se ao argumento dado a um bloco
IIRC
Eu amo como esse tamanho tem o mesmo tamanho da minha resposta Java - Java e groovy, uni-vos!
FlipTack
1
@FlipTack eu vou chorar agora.
Urna de polvo mágico
1

CJam , 8 bytes

ri2bW%2b

Experimente online!

Explicação

ri          e# Read integer
  2b        e# Convert to binary array
    W%      e# Reverse array
      2b    e# Convert from binary array to number. Implicitly display
Luis Mendo
fonte
1

Lote, 62 bytes

@set/an=%1/2,r=%2+%1%%2
@if %n% gtr 0 %0 %n% %r%*2
@echo %r%

Explicação: Na primeira passagem, %1contém o parâmetro de entrada enquanto %2está vazio. Portanto, avaliamos a nmetade %1e ro +%1módulo 2 (o %operador deve ser duplicado para citá-lo). Se nnão for zero, nos chamamos de passagem recursiva de cauda ne uma expressão que é avaliada na próxima passagem dobrando efetivamente a rcada vez.

Neil
fonte
1

C #, 98 bytes

using System.Linq;using b=System.Convert;a=>b.ToInt64(string.Concat(b.ToString(a,2).Reverse()),2);
Horváth Dávid
fonte
1

R, 55 bytes

sum(2^((length(y<-rev(miscFuncs::bin(scan()))):1)-1)*y)

Lê a entrada do stdin e, consequentemente, usa a binfunção do miscFuncspacote para converter de decimal em um vetor binário.

Billywob
fonte
1

Pushy , 19 bytes

Nenhuma conversão básica embutida!

$&2%v2/;FL:vK2*;OS#

Experimente online!

Pushy tem duas pilhas, e esta resposta faz uso extensivo disso.

Existem duas partes e dois neste programa. Primeiro, $&2%v2/;Fconverte o número em sua representação binária reversa:

            \ Implicit: Input is an integer on main stack.
$      ;    \ While i != 0:
 &2%v       \   Put i % 2 on auxiliary stack
     2/     \   i = i // 2 (integer division)
        F   \ Swap stacks (so result is on main stack)

Dado o exemplo 10, as pilhas apareceriam da seguinte maneira em cada iteração:

1: [10]
2: []

1: [5]
2: [0]

1: [2]
2: [0, 1]

1: [1]
2: [0, 1, 0]

1: [0]
2: [0, 1, 0, 1]

Podemos ver que após a iteração final, 0, 1, 0, 1foi criada na segunda pilha - os dígitos binários reversos de 10 0b1010,.

A segunda parte do código,, L:vK2*;OS#é retirada da minha resposta anterior, que converte binário em decimal . Usando o método descrito e explicado nessa resposta, ele converte os dígitos binários da pilha em um número inteiro de base 10 e imprime o resultado.

FlipTack
fonte
0

k, 18 bytes

{2/:|X@&|\X:0b\:x}

Exemplo:

k){2/:|X@&|\X:0b\:x}6
3
skeevey
fonte
0

C #, 167 bytes

 for(int i = 1; i <= 10; i++)
 {
 var bytes= Convert.ToString(i, 2);
 var value= Convert.ToInt32(byteValue.Reverse()); 
 console.WriteLine(value);
}

Explicação:

Aqui, iterarei n valores e cada vez que o valor inteiro iterado for convertido em valor de byte, inverta esse valor de byte e esse valor de byte será convertido em valor inteiro.

Deepak
fonte
1
Bem vindo ao site! Eu não sei muito sobre c #, mas você certamente tem uma grande quantidade de espaço em branco extra que eu recomendaria remover. Também não está claro como a E / S é tratada neste envio. É padrão escrever uma função ou usá-la STDIN(acho que console.Read()sim, mas você provavelmente saberia melhor do que eu) e STDOUT. De qualquer forma, bem-vindo ao site se você quer um conselho mais experiente no golfe C # Eu recomendaria codegolf.stackexchange.com/questions/173/...
Assistente de trigo
Eu diminuí a votação desta resposta, porque ela não funciona. .Reverse()retorna IEnumerable<char>. Como Convert.ToInt32não possui uma sobrecarga para IEnumerable, lança uma exceção. Além disso, a resposta não segue as regras do código golf: 1) Como nada é especificado, o envio deve ser um programa ou função completo, e não apenas um trecho. 2) usingdeclarações devem ser incluídos na contagem de bytes
raznagul
0

c / c ++ 136 bytes

uint8_t f(uint8_t n){int s=8*sizeof(n)-ceil(log2(n));n=(n&240)>>4|(n&15)<<4;n=(n&204)>>2|(n&51)<<2;n=(n&172)>>1|(n&85)<<1;return(n>>s);}

Não vai ganhar, mas eu queria adotar uma abordagem diferente em c / c ++ 120 bytes na função

#include <math.h>
#include <stdio.h>
#include <stdint.h>

uint8_t f(uint8_t n){
    int s=8*sizeof(n)-ceil(log2(n));
    n=(n&240)>>4|(n&15)<<4;
    n=(n&204)>>2|(n&51)<<2;
    n=(n&172)>>1|(n&85)<<1;
    return (n>>s);
}

int main(){
    printf("%u\n",f(6));
    return 0;
}

Para elaborar o que estou fazendo, usei a função log para determinar o número de bits utilizados pela entrada. Do que uma série de trocas de três bits para a esquerda / direita, dentro / fora, par / ímpar, que inverte todo o número inteiro. Finalmente, mude um pouco para mudar o número de volta para a direita. Usar decimais para deslocamento de bits em vez de hexadecimal é um problema, mas economizou alguns bytes.

mreff555
fonte
Você precisa incluir a declaração da função, portanto, na verdade, são 163 bytes . Embora, se você remover o espaço em branco estranho, poderá reduzi-lo para 136.
DJMcMayhem