Можно ли реализовать побитовые операторы с использованием целочисленной арифметики?
Я сталкиваюсь с довольно специфической проблемой. Я работаю над компилятором для архитектуры, которая не поддерживает побитовые операции. Однако он обрабатывает 16-разрядную целочисленную арифметику со знаком, и мне было интересно, можно ли реализовать побитовые операции, используя только:
- Сложение (с = а + б)
- Вычитание (c = a - b)
- Отдел (с = а / б)
- Умножение (c = a * b)
- Модуль (с = а% б)
- Минимум (c = min (a, b))
- Максимум (c = max (a, b))
- Сравнения (c = (a
- Прыжки (goto, for, et.c.)
Побитовые операции, которые я хочу поддерживать:
- Или (с = а | б)
- И (с = а и б)
- Xor (c = a ^ b)
- Сдвиг влево (c = a << b)
- Сдвиг вправо (c = a >> b)
- (Все целые числа подписаны, так что это проблема)
- Сдвиг со знаком (c = a >>> b)
- Дополнение (a = ~ 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;
}
Или подход Set & 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;
}
7 ответов
Первые решения для сдвига (сдвиг - это расстояние сдвига, он не должен быть отрицательным, 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 исчерпывающий тест занимает слишком много времени на моей машине, но, поскольку код для них довольно прост, в любом случае не должно быть крайних случаев.
В этой среде было бы лучше, если бы вы могли настроить использование арифметических операторов для выделения компонентов целых чисел.
НАПРИМЕР
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)):
#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;
}
Вы можете работать побитно (как предложил Марк Байерс), извлекая каждый бит, который будет медленным.
Или вы можете ускорить процесс и использовать 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 с "mask" (который является параметром "c"). затем добавьте маску к результату в ветке if, которая подходит для вашей операции. И вы вычитаете маску из значений, если бит установлен.
В зависимости от вашей платформы, это может быть быстрее, чем извлекать каждый бит с использованием% и /, а затем возвращать его с помощью умножения.
Убедитесь сами, что лучше для вас.
Пока вы готовы, чтобы это было очень дорого, да.
По сути, вы явно поместите число в представление base-2. Вы делаете это так же, как вы положили бы число в основание-10 (например, чтобы распечатать его), то есть путем повторного деления.
Это превратит ваше число в массив bools (или целые числа в диапазоне 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));
}
вот метод, который я придумал для параллельной обработки 16-битных битов XOR с использованием целочисленных сложений Double-64:
[gmn]awk '{ CONVFMT = OFMT = "%.20g"
c = (a=3e15+("1011000111110101"))+
(b=3e15+("1101010010101110"))
sub(/[7]/, "1",c)
gsub(/[268]/ ,"0",c)
sub(/^[^01]+/,"",c); print c }'
Битовые строки выглядят так (я вынул
3e15 защитная цифра здесь для ясности):
a = 1011 0001 1111 0101
b = 1101 0100 1010 1110
c = 8112 0101 2121 1211 (intermediate)
-------------------------------------------
c = 0110 0101 0101 1011 (output)
одно 52-битное целое число без знака и лишь несколько вызовов подстановки строк, и вывод уже находится в состоянии, которое может быть передано ниже по потоку.
Абсолютное максимальное значение, до которого поднимется это добавление, составляет 8222 2222 222 222, что чуть меньше 53-битного жесткого ограничения.
Для побитового И преобразуйте все 1, ведущие 6 или 7, в 0: только 2 и ведущие 8 являются истинными битами, которые затем следует преобразовать в 1.
Для побитового ИЛИ все наоборот - все, кроме 0 или 6, в выходной строке принимает значение «1».
Для побитового дополнения еще проще - начните с 1,111,111,111,111,111 и вычтите конкатенированные битовые строки из 2 байтов, чтобы получить его.