2010-11-25 36 views
15

en el espíritu de graphics.stanford.edu/~seander/bithacks.html que necesito para resolver el siguiente problema:C/C++ Bit haciendo girar

int x; 
int pow2; // always a positive power of 2 
int sgn; // always either 0 or 1 
// ... 
// ... 
if(sgn == 0) 
    x -= pow2; 
else 
    x += pow2; 

Por supuesto que necesita para evitar el condicional. Hasta ahora, lo mejor que se me ocurrió es

x -= (1|(~sgn+1))*pow2 

pero eso implica una multiplicación que también me gustaría evitar. Gracias por adelantado.

EDIT: Gracias a todos,

x -= (pow2^-sgn) + sgn 

parece hacer el truco!

+0

debe aceptar la respuesta, entonces. – Simone

+0

Cuando la multiplicación no es un problema, también tenemos: 'x - = (1-2 * sgn) * pow', usando el mapeo' 0 -> 1' y '1 -> -1', que es igual a' x - > (1-2x) '. – rafak

+0

una vez más, paréntesis! la precedencia de '^' es menor que '+', entonces 'x - = pow2^-sgn + sgn' es' x - = pow2^(- sgn + sgn) 'es' x - = pow2'. – lijie

Respuesta

16

me gustaría probar

x -= (pow2^(~sgn+1)) + sgn 

o, según lo sugerido por Lijie en los comentarios

x -= (pow2^-sgn) + sgn 

Si sgn es 0, ~sgn+1 es también 0, entonces pow2^(~sgn+1) == pow2. Si sgn es 1, (~sgn+1) es 0xFFFFFFFF, y (pow2^(~sgn+1)) + sgn == -pow2.

+4

puede cambiar '~ sgn + 1' a' -sgn'. – lijie

+0

@lijie: Sí, claro. ¡Gracias! –

+2

oh sí. uh '^' es de menor prioridad que '+', entonces sugiero paréntesis. – lijie

2

De la parte superior de mi cabeza:

int subMask = sgn - 1; 
x -= pow2 & subMask; 
int addMask = -sgn; 
x += pow2 & addMask; 

No hay garantías sobre si funciona o si esta es inteligente, esto es sólo una idea al azar que vino a la cabeza.

EDIT: vamos a hacer esto un poco menos legible (aka más compacto):

x += (pow2 & -sgn) - (pow2 & (sgn-1)); 
4
mask = sgn - 1; // generate mask: sgn == 0 => mask = -1, sgn == 1 => mask = 0 

x = x + (mask & (-pow2)) + (~mask & (pow2)); // use mask to select +/- pow2 for addition 
+0

Eso es un condicional. –

+4

@Sven: no, '&' es un operador bit a bit –

+0

Hubo un condicional cuando publiqué mi comentario. Y tu sabes esto. –

1

Cambiaría la interfaz y reemplazaría la multiplicación por el desplazamiento a la izquierda. (Uso exponente en lugar de pow2)

1

Usted puede hacer algo como (desde el enlace) x + = ((pow2^-sgn) + SGN)