Можно ли реализовать побитовые операторы с помощью целочисленной арифметики?

Первые решения для сдвига (сдвиг - это расстояние сдвига, не должно быть отрицательным, a - это операнд, который нужно сдвинуть, а также содержит результат, когда это сделано). Таблица мощности используется во всех трех сменах.

// table used for shift operations
powtab = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, -32768 };

// logical shift left
if (shift > 15) {
     a = 0; // if shifting more than 15 bits to the left, value is always zero
} else {
     a *= powtab[shift];
}

// logical shift right (unsigned)
if (shift > 15) {
    a = 0; // more than 15, becomes zero
} else if (shift > 0) {
    if (a < 0) {
        // deal with the sign bit (15)
        a += -32768;
        a /= powtab[shift];
        a += powtab[15 - shift];
    } else {
        a /= powtab[shift];
    }
}

// arithmetic shift right (signed)
if (shift >= 15) {
    if (a < 0) {
        a = -1;
    } else {
        a = 0;
    }
} else if (shift > 0) {
    if (a < 0) {
        // deal with the sign bit
        a += -32768;
        a /= powtab[shift];
        a -= powtab[15 - shift];
    } else {
        // same as unsigned shift
        a /= powtab[shift];
    }
}

Для AND, OR и XOR я не мог придумать простого решения, поэтому я сделаю это с помощью цикла по каждому отдельному биту. Для этого есть способ получше. Псевдокод предполагает, что a и b являются входными операндами, c - значением результата, x - счетчиком цикла (каждый цикл должен выполняться ровно 16 раз):

// XOR (^)
c = 0;
for (x = 0; x <= 15; ++x) {
    c += c;
    if (a < 0) {
        if (b >= 0) {
            c += 1;
        }
    } else if (b < 0) {
        c += 1;
    }
    a += a;
    b += b;
}

// AND (&)
c = 0;
for (x = 0; x <= 15; ++x) {
    c += c;
    if (a < 0) {
        if (b < 0) {
            c += 1;
        }
    }
    a += a;
    b += b;
}

// OR (|)
c = 0;
for (x = 0; x <= 15; ++x) {
    c += c;
    if (a < 0) {
        c += 1;
    } else if (b < 0) {
        c += 1;
    }
    a += a;
    b += b;
}

Это предполагает, что все переменные 16-битные и все операции ведут себя как подписанные (так что ‹0 действительно истинно, когда установлен бит 15).

РЕДАКТИРОВАТЬ: я фактически проверил все возможные значения операндов (от -32768 до 32767) для сдвигов от 0 до 31 для правильности, и он работает правильно (при условии целочисленного деления). Для кода AND / OR / XOR исчерпывающий тест на моей машине занимает слишком много времени, но, поскольку код для них довольно прост, в любом случае не должно быть крайних случаев.

В этой среде было бы лучше, если бы вы могли настроить фактическое использование арифматических операторов для выделения компонентов целых чисел.

E.G.

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

Преобразования для этих операторов достаточно очевидны, если вы ограничите RHS постоянной степенью 2.

Отслаивание двух или четырех кусков тоже несложно.

Неполный ответ на старый вопрос с упором на AND, OR, XOR. Как только решение для одной из этих побитовых операций найдено, можно вывести две другие. Есть несколько способов, один из которых показан в следующей тестовой программе (скомпилированной на gcc версии 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5)).

В декабре 2018 года я обнаружил ошибку в решении. Комментируемый ниже XOR работает только потому, что промежуточные результаты в a+b-2*AND(a,b) повышаются до int, что превышает 16 бит для всех современных компиляторов.

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

//#define XOR(a,b) (a + b - 2*AND(a,b)) // Error. Intermediate overflow
#define XOR(a,b) (a - AND(a,b) +  b - 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;
}

Вы можете работать побитно (как предложил Марк Байерс), извлекая каждый бит, который будет медленным.

Или вы могли бы ускорить процесс и использовать 2-мерные таблицы поиска, в которых хранятся результаты, скажем, для двух 4-битных операндов, и оперировать ими. Вам потребуется меньше извлечений, чем если бы вы работали с битами.

Вы также можете делать все, используя операции сложения, вычитания и> =. Каждую побитовую операцию можно развернуть во что-то вроде этого с помощью макросов:

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

Для этого вам понадобятся 3 переменные.

Каждая побитовая операция будет вращаться вокруг макросов, подобных AND_MACRO - вы сравниваете оставшиеся значения a и b с «маской» (которая является параметром «c»). затем добавьте маску к результату в ветви if, которая подходит для вашей операции. И вы вычитаете маску из значений, если установлен бит.

В зависимости от вашей платформы это может быть быстрее, чем извлекать каждый бит с помощью% и /, а затем возвращать его с помощью умножения.

Убедитесь сами, что лучше для вас.

Если вы хотите, чтобы это было очень дорого, да.

По сути, вы явно помещаете число в представление по основанию 2. Вы делаете это так же, как если бы вы поместили число в основание-10 (например, чтобы распечатать его), то есть путем повторного деления.

Это превращает ваше число в массив логических значений (или целых чисел в диапазоне 0,1), а затем мы добавляем функции для работы с этими массивами.

опять же, не то чтобы это намного дороже, чем побитовые операции, и что почти любая архитектура будет предоставлять побитовые операторы.

В C (конечно, в C есть побитовые операторы, но ...) реализация может быть такой:

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

Просто другие подходы

Например, 16-битное И:

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

двойное решение 2-битное И без циклов и поиска в таблице:

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

32-битное целое решение 2-битное И:

int and(int a, int b) {
    return ((684720128*a*a -b) * a) % (b+1);
}

16-битное целое решение 2-битное И:

int and(int a, int b) {
    return ((121 * a) % 16) % (b+1);
}

16-битное целое решение 3-битное И:

int and(int a, int b) {
    return sign(a) * ((((-23-a) * (40+b)) % 2)+40+b) % ((10624 * ((((-23-a) * (40+b))%2)+40+b)) % (a%2 - 2 -a) - a%2 + 2 +a);
}