Подтвердить что ты не робот

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

Я столкнулся с довольно своеобразной проблемой. Я работаю над компилятором для архитектуры, которая не поддерживает побитовые операции. Однако он обрабатывает подписанную 16-битную целочисленную арифметику, и мне было интересно, можно ли реализовать побитовые операции, используя только:

  • Дополнение (c = a + b)
  • Вычитание (c = a - b)
  • Отдел (c = a/b)
  • Умножение (c = a * b)
  • Модуль (c = a% b)
  • Минимум (c = min (a, b))
  • Максимум (c = max (a, b))
  • Сравнение (c = (a < b), c = (a == b), c = (a <= b), et.c.)
  • Переходы (goto, for, et.c.)

Побитовые операции, которые я хочу поддерживать:

  • Или (c = a | b)
  • И (c = a и b)
  • Xor (c = a ^ b)
  • Левый сдвиг (c = a < b)
  • Правый сдвиг (c = a → b)
    • (Все целые числа подписаны, так что это проблема)
  • Подписанный сдвиг (c = a → > b)
  • Одно дополнение (a = ~ b)
    • (уже найдено решение, см. ниже)

Обычно проблема - это наоборот; как добиться арифметической оптимизации с помощью побитовых хаков. Однако не в этом случае.

В этой архитектуре записываемая память очень скудна, следовательно, требуется побитовая операция. Поразрядные функции сами по себе не должны использовать много временных переменных. Тем не менее, постоянные данные только для чтения и память команд в изобилии. Обратите внимание также на то, что прыжки и ветки не дорогие, и все данные легко кэшируются. Скачки стоят половину циклов, как это делают инструкции арифметики (включая загрузку/хранение). Другими словами, все вышеперечисленные поддерживаемые функции стоят вдвое больше циклов одного скачка.

Некоторые мысли, которые могут помочь:

Я понял, что вы можете сделать одно дополнение (отрицание бит) следующим кодом:

// Bitwise one complement
b = ~a;
// Arithmetic one complement
b = -1 - a;

Я также помню старый взломанный сдвиг при делении с мощностью двух, поэтому побитовый сдвиг может быть выражен как:

// Bitwise left shift
b = a << 4;
// Arithmetic left shift
b = a * 16; // 2^4 = 16

// Signed right shift
b = a >>> 4;
// Arithmetic right shift
b = a / 16;

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

Я также хотел бы знать, есть ли быстрый/простой способ вычисления мощности двух (для операций сдвига) без использования таблицы данных памяти. Наивным решением было бы перейти в поле умножений:

b = 1;
switch (a)
{
  case 15: b = b * 2;
  case 14: b = b * 2;
  // ... exploting fallthrough (instruction memory is magnitudes larger)
  case 2: b = b * 2;
  case 1: b = b * 2;
}

Или подход Set and Jump:

switch (a)
{
  case 15: b = 32768; break;
  case 14: b = 16384; break;
  // ... exploiting the fact that a jump is faster than one additional mul
  //     at the cost of doubling the instruction memory footprint.
  case 2: b = 4; break;
  case 1: b = 2; break;
}
4b9b3361

ОТВЕТЫ

Ответ 1

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

// 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 я не мог найти простого решения, поэтому я сделаю это с циклом по каждому отдельному биту. Может быть, лучший трюк для этого. Pseudocode предполагает, что 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 бит, а все операции ведут себя как подписанные (поэтому a < 0 фактически истинно, когда бит 15 установлен).

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

Ответ 2

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

например.

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

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

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

Ответ 3

Неполный ответ на старый вопрос, здесь основное внимание уделяется 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;
}

Ответ 4

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

Или вы можете ускорить процесс и использовать таблицы поиска 2d, которые хранят результаты, скажем, для двух 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, подходящей для вашей операции. И вы вычитаете маску из значений, если бит установлен.

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

Смотрите сами, в зависимости от того, что лучше для вас.

Ответ 5

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

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

Это превращает ваш номер в массив bools (или int в диапазоне 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]  ;
  }
}

Ответ 6

Просто два других подхода

Например 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));
}