Menerapkan penambah 8 bit

12

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 #definedan 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

Orby
sumber
2
mengapa tidak bitwise "and"?
rdans
@Ryan Kebanyakan orang lebih mengenal gerbang NAND daripada gerbang NOR :)
Orby
1
apakah rekursi dihitung sebagai satu lingkaran?
rdans
@Ryan Recursion tidak dihitung sebagai loop, meskipun saya tidak yakin bagaimana Anda akan menerapkannya tanpa pernyataan kondisional.
Orby
Apakah overflow didefinisikan atau dapatkah saya hanya mengeluarkan sesuatu jika meluap?
Comintern

Jawaban:

8

Python, 36 operasi

Metode yang logaritmik pada parameter "8"!

def add(a,b):
    H = a&b   #4 for AND
    L = a|b   #1 
    NX = H | (~L) #2
    K = NX 

    H = H | ~(K | ~(H<<1)) #5
    K = K | (K<<1) #2

    H = H | ~(K | ~(H<<2)) #5
    K = K | (K<<2) #2

    H = H | ~(K | ~(H<<4)) #5

    carry = H<<1 #1

    neg_res = NX ^ carry  #7 for XOR
    res_mod_256 = ~(neg_res|-256) #2
    return res_mod_256

Idenya adalah untuk mencari tahu indeks mana yang meluap dan menyebabkan terbawa. Awalnya, ini hanya tempat-tempat di mana kedua aandd bmemiliki 1. 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:

def add(a,b):
    H = a&b   #4 for AND
    L = a|b   #1 
    NX = H | (~L) #2

    c=H<<1  #1

    for _ in range(6): #6*5
        d = (~c)|NX
        e = ~d
        c = c|(e<<1)

    res = c ^ NX  #7 for XOR

    res_mod_256 = ~(res|-256) #2
    return res_mod_256

Test rig, untuk siapa saja yang ingin menyalinnya.

errors=[]
for a in range(256):
    for b in range(256):
        res = add(a,b)
        if res!=(a+b)%256: errors+=[(a,b,res)]

print(len(errors),errors[:10])
Tidak
sumber
8

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.

unsigned char sum(unsigned char x, unsigned char y)
{
    static unsigned char z[] = {
        0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
        16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
        32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
        48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
        64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
        80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
        96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
        112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
        128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
        144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
        160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
        176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
        192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
        208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
        224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
        240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
        0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
        16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
        32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
        48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
        64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
        80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
        96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
        112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
        128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
        144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
        160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
        176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
        192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
        208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
        224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
        240,241,242,243,244,245,246,247,248,249,250,251,252,253,254
    };

    return (&z[x])[y];
}

sumber
Ini jelas merupakan celah, tetapi +1 untuk menunjukkannya.
Orby
7

python, skor = 83 80

def g(x,y):
    for i in xrange(7):
        nx = ~x
        ny = ~y
        x,y = ~(x|ny)|~(nx|y), (~(nx|ny))<<1
    x = ~(x|~y)|~(~x|y)
    return ~(~x|256)

Buka 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 bawah y.

Keith Randall
sumber
7

C, Nilai: 77 60

Golf hanya untuk itu, 206 169 131 byte:

#define F c=((~(~c|~m))|n)<<1;
a(x,y){int m=(~(x|~y))|~(~x|y),n=~(~x|~y),c;F F F F F F F return (unsigned char)(~(m|~c))|~(~m|c);}

Diperluas:

int add(x,y)
{
    int m=(~(x|~y))|~(~x|y);
    int n=~(~x|~y);
    int c = 0;
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1;    
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1; 
    return (int)((unsigned char)(~(m|~c))|~(~m|c));
}

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.

Komintern
sumber
Jika Anda akan menangani lilitan dengan cara itu, Anda bisa saja menyerah unsigned char. Lebih bersih dan lebih portabel.
Orby
@Orby - Saya kira mengetik unsignedtidak datang secara alami kepada saya dalam kode golf. Anda tentu saja benar - diperbarui.
Comintern
4

Python - Skor 66 64

def xand(a,b):
    return ~(~a|~b) #4

def xxor(a,b):
    return (~(a|~b))|~(~a|b) #7

def s(a,b):
    axb = xxor(a,b)   #7
    ayb = xand(a,b)   #4

    C = 0
    for i in range(1,8):
        C = ((xand(C,axb))|ayb)<<1    #(1+1+4)x7=6x7=42

    return xxor(axb,xand(C,255))    #7 + 4 = 11
    #total: 7+4+42+11 = 64

Ini 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.

Juan I Carrano
sumber
3
Pekerjaan bagus, tetapi kode Anda tidak membungkus dengan benar (yaitu s(255,2)mengembalikan 257daripada 1). Anda dapat memperbaikinya dengan mengubah baris terakhir Anda return ~(~xxor(axb,C)|256) yang menambahkan 3 poin.
Orby
2

C ++ - skor: 113

#define ands(x, y) ~(~x | ~y) << 1
#define xorm(x, y) ~(y | ~(x | y)) | ~(x | ~(x | y))

int add(int x, int y)
{
int x1 = xorm(x, y);
int y1 = ands(x, y);

int x2 = xorm(x1, y1);
int y2 = ands(x1, y1);

int x3 = xorm(x2, y2);
int y3 = ands(x2, y2);

int x4 = xorm(x3, y3);
int y4 = ands(x3, y3);

int x5 = xorm(x4, y4);
int y5 = ands(x4, y4);

int x6 = xorm(x5, y5);
int y6 = ands(x5, y5);

int x7 = xorm(x6, y6);
int y7 = ands(x6, y6);

int x8 = xorm(x7, y7);
int y8 = ands(x7, y7);

return (x8 | y8) % 256;
}
rans
sumber
add(1, 255)mengembalikan 128 untuk saya, @Ryan.
Orby
@Orby diperbaiki sekarang
rdans
%tidak pada daftar operator diizinkan, yaitu ~, |, >>, dan <<. Mungkin menggantinya dengan ands(x8|y8, 255)>>1?
Orby
Sebenarnya, ~(~x8 | y8 | 0xFFFFFF00)akan melakukan trik dengan baik dengan hanya 4+ untuk skor Anda.
Orby
2
Tapi bukankah membuat tipe itu bytebukannya intmembuatnya meluap secara otomatis?
haskeller bangga