Unkluge Bitoperationen

16

Ich spiele gerne Golf dc, bin aber manchmal frustriert, weil ich dckeine bitweisen Operationen habe.

Herausforderung

Geben Sie vier genannten Funktionen , die das Äquivalent der c bitweise Operationen implementieren &, |, ~und ^(bitweise AND, OR, NOT und XOR). Jede Funktion benötigt zwei Operanden ( ~nur einen), bei denen es sich um mindestens 32-Bit-Ganzzahlen ohne Vorzeichen handelt. Jede Funktion gibt eine ganze Zahl ohne Vorzeichen mit derselben Bitbreite wie die Operanden zurück.

Beschränkung

Sie dürfen nur Operationen verwenden, die von unterstützt werden dc. Diese sind:

  • + - * / Arithmetische Addition, Subtraktion, Multiplikation und Division
  • ~ modulo (oder divmod wenn deine Sprache es unterstützt)
  • ^ Potenzierung
  • | modulare Potenzierung
  • v Quadratwurzel
  • > >= == != <= < Standard-Gleichheits- / Ungleichheitsoperatoren
  • >> <<Bit-Shift-Operatoren. dchabe diese nicht, aber da sie in Bezug auf Division / Multiplikation durch Potenzen von 2 trivial implementiert sind, werde ich diese zulassen.

Kontrollstrukturen lassen dcsich mit (rekursiven) Makros und (in) Gleichheitsoperationen ungeschickt aufbauen. Sie können die in Ihrer Sprache integrierten Kontrollstrukturen verwenden.

Sie können auch logische Operatoren verwenden && || ! , obwohl diese in nicht direkt verfügbar sind dc.

Sie müssen nicht die Bit - Operatoren verwenden & , |, ~und ^oder alle Funktionen , die sie triviale implementieren.

Außerdem dürfen Sie keine eingebauten Basisumwandlungsoperatoren oder -funktionen verwenden.


Bitte geben Sie auch ein Testprogramm oder ein Online-Compiler-Snippet an (nicht im Golf-Score enthalten), um Ihre Antwort zu überprüfen.

Digitales Trauma
quelle
Können wir eine Funktion implementieren, die die gewünschte Operation als Parameter verwendet? Können wir als Ersatz für die Bitverschiebung auch durch 2 dividieren?
Xnor
@xnor Sie müssen 4 öffentliche Funktionen bereitstellen, die jeden der vier Operatoren implementieren. Möglicherweise verfügen Sie auch über allgemeine / helfer-private Methoden / Funktionen, die von allen vier öffentlichen Funktionen aufgerufen werden. Diese müssen jedoch alle im Golf-Score enthalten sein.
Digital Trauma
7
@xnor Sie und Sie müssen nur noch den Operator xnor implementieren ;-)
Digital Trauma
Kann ich eine Liste von vier anonymen Funktionen erstellen?
Xnor
@MariaTidalTug Was ist der effektive Unterschied zwischen dem Zurückgeben einer Liste mit vier Funktionen und dem manuellen Auswählen und Anwenden einer Funktion (wie nicht empfohlen) im Vergleich zu einer Funktion, die den Auswahlparameter akzeptiert und die Auswahl selbst ausführt (wie von Wolfhammer beantwortet)? Beide scheinen in ähnlicher Weise den Sinn von vier benannten Funktionen zu untergraben, da sie die Codegröße in den Benutzercode verlagern. Ich würde sogar behaupten, dass das erstere es stärker untergräbt, da der Benutzercode in diesem Fall wahrscheinlich komplexer ist als im letzteren Fall.
Runer112

Antworten:

4

C 134

Der C-Präprozessor ist ziemlich lustig zu missbrauchen. Grundsätzlich ist dieser Makro definiert die Funktionen 3, a, o, und x, für and, orundxor sind. Der einzige Unterschied im Algorithmus für diese Operationen besteht in den Kriterien zum Setzen des Bits im Ergebnis.

notist die Funktion n.

#define f(n,c)n(a,b){for(r=0,i=31;i+1;--i)if(((a>>i)%2+(b>>i)%2)c)r+=1<<i;return r;}
i,r;n(a){return 0xffffffff-a;}f(a,/2)f(o,)f(x,%2)

Tester-Programm (dauert lange, ich habe keine Zeit damit verbracht, es zu optimieren, aber es testet jeden möglichen Testfall, abgesehen von MAX_INT-bezogenen):

#define m_assert(expected, condition, actual)\
    if(!((expected) condition (actual)))\
        printf("assert fail @ line %i, expected: %x, actual %x, condition "#condition"\n", __LINE__, expected, actual);

int main()  {
    unsigned int j,k;
    for(j=0; j<0xffff; ++j)    {
        m_assert(~j, ==, n(j));
        for(k=0; k<0xffff; ++k)    {
            m_assert(j & k, ==, a(j,k));
            m_assert(j | k, ==, o(j,k));
            m_assert(j ^ k, ==, x(j,k));
        }
    }
Pseudonym117
quelle
1
Hoppla. habe das vergessen. repariert das jetzt.
Pseudonym117
4

ised 76 Bytes

ised hat auch nicht bitweise Operationen - in der Regel ärgerlich, aber jetzt gern gesehen, weil wir wirklich brauchen , um sie umzusetzen.

Funktionen werden in nummerierten Speicherplätzen gespeichert (keine ausführlichen Namen).

Konvertierung von und nach Binär:

@5{:x/2^[32]%2:};
@6{:x@:2^[32]:};

NICHT könnte sein, @1{:$6::{1-$5::x}:}aber es ist offensichtlich einfacher, nur zu subtrahieren:

@1{:2^32-x-1:};

ODER:

@2{:$6::{$5::{x_0}:+$5::{x_1}>0}:};

UND:

@3{:$6::{$5::{x_0}:*$5::{x_1}}:};

XOR:

@4{:$6::{$5::{x_0}:<>$5::{x_1}}:};

Dies würde uns auf 156 Bytes bringen (mit Zeilenumbrüchen und Semikolons). Ein Testcode wäre einfach (NICHT, ODER, UND, XOR nacheinander, gefunden unter den Namen $ 1, $ 2, $ 3, $ 4):

> $1::{6}
4294967289
> $2::{12 11}
15
> $3::{12 11}
8
> $4::{12 11}
7

Aber natürlich sind ODER und NICHT alles, was wir wirklich brauchen, und die Dinge können vereinfacht werden:

@1{:2^32-x-1:};
@2{:@+{2^U{?{$5::x}%32}}:};
@3{:${1 2 1}::x:};
@4{:$3::{$2::x${1 2}::x}:};
@5{:x/2^[32]%2:};

Das sind 109 Zeichen. Wenn Zeilenumbrüche und Semikolons übersprungen werden und etwas mehr Golf gespielt wird, haben wir 76 Zeichen:

@3{@1{:2^32-x-1:}@2{:@+{2^U{?{x/2^[32]%2}%32}}:}$1}@4{{:$2::x${1 2}::x:}$3};
orion
quelle
1

Nim (537) (490)

Nim Compiler 0.10.2

Ich habe nach einem Grund gesucht, um nim zu lernen, also können wir loslegen.

Für Code-Golf habe ich variable Parameter und implizite Renditen genutzt. Die variablen Parameter sind laut Dokumentation weniger stapeleffizient. Persönlich finde ich die impliziten Rückgaben schwerer zu lesen und würde sie wahrscheinlich nur in trivialen Verfahren verwenden.

Die Algorithmen sind einfach genug. Für alle Operationen außer NOT vergleichen wir jedes Bit und vergleichen sie manuell mit unserer erwarteten Wahrheitstabelle. Stellen Sie jedes Bit in unserer Ausgabevariable nach Bedarf ein. In Nim ist result der implizite Rückgabewert.

Ich war mir nicht sicher, ob wir das eingebaute ODER und UND verwenden dürfen, um zwei boolesche Bedingungen zu bestätigen, damit die notZero-Prozedur an ihre Stelle tritt.

proc s(x, y, b: var int)=
  x = x div 2
  y = y div 2
  b *= 2

proc n(x: var int): int =
  return -(x+1)

proc a(x, y: var int): int =
  var b = 1
  while x > 0 and y > 0:
    if (x mod 2  + y mod 2) == 2:
      result += b

    s(x,y,b)

proc o(x, y: var int): int =
  var b = 1
  while x + y > 0:
    if (x mod 2 + y mod 2) >= 1:
      result += b

    s(x,y,b)

proc r(x, y: var int): int =
  var b = 1
  while x + y > 0:
    if (x mod 2 + y mod 2) == 1:
      result += b

    s(x,y,b)

Immer noch auf der Suche nach einer besseren Methode ...

Hier ist die nicht gequetschte Version sowie ein vollständiger Testgurt, der auf Ihrem eigenen Computer ausgeführt werden kann.
Wenn Sie nur ein paar Eingaben ausführen möchten, finden Sie hier den Testfall lite .

cory.todd
quelle
@MariaTidalTug danke für die Klärung!
cory.todd
Das kann ich nicht reproduzieren. Befindet sich Ihr Rechner im Base-16-Modus?
cory.todd
Ich habe ein Testgeschirr ähnlich dem von pseudonym117 hinzugefügt.
cory.todd
1

CJam, 71 Bytes

{:F;0{:R;2md@2md@+F~!2I#*R+}64fI\;\;}:B{"2-"B}:A{'!B}:O{0SB}:N{'(B}:X];

Erläuterung

"B : UInt64 UInt64 String -> UInt64
 Computes a bitwise operation on the two given unsigned integers. The operation
 is defined by the logical inverse of the result of evaluating the given string
 given the sum of two input bits.";
{
  :F;             "Save the operation string.";
  0               "Initialize the result to 0.";
  {               "For I from 0 through 63:";
    :R;             "Save the result.";
    2md@2md@        "Divide each input by 2 and collect the remainders as the
                     next pair of bits to process.";
    +F~!            "Compute the logical inverse of the result of evaluating
                     the operation string given the sum of the two bits.";
    2I#*            "Adjust the resulting bit to be in the correct output
                     position by multiplying it by 2^I.";
    R+              "Add the location-adjusted bit to the result.";
  }64fI
  \;\;            "Clean up.";
}:B

"A : UInt64 UInt64 -> UInt64
 Computes the bitwise AND of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !((bit_in_1 + bit_in_2) - 2)";
{"2-"B}:A

"O : UInt64 UInt64 -> UInt64
 Computes the bitwise OR of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !(!(bit_in_1 + bit_in_2))";
{'!B}:O

"N : UInt64 -> UInt64
 Computes the bitwise NOT of the given unsigned integer.
 This is done by passing the input and 0 along to B with an operation such that:
   bit_out = !((bit_in + 0))";
{0SB}:N

"X : UInt64 UInt64 -> UInt64
 Computes the bitwise XOR of the two given unsigned integers.
 This is done by passing the inputs along to B with an operation such that:
   bit_out = !((bit_in_1 + bit_in_2) - 1)";
{'(B}:X

];              "Clean up.";

Testsuite

Dieser Code testet die Ausführung jeder meiner und / oder nicht und xor-Funktionen 100-mal mit gleichmäßig verteilten 64-Bit-Eingaben ohne Vorzeichen und vergleicht das Ergebnis mit dem Ergebnis des eingebauten Operators. Aufgrund der unbeabsichtigten Verwendung des eval-Operators ist dies recht langsam und kann mit dem Online-Dolmetscher bis zu einer Minute dauern. Aber wenn alles gut geht, sollte die Ausführung ohne Ausgabe enden, da alle gefundenen Unstimmigkeiten gedruckt werden.

N:L;
{:F;0{:R;2md@2md@+F~!2I#*R+}64fI\;\;}:B{"2-"B}:A{'!B}:O{0SB}:N{'(B}:X];
{;Y32#__mr*\mr+}2e2%2/{~:U;:V;"A&O|X^"2/{[{US@SV" = "UV5$~L}/9$2$={];}{]oLo}?}/"N~"[{U" = "U3$~Y64#(&L}/6$2$={];}{]oLo}?}/
Runer112
quelle
0

JavaScript 294 267

Konnte mit den Vorschlägen von @ AlexA. Und @ kennytm ein paar Bytes mehr abschneiden.

Funktionen:

B=(n,m,t)=>{for(var p=4294967296,y=0;p>=1;p/=2)y+=t=='x'&&(n>=p||m>=p)&& !(n>=p&&m>=p)?p:0,y+=t=='a'&&n>=p&&m>=p?p:0,y+=t=='o'&&(n>=p||m>=p)?p:0,n-=n>=p?p:0,m-=m>=p?p:0
return y}
N=(n)=>{return 4294967295-n}
A=(n,m)=>B(n,m,'a')
O=(n,m)=>B(n,m,'o')
X=(n,m)=>B(n,m,'x')

Beispiel:

var n = 300;
var m = 256;
console.log(X(n,m) + ", " + (n ^ m));
console.log(O(n,m) + ", " + (n | m));
console.log(A(n,m) + ", " + (n & m));
console.log(N(n) + ", " + (~n>>>0));
console.log(N(m) + ", " + (~m>>>0));

Ausgabe:

44, 44
300, 300
256, 256
4294966995, 4294966995
4294967039, 4294967039
Wolfhammer
quelle
2
Sie müssen vier öffentliche Funktionen bereitstellen - jeweils eine für AND, OR. NICHT und XOR. (Möglicherweise verfügen Sie auch über allgemeine / helper private Methoden / Funktionen, die von allen vier öffentlichen Funktionen aufgerufen werden.) Auch fehlen Sie das nicht - wahrscheinlich die einfachste von allen von diesen zu tun
Digital -
Vielen Dank @AlexA. Ich habe die Bytes hinzugefügt und noch mehr Golf gespielt.
Wolfhammer
Sie können den Raum nach verlieren forund ersetzen function B(n,m,t)mit B=(n,m,t)=>. Ebenso für die anderen Funktionen.
Alex A.
① Sie könnten 4*(1<<30)für 4294967296 und -1>>>0für 4294967295 verwenden. ② ist das hier varwirklich notwendig? ③ du könntest schreiben (n,m)=>B(n,m,'a')anstatt(n,m)=>{return B(n,m,'a')}
kennytm