Unterschiedliche Anzahl, gleiches Gewicht

22

Hintergrund

Das Hamming-Gewicht einer Ganzzahl ist die Anzahl der Einsen in ihrer Binärdarstellung. Für diese Herausforderung werden Ganzzahlen mit 32 Bit dargestellt und sie sind vorzeichenlos.

Herausforderung

Geben Sie bei einer Ganzzahl zwischen 0 und 2 ^ 32-1 (nicht inklusive) eine andere Ganzzahl in demselben Bereich und mit demselben Hamming-Gewicht aus.

Beispiele

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)

Wertung

Das ist , also gewinnt die Lösung mit den wenigsten Bytes in jeder Sprache.

musicman523
quelle
2
Ich würde vorschlagen, eine ungerade Zahl zwischen 2 ^ 31 + 1 und 2 ^ 32-3 hinzuzufügen, da einige Antworten diesbezüglich fehlschlagen.
Ørjan Johansen
Verbunden.
Martin Ender
Da Sie gerade hinzugefügt haben 2^31+2, wiederhole ich, dass ich eine ungerade Zahl gesagt habe . Die fraglichen Antworten sind nur fehlgeschlagen, wenn sowohl das höchste als auch das niedrigste Bit vorhanden sind 1.
Ørjan Johansen
Ich bin ein Narr. Vielen Dank. Wird das beheben
musicman523
1
@ musicman523 Ich habe gerade aktive Fragen durchsucht und diese gesehen. Und festgestellt, dass Sie die angeforderten Testfälle noch nicht hinzugefügt haben.
Draco18s

Antworten:

29

x86-64-Assembly, 5 4 Bytes

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

Eine Funktion, die die C-Aufrufkonvention verwendet und deren Argument bitweise um 1 Bit nach links dreht.

Anders Kaseorg
quelle
Verdammt - ich wollte genau das posten - gut gemacht :)
Digitales Trauma
12
Versammlung schlägt Jelly: o
Uriel
Ist das nicht multipliziert mit 2? Wenn ja, dann gewinnt wahrscheinlich meine 2-Byte-Pyth-Antwort
NoOneIsHere
@NoOneIsHere Nein, dies ist keine Multiplikation mit 2. Die Multiplikation mit 2 sendet die Hälfte der Eingänge außerhalb des erforderlichen Bereichs. Wenn Sie das Überlaufbit links ignorieren, haben Sie das Hamming-Gewicht um 1 verringert. Dies ist ein bitweises Ergebnis Drehung , die das Überlaufbit von rechts zurückbringt.
Anders Kaseorg
1
@DigitalTrauma GCC 4.9.0 und höher sind intelligent genug, um kompiliert n << 1 | n >> 31zu werden, rolanstatt ror(ein Byte zu speichern).
Anders Kaseorg
8

Python, 20 Bytes

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

Bitweise Drehung um 1 Bit nach links.

Anders Kaseorg
quelle
6

Gelee , 10 8 Bytes

‘&~^^N&$

Vertauscht das niedrigstwertige gesetzte und nicht gesetzte Bit.

Probieren Sie es online!

Wie es funktioniert

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

JavaScript (ES6), 35-31 Byte

Sucht nach dem ersten Bitübergang (0 → 1 oder 1 → 0) und invertiert ihn.

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

Demo

Bitrotation, 14 Bytes

Viel kürzer, aber weniger Spaß.

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

Demo

Arnauld
quelle
Die bitweisen JavaScript-Operatoren geben 32-Bit-Ganzzahlen mit und nicht ohne Vorzeichen an. Zum Beispiel f(2147483647)ist -1073741825und (n=>n>>>31|n<<1)(2147483647)ist -2.
Anders Kaseorg
2
Es ist in Ordnung, solange es nicht mehr als 32 Bits gibt.
musicman523
Können Sie eine Erklärung für die erste hinzufügen? Ich versuche Javascript zu lernen und bin ein bisschen ratlos, wie Sie f mit k undefined aufrufen und trotzdem eine vernünftige Antwort erhalten!
musicman523
2
@ musicman523 Hier ist der entsprechende Tipp. Grundsätzlich kist zunächst festgelegt, undefinedund wir nutzen die Tatsache, dass ~undefinedgleich ist -1.
Arnauld
@ musicman523 (Ich verwende diesen Tipp in der aktualisierten Version nicht mehr. Aber zögern Sie nicht zu fragen, ob Sie weitere Fragen zur ursprünglichen Antwort haben.)
Arnauld
4

Gehirn-Flak , 78 Bytes

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

Probieren Sie es online!

Gibt 2n zurück, wenn n <2 ^ 31, andernfalls 2n + 1-2 ^ 32. Da Brain-Flak das Vorzeichen einer Zahl nicht schnell ermitteln kann, tritt bei TIO ein Timeout des Programms auf, wenn die Eingabe um mehr als 500000 von 2 ^ 31 abweicht.

Erläuterung

Schieben Sie zuerst -2 ^ 32 auf den Stapel:

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

Berechnen Sie dann die gewünschte Ausgabe:

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

dc, 10

?2~z31^*+p

Probieren Sie es online aus .

Dies ist eine arithmetische Implementierung einer 32-Bit-Rechtsdrehung:

?           # 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
Digitales Trauma
quelle
3

Java 8, 117 17 29 Bytes

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

+12 Bytes durch Ändern intauf long, weil intdie maximale Größe ist2³¹-1

Durch das Erstellen eines Ports von @AndersKaseorgs erstaunlicher Python-Antwort werden 100 bis 89 Byte gespart .

Probieren Sie es hier aus.

Ausgänge:

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)

Alte Antwort ( 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 durch Ändern intauf long, da intdie maximale Größe ist2³¹-1

Probieren Sie es hier aus.

Ausgänge:

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

Mathematica, 29 Bytes

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

Probieren Sie es in der Wolfram Sandbox aus

Dreht rechnerisch nach links: Zuerst mit 2 multiplizieren, wodurch möglicherweise die Zahl außerhalb des Bereichs verschoben wird, dann die außerhalb des Bereichs liegende Ziffer mit abschneiden Mod[...,2^32]und mit wieder rechts addieren +Quotient[...,2^32].

(Mathematica hat eine einzige Funktion, die den Modul und den Quotienten in einem Zug angibt, aber es QuotientRemainderist eine Art Golf-Handicap.)

Kein Baum
quelle
Mod 2 ^ 32-1? (Noch 4)
user202729
2

APL, 12 Bytes

(2⊥32⍴1)|2×⊢

Wie?

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

R, 42 63 Bytes

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

Mischt die Bits nach dem Zufallsprinzip, überprüft jedoch, ob nicht zufällig dieselbe Zahl zurückgegeben wird.

BLT
quelle
1

Leerzeichen , 81 80 Bytes

(1 Byte gespart dank @ Ørjan Johansen, der mich daran erinnert, dass dup kürzer ist als Push 0)

   
 
 	
					 
    	 
	 		
	 
   	        
 
 	  
 
 	  
	   
  
   	 
	 	 	
 	

Probieren Sie es online!

Implementiert grundsätzlich eine zyklische Rechts-Bitverschiebung unter Verwendung einer Ganzzahl-Arithmetik. Das Pushen einer großen Konstante ist in Whitespace teuer, daher sparen wir einige Bytes, indem wir 2 ^ 8 drücken und zweimal quadrieren. (Speichert 1 Byte über (2 ^ 16) ^ 2 und 10 Byte über das direkte Drücken von 2 ^ 32.)

Erläuterung

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
quelle
1
Ich denke, Sie können die Sekunde push 0durch einen dupEin-Befehl früher ersetzen .
Ørjan Johansen
Sie haben Recht, ich habe gerade die Abkürzungssyntax zu meinem Transpiler hinzugefügt, also habe ich sie zu oft verwendet ...
Ephphatha
0

Python 2.7, 89 Bytes

Volles Programm:

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

Probieren Sie es online!

Vorschläge willkommen! :)

Koishore Roy
quelle
Das ist nicht gültig, da es zufällig wieder dieselbe Nummer zurückgeben kann.
Ørjan Johansen
0

Japt , 5 Bytes

Ñ%3pH

Bitweise Drehung, wie die meisten Antworten hier.

Versuch es

Verkörperung der Ignoranz
quelle