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 golf golfowy , więc wygrywa rozwiązanie z najmniejszą liczbą bajtów w każdym języku.

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.

Python, 20 bajtów

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

Bitowy obrót w lewo o 1 bit.

MATL , 9 bajtów

32&B1YSXB

Okrągłe przesunięcie 32-cyfrowej reprezentacji binarnej o krok w prawo.

Wypróbuj online!

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.

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

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

;[ 46, 12, 255, 2**32-2 ]
.map(n => {
  r = f(n);
  console.log((n >>> 0), '=', (n >>> 0).toString(2), '-->', (r >>> 0), '=', (r >>> 0).toString(2));
})

Rotacja bitów, 14 bajtów

Znacznie krótszy, ale mniej zabawny.

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

Próbny

let f =

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

;[ 46, 12, 255, 2**32-2 ]
.map(n => {
  r = f(n);
  console.log((n >>> 0), '=', (n >>> 0).toString(2), '-->', (r >>> 0), '=', (r >>> 0).toString(2));
})

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

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

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)

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

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

05AB1E , 5 bajtów

·žJ<%

Wypróbuj online!

Wyjaśnienie

Wykorzystuje sztuczkę, aby obrócić reprezentację binarną pozostawioną o 1 bit od odpowiedzi python Andersa Kaseorga .

·       # input * 2
    %   # modulus
 žJ<    # 2^32-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.

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

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! :)

Pari / GP , 15 bajtów

n->2*n%(2^32-1)

Wypróbuj online!

Japt , 5 bajtów

Ñ%3pH

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

Spróbuj

Perl 5 -p , 39 bajtów

$_=sprintf'0b%b',$_;$_=oct$_.int s/10//

Wypróbuj online!

Python 3 , 45 bajtów

lambda i:int(f'{i:32b}'[1:]+f'{i:32b}'[:1],2)

Wypróbuj online!

C ++ (gcc) , 45 39 bajtów

-6 bajtów dzięki x pułapowi na catcat

auto h(unsigned x){return x%2<<31|x/2;}

Wypróbuj online!