I have the following school problem:
Given a decimal n and a position k return the decimal number without the kth bit, that is, if n=37 and k=3 , you must return 33 . The problem is that I was conditioned to answer it in a single line, (The original problem is codefights apparently, and you can only change the return ), I do not have much experience in handling bits and I'm stuck, I'm coding in C ++.
Every number has a binary representation. This I think we all know. If we want to eliminate the X bit we have to apply an AND operation on that bit. The way to achieve this is to create a bit mask in which all the positions contain a 1 except the position to be deleted, where you will find a 0 .
Example to erase the 2nd bit
int numero = 150;
int mask = 0xFFFFFFFD; // 0xD = 1101
int resultado = numero & mask;
std::cout << resultado; // imprime 148
If now we want to do it dynamically the thing gets a bit complicated.
A very useful equation to change the bit we want is:
resultado = numero ^ ((-nuevoValorDelBit ^ numero) & (1 << indiceDelBit));
Where:
nuevoValorDelBit can be worth 0 or 1 . indiceDelBit is the position of the bit. Remember that the indexes start at 0. Carried this to our code:
int numero = 150;
int bitABorrar = 1; // el 2º bit
int resultado = numero ^ (numero & (1 << bitABorrar));
To understand this equation it is best to take a pencil and paper:
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
Notice 37 in binary is 100101 and 33 is 100001 what they really do is put the third bit in 0, this is done by applying a mask ... That is, doing a & with a known number.
That is, you need to do the operation & bit by bit with 111011 ... now as the numbers are bigger depending on the representation of the hardware where you run (16bits, 32 bits or 64bits) you do not know how many 1 you have of filling therefore I recommend doing the denial of 4 that is 000000100 with the bits upside down ....
int c = 37;
return c & (~4);
return n & ~(1 << (k-1)) do what you're looking for.
I recommend that you reread the problem statement; in this type of operations, for k it is usually considered that its first value is 0, so that (k-1) would simply remain as k (and the result for (n, k) = (37, 3) would not be 33, but 37). Indeed, with pencil and paper it is easier to understand.
The operators << and >> move a value to the left or right (multiply or divide by 2). In this case we start with a 1 and move it to the left k-1 bits. We already have 1 above the bit of n that we want to modify.
Since what we want to do is set the bit to 0, we use ~ to deny the 1, putting it to 0 and the rest of the bits to 1. Then, when doing & with n we will leave < em> pass the bits that correspond to the 1 in our mask, leaving 0 to those that do not.
For you to hit a review, this (although something more convoluted) would give the same result:
return ~(~n | (1 << (k-1))) . Do you understand why?
On a single line, it does not actually delete the bit, it just sets it to zero, it's multiples of 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;