Tantangan
Menerapkan fungsi yang menerima dua bilangan bulat yang nilainya berkisar antara 0 - 255 dan mengembalikan jumlah bilangan bulat itu mod 256. Anda hanya dapat menggunakan negasi bitwise (~), bitwise atau (|), operator pemindahan bit (>>, <<) , dan penugasan (=).
Hal-hal yang tidak dapat Anda gunakan termasuk (tetapi tidak terbatas pada)
- Penambahan, pengurangan, penggandaan, dan pembagian
- Loop
- Pernyataan bersyarat
- Panggilan fungsi
Penggunaan paling sedikit dari operasi biner atau, negasi biner, dan bit shift menang . Dalam hal seri, solusi yang paling populer menang. Seperti biasa, celah standar berlaku.
Berikut adalah contoh dari penambah 2-bit yang sederhana. Ia menggunakan 77 negasi biner, 28 bit biner, dan 2 bit-shift untuk skor total 107 (ini dapat dilihat dengan menjalankan preprosesor C bersama gcc -E
). Itu bisa dibuat jauh lebih efisien dengan menghapus #define
dan menyederhanakan ekspresi yang dihasilkan, tetapi saya meninggalkannya untuk kejelasan.
#include <stdio.h>
#define and(a, b) (~((~a)|(~b)))
#define xor(a, b) (and(~a,b) | and(a,~b))
int adder(int a, int b)
{
int x, carry;
x = xor(and(a, 1), and(b, 1));
carry = and(and(a, 1), and(b, 1));
carry = xor(xor(and(a, 2), and(b, 2)), (carry << 1));
x = x | carry;
return x;
}
int main(int argc, char **argv)
{
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
if (adder(i, j) != (i + j) % 4) {
printf("Failed on %d + %d = %d\n", i, j, adder(i, j));
}
}
}
}
Perbarui: Menambahkan contoh dan mengubah kriteria penilaian
Jawaban:
Python, 36 operasi
Metode yang logaritmik pada parameter "8"!
Idenya adalah untuk mencari tahu indeks mana yang meluap dan menyebabkan terbawa. Awalnya, ini hanya tempat-tempat di mana kedua
a
anddb
memiliki1
. Tetapi karena bit yang dibawa dapat menyebabkan overlows lebih lanjut, ini perlu ditentukan secara iteratif.Daripada meluap setiap indeks ke yang berikutnya, kami mempercepat proses dengan memindahkan 1 indeks, lalu 2 indeks, lalu 4 indeks, memastikan untuk mengingat tempat-tempat di mana terjadi overflow (H) dan di mana overflow tidak dapat terjadi lagi (K ).
Solusi iteratif yang lebih sederhana dengan 47 operasi:
Test rig, untuk siapa saja yang ingin menyalinnya.
sumber
C - 0
Memang menggunakan operator di luar ~, |, >>, <<, dan =, tapi saya melihat solusi menggunakan operator casting dan koma, jadi saya kira aturannya tidak terlalu ketat asalkan tidak menggunakan operator terlarang.
sumber
python, skor =
8380Buka gulungannya. Ini 10 ops per loop kali 7 loop, 7 untuk xor terakhir, dan 3 untuk menekan bit ke-9 di akhir.
Menerapkan persamaan
x+y = x^y + 2*(x&y)
dengan mengulanginya 8 kali. Setiap kali ada satu lagi nol bit di bagian bawahy
.sumber
C, Nilai:
7760Golf hanya untuk itu,
206169131 byte:Diperluas:
Pada dasarnya solusi yang sama (matematis) yang muncul dengan
@KeithRandall@JuanICarrano, tetapi mengambil keuntungan dari kemampuan C untuk bermain cepat dan longgar dengan tipe variabel dan pointer untuk menghapus semuanya setelah 8 bit pertama tanpa menggunakan operator lagi.Bergantung pada keasrian mesin dan ukuran () int dan char, tetapi harus dapat diangkut ke sebagian besar aplikasi spesifik mesin dengan matematika pointer yang tepat.
EDIT: Ini adalah tantangan yang C (atau bahasa tingkat rendah lainnya) akan memiliki keunggulan di - kecuali seseorang datang dengan algoritma yang tidak harus dilakukan.
sumber
unsigned char
. Lebih bersih dan lebih portabel.unsigned
tidak datang secara alami kepada saya dalam kode golf. Anda tentu saja benar - diperbarui.Python - Skor
6664Ini adalah persamaan untuk penambah riak. C adalah carry. Itu dihitung sedikit demi sedikit: dalam setiap iterasi, carry disebarkan ke kiri. Seperti yang ditunjukkan oleh @Orby, versi aslinya tidak membuat tambahan modular. Saya memperbaikinya dan juga menyimpan siklus dalam iterasi, karena carry-in pertama selalu nol.
sumber
s(255,2)
mengembalikan257
daripada1
). Anda dapat memperbaikinya dengan mengubah baris terakhir Andareturn ~(~xxor(axb,C)|256)
yang menambahkan 3 poin.C ++ - skor: 113
sumber
add(1, 255)
mengembalikan 128 untuk saya, @Ryan.%
tidak pada daftar operator diizinkan, yaitu~
,|
,>>
, dan<<
. Mungkin menggantinya denganands(x8|y8, 255)>>1
?~(~x8 | y8 | 0xFFFFFF00)
akan melakukan trik dengan baik dengan hanya 4+ untuk skor Anda.byte
bukannyaint
membuatnya meluap secara otomatis?