Lubię grać w golfa dc, ale czasami jestem sfrustrowany, ponieważ dcnie mam operacji bitowych.

Wyzwanie

Zapewnić cztery nazwach funkcji, które implementują odpowiednik operacji c bitowe &, |, ~oraz ^(bitowe AND, OR, NOT i XOR). Każda funkcja przyjmuje dwa operandy ( ~zajmuje tylko jeden), które są co najmniej 32-bitowymi liczbami całkowitymi bez znaku. Każda funkcja zwróci liczbę całkowitą bez znaku o tej samej szerokości bitów co argumenty.

Ograniczenie

Możesz używać tylko operacji obsługiwanych przez dc. To są:

• + - * / Dodawanie, odejmowanie, mnożenie i dzielenie arytmetyczne
• ~ modulo (lub divmod, jeśli Twój język to obsługuje)
• ^ potęgowanie
• | modułowe potęgowanie
• v pierwiastek kwadratowy
• > >= == != <= < standardowe operatory równości / nierówności
• >> <<operatorzy zmiany bitów. dcnie ma ich, ale ponieważ są one trywialnie realizowane w kategoriach dzielenia / mnożenia przez potęgi 2, pozwolę na to.

Struktury kontrolne mogą dcbyć niezgrabnie budowane przy użyciu (rekurencyjnych) makr i (nie) operacji równości. Możesz używać dowolnych wbudowanych struktur kontrolnych, które posiada Twój język.

Możesz także użyć operatorów logicznych && || ! , nawet jeśli nie są one bezpośrednio dostępne w dc.

Ci nie muszą stosować operatory bitowe & , |, ~i ^ani żadnych funkcji, które implementują je trywialnie.

Ponadto nie wolno używać wbudowanych operatorów lub funkcji konwersji ciągów bazowych.

Zastanów się też nad udostępnieniem programu testowego lub fragmentu kompilatora online (nieuwzględnionego w wynikach golfa), aby pomóc w weryfikacji odpowiedzi.

C 134

Preprocesor C jest przyjemny w nadużywaniu. Zasadniczo makro 3 określa funkcje a, oi xna and, ori xorodpowiednio. Jedyną różnicą w algorytmie dla tych operacji są kryteria ustawienia bitu w wyniku.

notjest funkcją 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)

Program testowy (zajmuje dużo czasu, wcale nie spędziłem czasu na jego optymalizowaniu, ale testuje każdy możliwy przypadek testowy, oprócz tych związanych z MAX_INT):

#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));
        }
    }

ised 76 bajtów

ised również nie ma operacji bitowych - zwykle denerwujących, ale teraz mile widzianych, ponieważ naprawdę potrzebujemy je wdrożyć.

Funkcje będą przechowywane w ponumerowanych gniazdach pamięci (bez pełnych nazw).

Konwersja do iz pliku binarnego:

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

NIE może być, @1{:$6::{1-$5::x}:}ale oczywiście łatwiej jest po prostu odjąć:

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

LUB:

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

I:

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

XOR:

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

To doprowadziłoby nas do 156 bajtów (z nowymi liniami i średnikami). Kod testowy to po prostu (NOT, OR, AND, XOR z rzędu, znaleziony pod nazwami 1 $, 2 $, 3 $, 4 $):

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

Ale oczywiście LUB i NIE to wszystko, czego naprawdę potrzebujemy, a sprawy można uprościć:

@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:};

To 109 znaków. Kiedy znaki nowej linii i średniki są pomijane, a przy odrobinie golfa mamy 76 znaków:

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

Nim (537) (490)

Nim Compiler 0.10.2

Szukałem powodu, żeby się go nauczyć, więc zaczynamy.

Do gry w golfa wykorzystałem zmienne parametry i niejawne zwroty. Zmienne parametry, zgodnie z dokumentacją, są mniej wydajne w stosie. Osobiście uważam, że ukryte zwroty są trudniejsze do odczytania i prawdopodobnie użyłbym ich tylko w trywialnych procedurach.

Jeśli chodzi o algorytmy, są one dość proste. Dla wszystkich operacji oprócz NIE porównujemy każdy bit i ręcznie porównujemy je z naszą oczekiwaną tabelą prawdy. Ustaw każdy bit zgodnie z potrzebami po drodze w naszej zmiennej wyjściowej. W Nim wynikiem jest niejawna wartość zwracana.

Nie byłem pewien, czy wolno nam używać wbudowanego OR i AND do zapewnienia dwóch warunków boolowskich, więc na ich miejsce została zastosowana procedura notZero.

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)

Wciąż szukam lepszej metody ...

Oto nieskomplikowana wersja plus pełna uprząż testowa do uruchomienia na własnej maszynie.
Jeśli chcesz po prostu uruchomić kilka wejść, oto lite przypadku testowego .

CJam, 71 bajtów

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

Wyjaśnienie

"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.";

Zestaw testowy

Ten kod testuje 100-krotnie każdą z moich funkcji i, lub nie, i xor z równomiernie rozmieszczonymi 64-bitowymi niepodpisanymi wejściami i porównuje wynik z wynikiem wygenerowanym przez wbudowanego operatora. Z powodu nieuzasadnionego korzystania z operatora eval jest on dość wolny i może zająć około minuty z tłumaczem online. Ale jeśli wszystko pójdzie dobrze, wykonanie powinno zakończyć się bez wyjścia, ponieważ drukowane są wszelkie znalezione rozbieżności.

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}?}/

JavaScript 294 267

Był w stanie zgolić jeszcze kilka bajtów dzięki sugestiom @ AlexA. i @ kennytm.

Funkcje:

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

przykład:

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

wynik:

44, 44
300, 300
256, 256
4294966995, 4294966995
4294967039, 4294967039