Действительно ли возможно реализовать побитовые операторы с помощью целочисленной арифметики?
Я сталкиваюсь с довольно специфической проблемой. Я работаю над компилятором для архитектуры, которая не поддерживает битовые операции. Однако это обрабатывает подписанную 16-разрядную целочисленную арифметику, и я задавался вопросом, будет ли возможно реализовать битовые операции с помощью только:
- Дополнение (c = + b)
- Вычитание (c = - b)
- Подразделение (c = / b)
- Умножение (c = * b)
- Модуль (c = % b)
- Минимум (c = минута (a, b))
- Максимум (c = макс. (a, b))
- Сравнения (c = (<b), c = (== b), c = (<= b), et.c.)
- Переходы (goto, поскольку, et.c.)
Битовые операции, которые я хочу смочь поддерживать:
- Или (c = | b)
- И (c = a и b)
- Xor (c = ^ b)
- Сдвиг влево (c = <<b)
- Сдвиг вправо (c = a>> b)
- (Все целые числа подписываются так, это - проблема),
- Сдвиг со знаком (c = a>>> b)
- Поразрядное дополнение до единицы (= ~b)
- (Уже найденный решением, посмотрите ниже),
Обычно проблема наоборот; как достигнуть арифметической оптимизации с помощью поразрядных взломов. Однако не в этом случае.
Перезаписываемая память очень недостаточна на этой архитектуре, следовательно потребность в битовых операциях. Сами поразрядные функции не должны использовать много временных переменных. Однако постоянная память данных и инструкции только для чтения в изобилии. Примечание стороны здесь также - то, что переходы и ответвления не являются дорогими, и все данные с готовностью кэшируются. Переходы стоят половины циклов как арифметика (включая загрузку и хранение), инструкции делают. На других словах, всей вышеупомянутой поддерживаемой стоимости функций дважды циклы единственного перехода.
Некоторые мысли, которые могли бы помочь:
Я выяснил, что можно сделать поразрядное дополнение до единицы (инвертируйте биты) со следующим кодом:
// Bitwise one's complement
b = ~a;
// Arithmetic one's 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;
}
Или подход Набора и Перехода:
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;
}
4 ответа
Первые решения для сдвига (shift - расстояние сдвига, не должно быть отрицательным, 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-битные и все операции ведут себя как знаковые (так что a<0 на самом деле истинно, когда установлен бит 15).
EDIT: я действительно протестировал все возможные значения операндов (от -32768 до 32767) для сдвигов от 0 до 31 на корректность, и он работает правильно (предполагая целочисленное деление). Для кода AND/OR/XOR исчерпывающий тест занимает слишком много времени на моей машине, но поскольку код для них довольно прост, в любом случае не должно быть никаких крайних случаев.
Вы можете работать побитно (как предложил Марк Байерс), извлекая каждый бит, что будет медленно.
Или вы можете ускорить процесс и использовать 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, которая подходит для вашей операции. И вычитаете маску из значений, если бит установлен.
В зависимости от вашей платформы, это может быть быстрее, чем извлекать каждый бит с помощью % и / , а затем складывать их обратно с помощью умножения.
Смотрите сами, что лучше для вас.
При условии, что вы готовы к тому, что это будет очень дорого, да.
По сути, вы явно переводите число в представление по основанию-2. Вы делаете это так же, как вы переводите число в основание-10 (например, чтобы распечатать его), то есть путем повторного деления.
Это превращает ваше число в массив bools (или ints в диапазоне 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] ;
}
}
В этой среде было бы лучше, если бы вы могли настроить фактическое использование арифматических операторов для выделения компонентов целых чисел.
Э.
if (a & 16) becomes if ((a % 32) > 15)
a &= 16 becomes if ((a % 32) < 15) a += 16
Преобразования для этих операторов достаточно очевидны, если вы ограничите RHS постоянной степенью 2.
Удаление двух или четырех битов также легко сделать.