bitwise operators - bitwise - ¿Es posible implementar operadores bit a bit usando aritmética de enteros?
operadores de bits en c (6)
Solo dos otros enfoques
Por ejemplo, un 16 Bit y :
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;
}
Aquí hay un divertido de 2 bits y sin bucles o búsquedas en la tabla:
int and(int a, int b) {
double x=a*b/12;
return (int) (4*(sign(ceil(tan(50*x)))/6+x));
}
Estoy enfrentando un problema bastante peculiar. Estoy trabajando en un compilador para una arquitectura que no admite operaciones bit a bit. Sin embargo, maneja aritméticos enteros firmados de 16 bits y me preguntaba si sería posible implementar operaciones bit a bit usando solo:
- Adición ( c = a + b )
- Resta ( c = a - b )
- División ( c = a / b )
- Multiplicación ( c = a * b )
- Módulo ( c = a% b )
- Mínimo ( c = min (a, b) )
- Máximo ( c = max (a, b) )
- Comparaciones ( c = (a <b), c = (a == b), c = (a <= b), et.c. )
- Salta ( goto, for, et.c. )
Las operaciones bit a bit que quiero ser compatible son:
- O ( c = a | b )
- Y ( c = a & b )
- Xor ( c = a ^ b )
- Cambio a la izquierda ( c = a << b )
- Desplazamiento a la derecha ( c = a >> b )
- (Todos los enteros están firmados por lo que este es un problema)
- Cambio firmado ( c = a >>> b )
- El complemento de uno ( a = ~ b )
- (Ya encontré una solución, ver abajo)
Normalmente el problema es al revés; cómo lograr optimizaciones aritméticas usando hacks bit a bit. Sin embargo, no en este caso.
La memoria grabable es muy escasa en esta arquitectura, de ahí la necesidad de operaciones bit a bit. Las funciones bit a bit no deberían usar muchas variables temporales. Sin embargo, la memoria de instrucción y los datos constantes de solo lectura son abundantes. Una nota al margen aquí también es que los saltos y las ramas no son caros y todos los datos se guardan fácilmente en caché. Los saltos cuestan la mitad de los ciclos que las instrucciones aritméticas (incluidas las de carga / almacenamiento). En otras palabras, todas las funciones soportadas arriba cuestan el doble de ciclos de un solo salto.
Algunos pensamientos que pueden ayudar:
Descubrí que puedes hacer un complemento (negar bits) con el siguiente código:
// Bitwise one''s complement
b = ~a;
// Arithmetic one''s complement
b = -1 - a;
También recuerdo el viejo hack de cambio al dividir con una potencia de dos, por lo que el cambio a nivel de bit se puede expresar como:
// 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;
Para el resto de las operaciones bit a bit, estoy un poco despistado. Ojalá los arquitectos de esta arquitectura hubieran proporcionado operaciones de bits.
También me gustaría saber si existe una forma rápida / fácil de calcular la potencia de dos (para operaciones de cambio) sin utilizar una tabla de datos de memoria. Una solución ingenua sería saltar a un campo de multiplicaciones:
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;
}
O un enfoque 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;
}
En este entorno, podría ser mejor si pudieras configurar realmente operadores aritmáticos para pelar componentes de números enteros.
P.EJ
if (a & 16) becomes if ((a % 32) > 15)
a &= 16 becomes if ((a % 32) < 15) a += 16
Las transformaciones para estos operadores son bastante obvias si restringe el RHS a una potencia constante de 2.
Pelar dos o cuatro pedazos también es fácil de hacer.
Mientras estés dispuesto a que sea muy caro, sí.
Básicamente, pondrás explícitamente un número en una representación de base 2. Haga esto tal como lo haría con un número en la base 10 (por ejemplo, para imprimirlo), es decir, por división repetida.
Esto convierte su número en una matriz de bools (o entradas en el rango 0,1), luego agregamos funciones para operar en esas matrices.
una vez más, no es que esto sea tremendamente más costoso que las operaciones a nivel de bit, y que casi cualquier arquitectura suministrará operadores bit a bit.
En C (por supuesto, en C tienes operadores bit a bit, pero ...) una implementación podría ser:
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] ;
}
}
Primeras soluciones para el cambio (shift es la distancia de desplazamiento, no debe ser negativo, a es el operando que se desplazará y contiene también el resultado cuando se realiza). La tabla de poder es utilizada por las tres operaciones de cambio.
// 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];
}
}
Para AND, OR y XOR no pude encontrar una solución simple, así que lo haré con un bucle sobre cada bit. Puede haber un truco mejor para hacer esto. El seudocódigo asume que a y b son operandos de entrada, c es el valor resultante, x es el contador de bucles (cada bucle debe ejecutarse exactamente 16 veces):
// 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;
}
Eso supone que todas las variables son 16 bits y todas las operaciones se comportan como firmadas (por lo que a <0 en realidad es verdadero cuando se establece el bit 15).
EDITAR: en realidad probé todos los valores de operandos posibles (-32768 a 32767) para los cambios que van de 0 a 31 para la corrección y funciona correctamente (asumiendo divisiones enteras). Para el código AND / OR / XOR una prueba exhaustiva lleva demasiado tiempo en mi máquina, pero dado que el código para estos es bastante simple, no debería haber casos extremos.
Puede operar bit a bit (como sugirió Mark Byers), extrayendo cada bit que será lento.
O puede acelerar el proceso y usar tablas de búsqueda en 2d que almacenan los resultados, por ejemplo, para dos operandos de 4 bits y operar en ellos. Necesitará menos extracciones que si estuviera operando en bits.
También puede hacer todo usando la suma, la substracción y la operación> =. Cada operación bit a bit puede desenrollarse en algo como esto usando 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;
}
Necesitarás 3 variables para implementar esto.
Cada operación a nivel de bits girará en torno a macros similares a AND_MACRO; usted compara los valores restantes de ayb con la "máscara" (que es el parámetro "c"). luego agregue máscara al resultado en la rama if que sea adecuada para su operación. Y resta la máscara de los valores, si se establece un bit.
Dependiendo de su plataforma, puede ser más rápido que extraer cada bit usando% y /, y luego volver a usar la multiplicación.
Vea por usted mismo lo que sea mejor para usted.
Una respuesta incompleta a una vieja pregunta, concentrándose aquí en AND, OR, XOR. Una vez que se encuentra una solución para una de estas operaciones bit a bit, se pueden derivar las otras dos. Hay varias maneras, una se muestra en el siguiente programa de prueba (compilado en la versión 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;
}