Czy możliwe jest zaimplementowanie operatorów bitowych przy użyciu arytmetyki całkowitej?

W tym środowisku najlepiej byłoby skonfigurować operatory arytmatyczne do oddzielania składników liczb całkowitych.

E. G.

if (a & 16)  becomes if ((a % 32) > 15)
a &= 16 becomes if ((a % 32) < 15) a += 16

Transformaty dla tych operatorów są wystarczająco oczywiste, jeśli ograniczysz RHS do stałej mocy 2.

Odrywanie dwóch lub czterech bitów jest również łatwe do zrobienia.

Niekompletna odpowiedź na Stare pytanie, tutaj koncentrując się na i, lub, XOR. Po znalezieniu rozwiązania dla jednej z tych operacji bitowych można uzyskać dwie pozostałe. Jest kilka sposobów, jeden jest pokazany w następującym programie testowym (skompilowanym na gcc w wersji 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5)): {]}

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define XOR(a,b) (a + b - 2*AND(a,b))
#define IOR(a,b) XOR(XOR(a,b),AND(a,b)) // Credit to Jan Gray, Gray Research LLC, for IOR
static const uint16_t andlookup[256] = {
#define C4(a,b) ((a)&(b)), ((a)&(b+1)), ((a)&(b+2)), ((a)&(b+3))
#define L(a) C4(a,0), C4(a,4), C4(a,8), C4(a,12)
#define L4(a) L(a), L(a+1), L(a+2), L(a+3)
    L4(0), L4(4), L4(8), L4(12)
#undef C4
#undef L
#undef L4
};

uint16_t AND(uint16_t a, uint16_t b) {
    uint16_t r=0, i;

    for ( i = 0; i < 16; i += 4 ) {
            r = r/16 + andlookup[(a%16)*16+(b%16)]*4096;
            a /= 16;
            b /= 16;
    }
    return r;
}

int main( void ) {
    uint16_t a = 0, b = 0;

    do {
            do {
                    if ( AND(a,b) != (a&b) ) return printf( "AND error\n" );
                    if ( IOR(a,b) != (a|b) ) return printf( "IOR error\n" );
                    if ( XOR(a,b) != (a^b) ) return printf( "XOR error\n" );
            } while ( ++b != 0 );
            if ( (a & 0xff) == 0 )
                    fprintf( stderr, "." );
    } while ( ++a != 0 );
    return 0;
}

Można operować bit po bitach (jak zasugerował Mark Byers), wydobywając każdy bit, który będzie wolny.

Lub możesz przyspieszyć proces i użyć tabel wyszukiwania 2d, które przechowują wyniki, powiedzmy, dla dwóch 4-bitowych operandów i działają na nich. Będziesz potrzebował mniej ekstrakcji niż gdybyś operował na bitach.

Możesz również zrobić wszystko za pomocą dodawania, odejmowania i operacji>=. Każda operacja bitowa może być rozwinięta do czegoś takiego za pomocą makr:

/*I didn't actually compile/test it, it is just illustration for the idea*/
uint16 and(uint16 a, uint16 b){
    uint16 result = 0;
    #define AND_MACRO(c) \
        if (a >= c){ \ 
            if (b >= c){\
                result += c;\
                b -= c;\
            }\
            a -= c;\
        }\
        else if (b >= c)\
            b -= c;

    AND_MACRO(0x8000)
    AND_MACRO(0x4000)
    AND_MACRO(0x2000)
    AND_MACRO(0x1000)
    AND_MACRO(0x0800)
    AND_MACRO(0x0400)
    AND_MACRO(0x0200)
    AND_MACRO(0x0100)
    AND_MACRO(0x0080)
    AND_MACRO(0x0040)
    AND_MACRO(0x0020)
    AND_MACRO(0x0010)
    AND_MACRO(0x0008)
    AND_MACRO(0x0004)
    AND_MACRO(0x0002)
    AND_MACRO(0x0001)
    #undef AND_MACRO
    return result;
}

Będziesz potrzeba 3 zmiennych, aby to zaimplementować.

Każda operacja bitowa będzie obracać się wokół makr podobnych do AND_MACRO - porównujesz pozostałe wartości a i b do "maski" (która jest parametrem "c"). następnie dodaj maskę do wyniku w gałęzi if, która jest odpowiednia dla twojej operacji. I odejmujesz maskę od wartości, jeśli bit jest ustawiony.

W zależności od platformy może to być szybsze niż ekstrakcja każdego bitu za pomocą % i/, a następnie odłożenie go z powrotem za pomocą mnożenia.

Zobacz dla siebie, cokolwiek jest dla ciebie lepsze.

Tak długo, jak jesteś skłonny, żeby to było bardzo drogie, tak.

Ogólnie rzecz biorąc, wyraźnie umieścisz liczbę w reprezentacji Bazy-2. Robisz to tak, jak wstawiasz liczbę do bazy-10 (np. aby ją wydrukować), czyli powtarzając dzielenie.

To zamienia Twoją liczbę w tablicę boolów (lub ints w zakresie 0,1), następnie dodajemy funkcje do operowania na tych tablicach.

W C (Oczywiście w C masz operatory bitowe, ale...) implementacja może być:

include <limits.h>
const int BITWIDTH = CHAR_BIT;
typedef int[BITWIDTH] bitpattern;

// fill bitpattern with base-2 representation of n
// we used an lsb-first (little-endian) representation
void base2(char n, bitpattern array) {
  for( int i = 0 ; i < BITWIDTH ; ++i ) {
    array[i] = n % 2 ;
    n /= 2 ;
  }
}

void bitand( bitpattern op1, bitpattern op2, bitpattern result ) {
  for( int i = 0 ; i < BITWIDTH ; ++i ) {
    result[i] = op1[i] * op2[i];
  }
}


void bitor( bitpattern op1, bitpattern op2, bitpattern result ) {
  for( int i = 0 ; i < BITWIDTH ; ++i ) {
    result[i] = (op1[i] + op2[i] != 0 );
  }
}

// assumes compiler-supplied bool to int conversion 
void bitxor( bitpattern op1, bitpattern op2, bitpattern result ) {
  for( int i = 0 ; i < BITWIDTH ; ++i ) {
    result[i] = op1[i] != op2[i]  ;
  }
}

Tylko dwa inne podejścia

Na przykład 16 bitowe i:

int and(int a, int b) {
    int d=0x8000;
    int result=0;
    while (d>0)  {
        if (a>=d && b>=d) result+=d;
        if (a>=d) a-=d;
        if (b>=d) b-=d;
        d/=2;
    }
    return result;
}

Oto zabawny 2 Bit i bez pętli lub wyszukiwania tabeli:

int and(int a, int b) {
    double x=a*b/12;
    return (int) (4*(sign(ceil(tan(50*x)))/6+x));
}