Operasi bit yang tidak bijaksana

16

Saya suka bermain golf dc, tapi kadang-kadang saya frustrasi karena dctidak memiliki operasi bitwise.

Tantangan

Menyediakan empat fungsi bernama yang menerapkan setara dengan operasi c bitwise &, |, ~dan ^(bitwise AND, OR, NOT dan XOR). Setiap fungsi akan mengambil dua operan ( ~hanya satu) yang setidaknya merupakan bilangan bulat 32-bit yang tidak ditandatangani. Setiap fungsi akan mengembalikan bilangan bulat tanpa tanda dengan lebar bit yang sama dengan operan.

Larangan

Anda hanya dapat menggunakan operasi yang didukung oleh dc. Ini adalah:

  • + - * / Penambahan aritmatika, pengurangan, perkalian dan pembagian
  • ~ modulo (atau divmod jika bahasa Anda mendukungnya)
  • ^ eksponensial
  • | eksponensial modular
  • v akar pangkat dua
  • > >= == != <= < operator kesetaraan / ketidakmerataan standar
  • >> <<operator bit shift. dctidak memiliki ini, tetapi karena mereka sepele diimplementasikan dalam hal pembagian / perkalian dengan kekuatan 2, maka saya akan mengizinkan ini.

Struktur kontrol di dcsaya dibuat dengan canggung menggunakan makro (rekursif) dan operasi kesetaraan (dalam). Anda dapat menggunakan struktur kontrol bawaan apa saja yang dimiliki bahasa Anda.

Anda juga dapat menggunakan operator logis && || ! , meskipun ini tidak tersedia secara langsung di dc.

Anda tidak harus menggunakan operator bitwise & , |, ~dan ^atau fungsi yang sepele menerapkannya.

Selain itu, Anda tidak boleh menggunakan operator atau fungsi konversi-dalam-string-basis-bawaan.


Harap pertimbangkan untuk memberikan program pengujian atau cuplikan kompiler online (tidak termasuk dalam skor golf) untuk membantu memverifikasi jawaban Anda.

digital Trauma
sumber
Bisakah kita menerapkan satu fungsi yang mengambil operasi yang diinginkan sebagai parameter? Juga, dapatkah kita membagi integer dengan 2 sebagai pengganti bit-shift?
xnor
@ xnor Anda harus menyediakan 4 fungsi publik yang mengimplementasikan masing-masing dari empat operator. Anda mungkin juga memiliki metode / fungsi pribadi umum / pembantu yang dipanggil oleh keempat fungsi publik, tetapi ini semua harus dimasukkan dalam skor golf.
Trauma Digital
7
@ xnor Anda dan Anda hanya harus mengimplementasikan operator xnor ;-)
Digital Trauma
Bisakah saya membuat daftar empat fungsi anonim?
xnor
@MariaTidalTug Apa perbedaan efektif antara mengembalikan daftar empat fungsi dan secara manual memilih dan menerapkan satu (seperti yang disarankan xnor) dibandingkan memiliki satu fungsi yang menerima parameter pemilihan dan melakukan pemilihan itu sendiri (seperti jawaban wolfhammer)? Mereka berdua tampaknya juga merusak titik memiliki empat fungsi bernama, karena mereka menurunkan ukuran kode ke kode pengguna. Saya bahkan berpendapat bahwa yang pertama lebih merusak, karena kode pengguna mungkin lebih kompleks dalam kasus itu daripada dalam kasus terakhir.
Runer112

Jawaban:

4

C, 134

Preprosesor C cukup menyenangkan untuk disalahgunakan. Pada dasarnya makro ini mendefinisikan 3 fungsi, a, o, dan x, untuk and, ordan xormasing-masing. Satu-satunya perbedaan dalam algoritma untuk operasi ini adalah kriteria untuk mengatur bit dalam hasilnya.

notadalah fungsinya 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 penguji (membutuhkan waktu lama, saya tidak menghabiskan waktu untuk mengoptimalkannya sama sekali, tetapi ia menguji setiap test case yang mungkin, selain MAX_INT yang terkait):

#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
sumber
1
oops. lupa tentang itu. memperbaikinya sekarang.
pseudonym117
4

ised 76 byte

ised juga tidak memiliki operasi bitwise - biasanya menjengkelkan, tapi sekarang selamat datang, karena kita benar - benar perlu mengimplementasikannya.

Fungsi akan disimpan dalam slot memori bernomor (tidak ada nama verbose).

Konversi ke dan dari biner:

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

TIDAK bisa @1{:$6::{1-$5::x}:}tetapi jelas lebih mudah untuk mengurangi:

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

ATAU:

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

DAN:

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

XOR:

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

Ini akan membawa kita ke 156 byte (dengan baris baru dan titik koma). Kode uji hanya akan menjadi (BUKAN, ATAU, DAN, XOR berturut-turut, ditemukan dengan nama $ 1, $ 2, $ 3, $ 4):

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

Tapi tentu saja OR dan NOT adalah yang benar-benar kita butuhkan dan hal-hal yang dapat disederhanakan:

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

Itu 109 karakter. Saat baris baru dan titik koma dilewati, dan dengan sedikit lebih banyak bermain golf, kami memiliki 76 karakter:

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

Nim (537) (490)

Nim Compiler 0.10.2

Saya telah mencari alasan untuk belajar nim jadi di sini kita mulai.

Untuk golf kode, saya telah meningkatkan parameter variabel dan pengembalian implisit. Parameter variabel, per dokumentasi kurang efisien. Secara pribadi, saya menemukan pengembalian implisit lebih sulit untuk dibaca dan mungkin hanya akan menggunakannya dalam prosedur sepele.

Adapun algoritma, mereka cukup sederhana. Untuk semua operasi kecuali TIDAK, kami membandingkan setiap bit dan membandingkannya secara manual dengan tabel kebenaran yang kami harapkan. Atur setiap bit sesuai kebutuhan di dalam variabel output kami. Dalam Nim, hasilnya adalah nilai balik implisit.

Saya tidak yakin apakah kami diizinkan menggunakan built-in OR dan AND untuk menyatakan dua kondisi boolean sehingga prosedur notZero diletakkan di tempatnya.

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)

Masih mencari metode yang lebih baik ...

Ini adalah versi non-squished plus harness uji lengkap untuk dijalankan di mesin Anda sendiri.
Jika Anda hanya ingin menjalankan beberapa input, berikut ini adalah test case lite .

cory.todd
sumber
@MariaTidalTug terima kasih telah menjelaskan!
cory.todd
Saya tidak bisa mereproduksi itu. Apakah kalkulator Anda dalam mode base-16?
cory.todd
Saya menambahkan test harness mirip dengan nama samaran117.
cory.todd
1

CJam, 71 byte

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

Penjelasan

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

Suite uji

Kode ini menguji setiap fungsi saya dan, atau, tidak, dan xor yang 100 kali berfungsi dengan input unsigned 64-bit yang terdistribusi secara merata dan membandingkan hasilnya dengan yang dihasilkan oleh operator bawaan. Karena penggunaan operator eval yang serampangan, itu sangat lambat dan mungkin memakan waktu sekitar satu menit dengan penerjemah online. Tetapi jika semuanya berjalan dengan baik, eksekusi harus berakhir tanpa output, karena setiap perbedaan yang ditemukan dicetak.

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

JavaScript 294 267

Mampu mencukur beberapa byte lagi dengan saran @ AlexA. Dan @ kennytm.

Fungsi:

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

contoh:

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

keluaran:

44, 44
300, 300
256, 256
4294966995, 4294966995
4294967039, 4294967039
wolfhammer
sumber
2
Anda perlu menyediakan empat fungsi publik - masing-masing untuk AND, OR. BUKAN dan XOR. (Anda mungkin juga memiliki metode / fungsi pribadi umum / pembantu yang dipanggil oleh keempat fungsi publik). Juga, Anda melewatkan TIDAK - mungkin yang paling mudah untuk dilakukan
Digital Trauma
Terima kasih @AlexA. Saya telah menambahkan byte dan memutarnya lagi.
wolfhammer
Anda dapat kehilangan ruang setelah fordan mengganti function B(n,m,t)dengan B=(n,m,t)=>. Begitu juga untuk fungsi lainnya.
Alex A.
① Anda bisa menggunakan 4*(1<<30)untuk 4294967296 dan -1>>>0untuk 4294967295. ② apakah yang varbenar - benar diperlukan di sini? ③ Anda bisa menulis (n,m)=>B(n,m,'a')alih-alih(n,m)=>{return B(n,m,'a')}
kennytm