Niemądre operacje bitowe

16

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.

Cyfrowa trauma
źródło
Czy możemy wdrożyć jedną funkcję, która przyjmuje żądaną operację jako parametr? Czy możemy również podzielić liczbę całkowitą przez 2 jako stand-in dla przesunięcia bitów?
xnor
@xnor Musisz udostępnić 4 funkcje publiczne, które implementują każdy z czterech operatorów. Możesz także mieć wspólne / pomocnicze prywatne metody / funkcje, które są wywoływane przez wszystkie cztery funkcje publiczne, ale wszystkie one muszą zostać uwzględnione w wyniku golfa.
Cyfrowa trauma
7
@xnor Ty i tylko Ty musisz wdrożyć operator xnor ;-)
Digital Trauma
Czy mogę stworzyć listę czterech anonimowych funkcji?
xnor
@MariaTidalTug Jaka jest efektywna różnica między zwróceniem listy czterech funkcji a ręcznym wybraniem i zastosowaniem jednej (zgodnie z sugestią xnor) w porównaniu z posiadaniem jednej funkcji, która akceptuje parametr selekcji i dokonuje samej selekcji (jak odpowiedział wolfhammer)? Oba wydają się podobnie podważać sens posiadania czterech nazwanych funkcji, ponieważ przenoszą rozmiar kodu na kod użytkownika. Twierdziłbym nawet, że ten pierwszy bardziej go podważa, ponieważ kod użytkownika jest prawdopodobnie bardziej złożony w tym przypadku niż w drugim przypadku.
Runer112,

Odpowiedzi:

4

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));
        }
    }
pseudonim117
źródło
1
ups. zapomniałem o tym. naprawiłem to teraz.
pseudonim
4

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};
orion
źródło
1

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 .

cory.todd
źródło
@MariaTidalTug dzięki za wyjaśnienie!
cory.todd
Nie mogę tego odtworzyć. Czy twój kalkulator działa w trybie base-16?
cory.todd,
Dodałem uprząż testową podobną do pseudonimu 117.
cory.todd,
1

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}?}/
Runer112
źródło
0

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
wolfhammer
źródło
2
Musisz zapewnić cztery funkcje publiczne - po jednej dla AND, OR. NIE i XOR. (Możesz także mieć wspólne / pomocnicze prywatne metody / funkcje wywoływane przez wszystkie cztery funkcje publiczne). Brakuje również NIE - prawdopodobnie najłatwiejszego z nich do zrobienia
Cyfrowej Traumy
Dzięki @AlexA. Dodałem bajty i jeszcze trochę grałem w golfa.
wolfhammer,
Możesz stracić przestrzeń po fori zastąpić function B(n,m,t)z B=(n,m,t)=>. Podobnie w przypadku innych funkcji.
Alex A.
Could Możesz użyć 4*(1<<30)dla 4294967296 i-1>>>0 dla 4294967295. ② jest varnaprawdę konieczne tutaj? (n,m)=>B(n,m,'a')(n,m)=>{return B(n,m,'a')}
Could