0

Tengo el siguiente problema escolar:

Dados un decimal n y una posición k retornar el número decimal sin el k-ésimo bit, es decir, si n=37 y k=3, se debe retornar 33. El problema que es que me condicionaron contestarlo en una sola línea, (El problema original es de codefights al parecer, y solo se puede modificar el return), no tengo mucha experiencia en manejo de bits y estoy atascado, estoy codificando en C++.

0

5 respuestas 5

6

Todo número tiene una representación binaria. Esto creo que lo todos lo sabemos. Si queremos eliminar el bit X tenemos que aplicar una operación AND sobre dicho bit. La forma de conseguir esto es crear una máscara de bits en la que todas las posiciones contienen un 1 salvo la posición a borrar, en la que se encontrará un 0.

Ejemplo para borrar el 2º bit

int numero = 150;
int mask = 0xFFFFFFFD; // 0xD = 1101
int resultado = numero & mask;
std::cout << resultado; // imprime 148

Si ahora lo queremos hacer dinámicamente la cosa se complica un poco.

Una ecuación muy útil para cambiar el bit que deseemos es:

resultado = numero ^ ((-nuevoValorDelBit ^ numero) & (1 << indiceDelBit));

Donde:

  • nuevoValorDelBit puede valer 0 o 1.
  • indiceDelBit es la posición del bit. Recuerda que los índices empiezan en 0.

Llevado esto a nuestro código:

int numero = 150;
int bitABorrar = 1; // el 2º bit
int resultado = numero ^ (numero & (1 << bitABorrar));  

Para entender esta ecuación lo mejor es coger lapiz y papel:

numero = 150 = 1001 0110
A = 1 << bitABorrar = 1 << 1 = 0010
B = numero & (1 << bitABorrar) = numero & A = 1001 0110 & 0010 = 0010
C = numero ^ (numero & (1 << bitABorrar)) = numero ^ B = 1001 0110 ^ 0010 = 1001 0100
resultado = C = 1001 0100 = 148
1
  • 1
    Gracias, tu respuesta me dejo claro lo que se tiene que hacer y las operaciones a utilizar, me has sacado de dudas, tengo que estudiar mas de estas operaciones a nivel de bits. Commented el 30 sept. 2016 a las 0:13
1

En una sola línea, en realidad no elimina el bit, solo lo pone en cero, se trata de múltiplos de 2.

int k=3,n=37; n-=k==1?1:k==2?2:k==3?4:k==4?8:k==5?16:k==6?32:k==7?64:k==8?128:0;
1

return n & ~(1 << k);

La parte izda "n" es trivial

La parte derecha es la forma de poner un bit a 0 en C:

& ~(1 << k)

0

Fijate 37 en binario es 100101 y 33 es 100001 realmente lo que hacen es poner el tercer bit en 0 esto lo haces aplicando una mascara...Es decir haciendo un & con un numero conocido.

Es decir necesitas hacer la operacion & bit a bit con 111011 ... ahora como los numeros son más grandes dependiendo de la representación del hardware donde corra (16bits, 32 bits o 64bits) no sabes cuantos 1 tienes de relleno por lo tanto yo recomiento hacer la negacion de 4 que es 000000100 con los bits al reves....

 int c = 37;
 return c & (~4);
2
  • 1
    Es incluso más fácil usando los literales binarios de C++14: int c = 0b100101; return c & 0b111011; Commented el 29 sept. 2016 a las 8:03
  • Gracias, con tu solucion y la de eferion me quedo claro el asunto, es algo raro por que nunca habia usado estos operadores pero ahora comprendo mejor. Commented el 30 sept. 2016 a las 0:16
0

return n & ~(1 << (k-1)) hace lo que buscas.

Te recomiendo que releas el enunciado del problema; en este tipo de operaciones, para k se suele considerar que su primer valor es 0, de modo que (k-1) quedaría simplemente como k (y el resultado para (n, k) = (37, 3) no sería 33, sino 37). En efecto, con lápiz y papel es más sencillo de entender.

Los operadores << y >> desplazan un valor a izquierda o derecha (multiplican o dividen por 2). En este caso empezamos con un 1 y lo desplazamos a la izquierda k-1 bits. Ya tenemos el 1 encima del bit de n que queremos modificar.

Como lo que queremos hacer es poner a 0 el bit, usamos ~ para negar el 1, poniéndo éste a 0 y el resto de bits a 1. Luego, al hacer el & con n dejaremos pasar los bits que corresponden con los 1 de nuestra máscara, dejando a 0 los que no.

Para que le pegues un repaso, esto (aunque algo más enrevesado) daría el mismo resultado:

return ~(~n | (1 << (k-1))). ¿Entiendes por qué?

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.