Número diferente, mesmo peso

22

fundo

O peso de Hamming de um número inteiro é o número de unidades em sua representação binária. Para esse desafio, os números inteiros são representados com 32 bits e não são assinados.

Desafio

Dado um número inteiro entre 0 e 2 ^ 32-1 (não inclusivo), produza um número inteiro diferente dentro do mesmo intervalo e também com o mesmo peso de Hamming.

Exemplos

Input (Decimal) | Input (Binary) | Hamming weight | Possible output (Decimal)
       46       |   0b0010 1110  |       4        |      15
       12       |   0b0000 1100  |       2        |      3
        1       |   0b0000 0001  |       1        |      2
        3       |   0b0000 0011  |       2        |      6
      2^31      |   0b1000....0  |       1        |      1
      2^31+2    |   0b1000...10  |       2        |      3
      2^32-5    |   0b1111..011  |       31       |      2^31-1
      2^32-2    |   0b1111....0  |       31       |      2^31-1
        0       |   0b0000 0000  |       0        | None (This case need not be handled)
      2^32-1    |   0b1111....1  |       32       | None (This case need not be handled)

Pontuação

Isso é , então a solução com o menor número de bytes em cada idioma vence.

musicman523
fonte
2
Eu sugiro adicionar um número ímpar entre 2 ^ 31 + 1 e 2 ^ 32-3, pois algumas respostas estão falhando nisso.
Ørjan Johansen
Relacionado.
Martin Ender
Como você acabou de adicionar 2^31+2, repetirei que disse um número ímpar . As respostas em questão só falhou quando tanto o maior e o menor bit são 1.
Ørjan Johansen
Eu sou um idiota. Obrigado. Vai corrigir isso
musicman523
1
@ musicman523 Por acaso navegava por perguntas ativas e vi essa. E percebeu que você ainda não adicionou os casos de teste solicitados.
Draco18s 29/04

Respostas:

29

montagem x86-64, 5 4 bytes

   0:   97                      xchg   %eax,%edi
   1:   d1 c0                   rol    %eax
   3:   c3                      retq   

Uma função que usa a convenção de chamada C que gira bit a bit seu argumento deixado em 1 bit.

Anders Kaseorg
fonte
Droga - eu estava prestes a postar exatamente isso - bem feito :)
Digital Trauma
12
assembly vence Jelly: o
Uriel
Isso não é multiplicado por 2? Se assim for, então a minha 2 byte Pyth resposta provavelmente ganha
NoOneIsHere
@NoOneIsHere Não, isso não é multiplicação por 2. A multiplicação por 2 envia metade das entradas para fora do intervalo necessário e, se você ignorar o bit de estouro à esquerda, diminuiu o peso de Hamming em 1. Isso é um bit a bit rotação , que traz o bit de excesso de volta da direita.
Anders Kaseorg
1
O @DigitalTrauma GCC 4.9.0 e posterior é inteligente o suficiente para compilar n << 1 | n >> 31em rolvez de ror(salvar um byte).
Anders Kaseorg 3/17/17
8

Python, 20 bytes

lambda x:x*2%~-2**32

Rotação bit a bit deixada em 1 bit.

Anders Kaseorg
fonte
6

MATL , 9 bytes

32&B1YSXB

Desloca circularmente a representação binária de 32 dígitos um passo para a direita.

Experimente online!

Luis Mendo
fonte
6

Geléia , 10 8 bytes

‘&~^^N&$

Troca o conjunto menos significativo e o bit não definido.

Experimente online!

Como funciona

‘&~^^N&$  Main link. Argument: n

‘         Increment; yield n+1, toggling all trailing set bits and the rightmost
          unset bit.
  ~       Bitwise NOT; yield ~n, toggling ALL bits of n.
 &        Bitwise AND; yield (n+1)&~n, keeping the only bit that differs in n+1 and
          ~n, i.e., the rightmost unset bit.
   ^      Perform bitwise XOR with n, toggling the rightmost unset bit.
       $  Combine the two links to the left into a monadic chain.
     N        Negate; yield -n. Since ~n = -(n+1) in 2's complement, -n = ~n+1.
      &       Take the bitwise AND of n and -n. Since -n = ~n + 1 and n = ~~n, the
              same reasoning that applied for (n+1)&~n applies to -n&n; it yields
              the rightmost unset bit of ~n, i.e., the rightmost set bit of n.
    ^      XOR the result to the left with the result to the right, toggling the
           rightmost set bit of the left one.
Dennis
fonte
5

JavaScript (ES6), 35 31 bytes

Procura a primeira transição de bits (0 → 1 ou 1 → 0) e a inverte.

f=(n,k=3)=>(n&k)%k?n^k:f(n,k*2)

Demo

Rotação de bits, 14 bytes

Muito mais curto, mas menos divertido.

n=>n>>>31|n<<1

Demo

Arnauld
fonte
Os operadores JavaScript bit a bit fornecem números inteiros assinados de 32 bits em vez de não assinados. Por exemplo, f(2147483647)é -1073741825e (n=>n>>>31|n<<1)(2147483647)é -2.
Anders Kaseorg 1/06
2
Tudo bem, desde que não haja mais que 32 bits.
musicman523
Você pode adicionar uma explicação para a primeira? Estou tentando aprender Javascript e estou meio que sem saber como você está chamando f com k indefinido e ainda está obtendo uma resposta razoável!
musicman523
2
@ musicman523 Aqui está a dica correspondente. Basicamente, ké definido inicialmente como undefinede aproveitamos o fato de que ~undefinedé igual a -1.
precisa
@ musicman523 (eu não estou usando esta dica mais na versão atualizada Mas não hesite em perguntar se você tem outras perguntas sobre a resposta original..)
Arnauld
4

Brain-Flak , 78 bytes

(([()()])[[]()]){((){}<({({})({}())}{})>)}{}([(({}(({}){})())<>)]){({}())<>}{}

Experimente online!

Retorna 2n se n <2 ^ 31 e 2n + 1-2 ^ 32 caso contrário. Infelizmente, como o Brain-Flak não possui uma maneira rápida de determinar o sinal de um número, o programa atinge o tempo limite no TIO se a entrada diferir de 2 ^ 31 em mais de 500000.

Explicação

Primeiro, pressione -2 ^ 32 na pilha:

(([()()])[[]()])                               push (initial value) -2 and (iterator) -5
                {((){}<                >)}     do 5 times:
                       ({({})({}())}{})        replace the current (negative) value with the negation of its square
                                            {}   pop the (now zero) iterator

Em seguida, calcule a saída desejada:

      (({}){})                        replace n by 2n on left stack
   ({}        ())                     push 2n+1-2^32 on left stack
  (              <>)                  push again on right stack
([                  ])                push its negation on right stack
                      {({}())<>}      add 1 to the top value of each stack until one of them reaches zero
                                {}    pop this zero, and implicitly print the number below it on the stack
Nitrodon
fonte
3

dc, 10

?2~z31^*+p

Experimente online .

Esta é uma implementação aritmética de uma rotação de 32 bits à direita:

?           # input
 2~         # divmod by 2 - quotient pushed first, then the remainder
   z        # z pushes the size of the stack which will be 2 (quotient and remainder) ...
    31^     #  ... and take that 2 to the 31st power
       *    # multiply the remainder by 2^31
        +   # add
         p  # output
Trauma Digital
fonte
3

Java 8, 117 17 29 bytes

n->n*2%~-(long)Math.pow(2,32)

+12 bytes, alterando intpara long, porque into tamanho máximo é2³¹-1

100 89 bytes salvos criando uma porta de incrível resposta Python @AndersKaseorg .

Experimente aqui.

Saídas:

46 (101110):                                     92 (1011100)
12 (1100):                                       24 (11000)
1 (1):                                           2 (10)
3 (11):                                          6 (110)
10000 (10011100010000):                          20000 (100111000100000)
987654 (11110001001000000110):                   1975308 (111100010010000001100)
2147483648 (10000000000000000000000000000000):   1 (1)
4294967294 (11111111111111111111111111111110):   4294967293 (11111111111111111111111111111101)

Resposta antiga ( 117 118 bytes):

n->{long r=0;for(;!n.toBinaryString(++r).replace("0","").equals(n.toBinaryString(n).replace("0",""))|r==n;);return r;}

+1 byte, alterando intpara long, porque into tamanho máximo é2³¹-1

Experimente aqui.

Saídas:

46 (101110):                                     15 (1111)
12 (1100):                                       3 (11)
1 (1):                                           2 (10)
3 (11):                                          5 (101)
10000 (10011100010000):                          31 (11111)
987654 (11110001001000000110):                   255 (11111111)
2147483648 (10000000000000000000000000000000):   1 (1)
Kevin Cruijssen
fonte
2

Mathematica, 29 bytes

Mod@##+Quotient@##&[2#,2^32]&

Experimente na sandbox Wolfram

Gira à esquerda aritmeticamente: primeiro multiplique por 2, o que possivelmente altera o número fora da faixa, depois corte o dígito fora da faixa Mod[...,2^32]e adicione-o novamente à direita com +Quotient[...,2^32].

(O Mathematica tem um único componente que fornece o módulo e o quociente de uma só vez, mas é QuotientRemainder, o que é um pouco um obstáculo para o golfe ...)

Não é uma árvore
fonte
Mod 2 ^ 32-1? (4 mais para ir)
user202729
2

APL, 12 bytes

(2⊥32⍴1)|2×⊢

Quão?

           ⊢  ⍝ monadic argument
         2×   ⍝ shift left (×2)
(2⊥32⍴1)|     ⍝ modulo 2^32 - 1
Uriel
fonte
1

R, 42 bytes 63

function(x){s=x;while(s==x){sample(binaryLogic::as.binary(x))}}

Baralha aleatoriamente os bits, mas verifica se não retornou o mesmo número por acaso.

BLT
fonte
1

Espaço em branco , 81 80 bytes

(1 byte salvo graças a @ Ørjan Johansen, lembrando-me que o dup é menor que o push 0)

   
 
 	
					 
    	 
	 		
	 
   	        
 
 	  
 
 	  
	   
  
   	 
	 	 	
 	

Experimente online!

Implementa basicamente um deslocamento de bits cíclico à direita usando aritmética inteira. Pressionar uma constante grande é caro no espaço em branco, por isso economizamos alguns bytes pressionando 2 ^ 8 e quadrando-o duas vezes. (Salva 1 byte acima (2 ^ 16) ^ 2 e 10 bytes pressionando 2 ^ 32 diretamente.)

Explicação

sssn  ; push 0
sns   ; dup
tntt  ; getnum from stdio
ttt   ; retrieve n from heap and put it on the stack
sns   ; dup
ssstsn ; push 2
tstt  ; mod - check if divisible by 2 (i.e. even)
ntsn  ; jez "even"
ssstssssssssn ; push 2^8
sns   ; dup
tssn  ; mul - square it to get 2^16
sns   ; dup
tssn  ; mul - square it to get 2^32
tsss  ; add 2^32 so MSB ends up set after the divide
nssn  ; even:
ssstsn ; push 2
tsts  ; divide by 2, aka shift right
tnst  ; putnum - display result
Ephphatha
fonte
1
Eu acho que você pode substituir o segundo push 0por dupum comando anterior.
Ørjan Johansen
Você está certo, eu só terminar de adicionar sintaxe atalho para o meu transpiler então eu tenho usado muito ...
Efatá
0

Python 2.7, 89 bytes

Programa completo:

from random import*;a=list(bin(input())[2:].zfill(32));shuffle(a);print int(''.join(a),2)

Experimente online!

Sugestões são bem-vindas! :)

Koishore Roy
fonte
Isso não é válido porque, por acaso, pode retornar o mesmo número novamente.
Ørjan Johansen
0

Japt , 5 bytes

Ñ%3pH

Rotação bit a bit, como a maioria das respostas aqui.

Tente

Modalidade de ignorância
fonte