Est-il possible d'implémenter des opérateurs bitwise en utilisant l'arithmétique entière?

dans cet environnement, il pourrait être préférable si vous pouviez configurer pour réellement utiliser des opérateurs arithmétiques pour éplucher les composants des entiers.

E. G.

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

les transformations pour ces opérateurs sont assez évidentes si vous limitez RHS à une puissance constante de 2.

enlever deux ou quatre bits est également facile à faire.

Une réponse incomplète sur une vieille question, ici, à se concentrer ET, OU, XOR. Une fois qu'une solution est trouvée pour l'une de ces opérations, les deux autres peuvent être dérivées. Il y a plusieurs façons, une est montrée dans le programme de test suivant (compilé sur la version 4.6.3 de gcc (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;
}

vous pouvez opérer petit à petit (comme Mark Byers l'a suggéré), en extrayant tout ce qui sera lent.

ou vous pourriez accélérer le processus et utiliser des tables de recherche 2d qui stockent les résultats, disons, pour deux opérandes 4-bits et opérer sur ceux. Vous aurez besoin de moins d'extractions que si vous opériez sur des bits.

vous pouvez également tout faire en utilisant addition, soustraction et >= opération. Chaque opération de bitwise peut être déroulée dans quelque chose comme ça utilisation de macros:

/*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;
}

vous aurez besoin de 3 variables pour implémenter ceci.

chaque opération bitwise tournera autour de macros similaires à AND_MACRO - vous comparez les valeurs restantes de a et b au" masque "(qui est le paramètre" c"). Ensuite, ajoutez un masque au résultat dans la branche si qui convient à votre opération. Et vous soustrayez le masque des valeurs, si bit est défini.

selon votre plate-forme, il peut être plus rapide que extraire chaque bit en utilisant % et / , puis le remettre en utilisant la multiplication.

voyez par vous-même ce qui est le mieux pour vous.

tant que vous voulez que ce soit très cher, oui.

fondamentalement, vous allez explicitement mettre un nombre dans une représentation de base-2. Vous faites cela tout comme vous mettez un nombre dans la base-10 (par exemple, pour l'imprimer), c'est-à-dire, par division répétée.

cela transforme votre nombre en un tableau de bools (ou ints dans la gamme 0,1), puis nous ajoutons des fonctions pour fonctionner sur ces tableaux.

encore une fois, non pas que ce soit beaucoup plus cher que les opérations bitwise, et que presque n'importe quelle architecture fournira des opérateurs bitwise.

en C (bien sûr, en C vous avez des opérateurs bitwise, mais...) une mise en œuvre pourrait être:

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]  ;
  }
}

deux autres approches

par exemple un 16 bits et :

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

voici un drôle de 2 bits et sans boucles ou tables de recherche:

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