Jumlah yang berbeda, berat yang sama

22

Latar Belakang

The Hamming berat dari integer adalah jumlah yang dalam representasi biner. Untuk tantangan ini, bilangan bulat diwakili dengan 32 bit, dan mereka tidak ditandatangani.

Tantangan

Diberikan bilangan bulat antara 0 dan 2 ^ 32-1 (tidak termasuk), menghasilkan bilangan bulat yang berbeda dalam rentang yang sama, dan juga dengan bobot Hamming yang sama.

Contohnya

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)

Mencetak gol

Ini adalah , sehingga solusi dalam byte paling sedikit di setiap bahasa menang.

musicman523
sumber
2
Saya sarankan menambahkan angka ganjil antara 2 ^ 31 + 1 dan 2 ^ 32-3, karena beberapa jawaban gagal pada saat itu.
Ørjan Johansen
Terkait
Martin Ender
Karena Anda baru saja menambahkan 2^31+2, saya akan mengulangi bahwa saya mengatakan angka ganjil . Jawaban tersebut hanya gagal ketika kedua tertinggi dan bit terendah adalah 1.
Ørjan Johansen
Saya bodoh. Terima kasih. Akan memperbaikinya
musicman523
1
@ musicman523 Saya baru saja menjelajah pertanyaan aktif dan melihat yang satu ini. Dan perhatikan bahwa Anda masih belum menambahkan kasus uji yang diminta.
Draco18s

Jawaban:

29

perakitan x86-64, 5 4 byte

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

Sebuah fungsi menggunakan konvensi pemanggilan C yang bitwise memutar argumennya menjadi 1 bit.

Anders Kaseorg
sumber
Sialan - Saya akan memposting persis ini - dilakukan dengan baik :)
Digital Trauma
12
assembly mengalahkan Jelly: o
Uriel
Bukankah ini dikalikan 2? Jika demikian, maka jawaban Pyth 2 byte saya mungkin menang
NoOneIsHere
@NoOneIsHere Tidak, ini bukan perkalian dengan 2. Perkalian dengan 2 mengirimkan setengah dari input di luar rentang yang diperlukan, dan jika Anda mengabaikan bit overflow di sebelah kiri, Anda telah mengurangi berat Hamming sebesar 1. Ini adalah bitwise rotasi , yang membawa bit overflow kembali dari kanan.
Anders Kaseorg
1
@DigitalTrauma GCC 4.9.0 dan kemudian cukup cerdas untuk mengkompilasi n << 1 | n >> 31menjadi rolbukan ror(menyimpan byte).
Anders Kaseorg
8

Python, 20 byte

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

Rotasi bitwise dibiarkan 1 bit.

Anders Kaseorg
sumber
6

MATL , 9 byte

32&B1YSXB

Secara melingkar menggeser representasi biner 32 digit satu langkah ke kanan.

Cobalah online!

Luis Mendo
sumber
6

Jelly , 10 8 byte

‘&~^^N&$

Tukar bit yang paling tidak signifikan dan tidak disetel.

Cobalah online!

Bagaimana itu bekerja

‘&~^^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
sumber
5

JavaScript (ES6), 35 31 byte

Mencari transisi bit pertama (0 → 1 atau 1 → 0) dan membalikkannya.

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

Demo

Rotasi bit, 14 byte

Jauh lebih pendek tapi kurang menyenangkan.

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

Demo

Arnauld
sumber
Operator bitwise JavaScript memberikan bilangan bulat bertanda 32-bit alih-alih tidak ditandatangani. Misalnya, f(2147483647)adalah -1073741825dan (n=>n>>>31|n<<1)(2147483647)sekarang -2.
Anders Kaseorg
2
Tidak apa-apa asalkan tidak ada lebih dari 32 bit.
musicman523
Bisakah Anda menambahkan penjelasan untuk yang pertama? Saya mencoba mempelajari Javascript, dan saya agak bingung bagaimana Anda memanggil f dengan k tidak ditentukan dan masih mendapatkan jawaban yang masuk akal!
musicman523
2
@ musicman523 Ini tip yang sesuai. Pada dasarnya, kawalnya diatur ke undefineddan kami mengambil keuntungan dari fakta yang ~undefinedsama -1.
Arnauld
@ musicman523 (Saya tidak menggunakan tip ini lagi dalam versi yang diperbarui. Tapi jangan ragu untuk bertanya apakah Anda memiliki pertanyaan lain tentang jawaban yang asli.)
Arnauld
4

Brain-Flak , 78 byte

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

Cobalah online!

Mengembalikan 2n jika n <2 ^ 31, dan 2n + 1-2 ^ 32 sebaliknya. Sayangnya, karena Brain-Flak tidak memiliki cara cepat untuk menentukan tanda suatu angka, program akan mati pada TIO jika inputnya berbeda dari 2 ^ 31 lebih dari sekitar 500000.

Penjelasan

Pertama, tekan -2 ^ 32 ke stack:

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

Kemudian, hitung output yang diinginkan:

      (({}){})                        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
sumber
3

dc, 10

?2~z31^*+p

Cobalah online .

Ini adalah implementasi aritmatika dari putaran kanan 32bit:

?           # 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
sumber
3

Java 8, 117 17 29 byte

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

+12 byte dengan mengubah intke long, karena intukuran maksimalnya adalah2³¹-1

100 89 byte disimpan dengan membuat port jawaban Python @AndersKaseorg yang luar biasa.

Coba di sini.

Output:

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)

Jawaban lama ( 117 118 byte):

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

+1 byte dengan mengubah intke long, karena intukuran maksimalnya adalah2³¹-1

Coba di sini.

Output:

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
sumber
2

Mathematica, 29 bytes

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

Try it at the Wolfram sandbox

Rotates left arithmetically: first multiply by 2, which possibly shifts the number out of range, then cut off the out-of-range digit with Mod[...,2^32] and add it back on the right with +Quotient[...,2^32].

(Mathematica does have a single builtin that gives the modulus and the quotient in one go, but it's QuotientRemainder, which is a bit of a golfing handicap…)

Not a tree
sumber
Mod 2^32-1? (4 more to go)
user202729
2

APL, 12 bytes

(2⊥32⍴1)|2×⊢

How?

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

R, 42 63 bytes

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

Shuffles the bits around randomly, but checks to make sure it didn't return the same number by chance.

BLT
sumber
1

Whitespace, 81 80 bytes

(1 byte saved thanks to @Ørjan Johansen reminding me dup is shorter than push 0)

   
 
 	
					 
    	 
	 		
	 
   	        
 
 	  
 
 	  
	   
  
   	 
	 	 	
 	

Try it online!

Basically implements a cyclic right bitshift using integer arithmetic. Pushing a large constant is expensive in Whitespace so we save some bytes by pushing 2^8 and squaring it twice. (Saves 1 byte over (2^16)^2 and 10 bytes over pushing 2^32 directly.)

Explanation

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
sumber
1
I think you can replace the second push 0 with a dup one command earlier.
Ørjan Johansen
You're right, I just finished adding shortcut syntax to my transpiler so I've been using it too much...
Ephphatha
0

Python 2.7, 89 bytes

Full Program:

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

Try it online!

Suggestions welcome! :)

Koishore Roy
sumber
That is not valid because it can by chance return the same number again.
Ørjan Johansen
0

Japt, 5 bytes

Ñ%3pH

Bitwise rotation, like most answers here.

Try it

Embodiment of Ignorance
sumber
0

Python 3, 45 bytes

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

Try it online!

movatica
sumber