Inna liczba, ta sama waga

22

tło

Ciężar Hamminga liczby całkowitej jest liczba jedynek w jej reprezentacji binarnej. W przypadku tego wyzwania liczby całkowite są reprezentowane przez 32 bity i są niepodpisane.

Wyzwanie

Biorąc pod uwagę liczbę całkowitą od 0 do 2 ^ 32-1 (nie obejmuje), wypisz inną liczbę całkowitą w tym samym zakresie, a także o tej samej masie Hamminga.

Przykłady

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)

Punktacja

To jest , więc wygrywa rozwiązanie z najmniejszą liczbą bajtów w każdym języku.

musicman523
źródło
2
Sugerowałbym dodanie nieparzystej liczby między 2 ^ 31 + 1 a 2 ^ 32-3, ponieważ niektóre odpowiedzi na to nie pozwalają.
Ørjan Johansen
Związane z.
Martin Ender
Ponieważ właśnie dodałeś 2^31+2, powtórzę, że powiedziałem liczbę nieparzystą . Odpowiedzi, o których mowa, zawiodły tylko wtedy, gdy zarówno najwyższy, jak i najniższy bit są 1.
Ørjan Johansen
Jestem głupcem. Dziękuję Ci. Naprawi to
musicman523
1
@ musicman523 Właśnie przypadkiem przeglądałem aktywne pytania i widziałem to. Zauważyłem, że nadal nie dodałeś wymaganych przypadków testowych.
Draco18s

Odpowiedzi:

29

Zestaw x86-64, 5 4 bajtów

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

Funkcja korzystająca z konwencji wywoływania C, która bitowo obraca swój argument w lewo o 1 bit.

Anders Kaseorg
źródło
Cholera - właśnie miałem opublikować dokładnie to - dobrze zrobione :)
Digital Trauma
12
montaż bije Galaretkę: o
Uriel
Czy to nie jest mnożenie przez 2? Jeśli tak, to prawdopodobnie moja 2-bajtowa odpowiedź na pytanie Pyth wygrywa
NoOneIsHere
@NoOneIsHere Nie, to nie mnożenie przez 2. Mnożenie przez 2 przesyła połowa wejść poza wymaganym zakresie, a jeśli ignorować bit przepełnienia po lewej, masz spadł ciężar Hamminga o 1. To jest bitowe obrót , który przywraca bit przelewu z prawej strony.
Anders Kaseorg,
1
@DigitalTrauma GCC 4.9.0 i później są wystarczająco inteligentny, aby skompilować n << 1 | n >> 31pod rolzamiast ror(oszczędność bajt).
Anders Kaseorg,
8

Python, 20 bajtów

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

Bitowy obrót w lewo o 1 bit.

Anders Kaseorg
źródło
6

Galaretka , 10 8 bajtów

‘&~^^N&$

Zamienia najmniej znaczący ustawiony i nieuzbrojony bit.

Wypróbuj online!

Jak to działa

‘&~^^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
źródło
5

JavaScript (ES6), 35 31 bajtów

Wyszukuje pierwsze przejście bitowe (0 → 1 lub 1 → 0) i odwraca je.

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

Próbny

Rotacja bitów, 14 bajtów

Znacznie krótszy, ale mniej zabawny.

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

Próbny

Arnauld
źródło
Bitowe operatory JavaScript podają liczby całkowite ze znakiem 32-bitowym, a nie bez znaku. Na przykład f(2147483647)jest -1073741825i (n=>n>>>31|n<<1)(2147483647)jest -2.
Anders Kaseorg
2
Jest w porządku, o ile nie ma więcej niż 32 bity.
musicman523
Czy możesz dodać wyjaśnienie do pierwszego? Próbuję nauczyć się Javascript i jestem nieco zaniepokojony tym, jak dzwonisz fz k niezdefiniowany i wciąż otrzymuję rozsądną odpowiedź!
musicman523
2
@ musicman523 Oto odpowiednia wskazówka. Zasadniczo kjest początkowo ustawiony undefinedi korzystamy z faktu, że ~undefinedjest równy -1.
Arnauld
@ musicman523 (Nie używam już tej wskazówki w zaktualizowanej wersji. Ale nie wahaj się zapytać, czy masz inne pytania dotyczące oryginalnej odpowiedzi.)
Arnauld
4

Brain-Flak , 78 bajtów

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

Wypróbuj online!

Zwraca 2n, jeśli n <2 ^ 31, a 2n + 1-2 ^ 32 w przeciwnym razie. Niestety, ponieważ Brain-Flak nie ma szybkiego sposobu na określenie znaku liczby, program przekroczy limit czasu TIO, jeśli dane wejściowe różnią się od 2 ^ 31 o więcej niż około 500000.

Wyjaśnienie

Najpierw pchnij -2 ^ 32 na stos:

(([()()])[[]()])                               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

Następnie oblicz żądane dane wyjściowe:

      (({}){})                        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
źródło
3

dc, 10

?2~z31^*+p

Wypróbuj online .

Jest to arytmetyczna implementacja 32-bitowego obrotu w prawo:

?           # 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
Cyfrowa trauma
źródło
3

Java 8, 117 17 29 bajtów

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

+12 bajtów, zmieniając intna long, ponieważ intmaksymalny rozmiar to2³¹-1

100 89 bajtów zapisanych dzięki utworzeniu portu niesamowitej odpowiedzi Pythona na @AndersKaseorg .

Wypróbuj tutaj.

Wyjścia:

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)

Stara odpowiedź ( 117 118 bajtów):

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

+1 bajt, zmieniając intna long, ponieważ intmaksymalny rozmiar to2³¹-1

Wypróbuj tutaj.

Wyjścia:

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
źródło
2

Mathematica, 29 bajtów

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

Wypróbuj w piaskownicy Wolfram

Obraca arytmetycznie w lewo: najpierw pomnóż przez 2, co może przesunąć liczbę poza zakres, a następnie odetnij cyfrę poza zakresem za pomocą Mod[...,2^32]i dodaj ją ponownie po prawej za pomocą +Quotient[...,2^32].

(Mathematica ma jedno wbudowane narzędzie, które daje moduł i iloraz za jednym razem, ale QuotientRemainderjest to trochę handicap golfowy…)

Nie drzewo
źródło
Mod 2 ^ 32-1? (
Pozostało
2

APL, 12 bajtów

(2⊥32⍴1)|2×⊢

W jaki sposób?

           ⊢  ⍝ monadic argument
         2×   ⍝ shift left (×2)
(2⊥32⍴1)|     ⍝ modulo 2^32 - 1
Uriel
źródło
1

R 42 42 bajty

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

Losowo tasuje bity, ale sprawdza, czy przypadkiem nie zwróci tej samej liczby.

BLT
źródło
1

Biała spacja , 81 80 bajtów

(1 bajt zapisany dzięki @ Ørjan Johansen przypominając mi, że dup jest krótszy niż push 0)

   
 
 	
					 
    	 
	 		
	 
   	        
 
 	  
 
 	  
	   
  
   	 
	 	 	
 	

Wypróbuj online!

Zasadniczo implementuje cykliczną prawą przesunięcie bitów za pomocą arytmetyki liczb całkowitych. Przesuwanie dużej stałej jest drogie w Białej Przestrzeni, więc oszczędzamy niektóre bajty, naciskając 2 ^ 8 i dwukrotnie zwiększając kwadrat. (Oszczędza 1 bajt ponad (2 ^ 16) ^ 2 i 10 bajtów przez przepchnięcie 2 ^ 32 bezpośrednio.)

Wyjaśnienie

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
źródło
1
Myślę, że można zastąpić drugą push 0z dupjednego polecenia wcześniej.
Ørjan Johansen
Masz rację, właśnie skończyłem dodawanie składni skrótu do mojego transpilera, więc używałem go za dużo ...
Ephphatha
0

Python 2.7, 89 bajtów

Pełny program:

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

Wypróbuj online!

Sugestie mile widziane! :)

Koishore Roy
źródło
To nie jest ważne, ponieważ może przypadkowo zwrócić ten sam numer ponownie.
Ørjan Johansen
0

Japt , 5 bajtów

Ñ%3pH

Bitowa rotacja, jak większość odpowiedzi tutaj.

Spróbuj

Wcielenie ignorancji
źródło