If we have a number with n bits, can we remove a bit such that the remaining number tells us which b-CodePudding

while solving a computer science problem, I came up with this question. I would like to find an algorithm to, given a number with n bits, I remove a bit such that the number formed by the other n-1 bits (in the same order) tell us whether the removed bit is a 0 or an 1.

For instance, if n = 7, if it is given the number 0110101, I must be able to choose a bit such that the remaining number tells me if the removed bit is a 0 or an 1. If the number 010101 corresponds to an 1, then I can remove the second (or the third) bit from 0110101 and, with the remaining number (010101) i would know that I removed an 1.

If I found a correspondence between each number of n-1 bits and a 0 or a 1 such that for every n-bit number I am able to remove a bit that is the correspondent of the remaining (n-1)-bit number, I would have the problem solved, but I still couldn't find such a correspondence. May anyone if there is such a correspondece and what is the correspondence, please?

CodePudding user response：

if you are only looking at it from the perspective of one bit missing, tell if it was 0 or 1, simple parity should solve your case...

parity is just: agree upon either having an even amount of 1 bits or an odd amount

given any N bit number, count the bits that are one and add a new bit so the resulting number either has an even or odd amount of 1 bits

now if one bit is deleted you can simply count the number of 1 bits... say you are running even parity... if your number has an even number of 1s, a 0 was deleted, else it was a 1

parity itself will not tell you if a bit was removed
but knowing that it was removed, parity can answer if it was a 0 or 1

example with numbers:

initial number: 0110101  
even parity:    01101010 (we add a 0 because there were 4 1s)  
delete a bit:     x  
                0101010
count parity -> 3 -> odd -> we are on even parity -> a 1 was removed

CodePudding user response：

There does not exist a unique "correspondence" between all n-bit numbers and all n-1 bit numbers. So the algorithm in question cannot exist with the given parameters.

Observe: (My apologies for the notation. I'm just getting started on stack overflow and have yet to learn how to use nice symbols [specifically those used in set theory would have been helpful])

Let A be the set of all n-bit numbers. Let X be the set of all n-1 bit numbers which are obtained by removing a 1 from all elements in set A. Let Y be the set of all n-1 bit numbers which are obtained by removing a 0 from all elements in set A.

Now, suppose we have an n-1 bit value b. We would like to determine whether b belongs in the set X or the set Y, and note that it cannot be in both (your algorithm). The only way this would be able to work is if the intersection of X and Y is empty.

So, we can prove that the intersection of X and Y is not empty by showing that there exists some n-1 bit value z where z is an element in X and z is an element in Y.

Let z be the n-1 bit number 11010. To obtain z in X we start with the n-bit value in A 110110, then we remove a 1 to obtain 11010 (which is z), which by our definition of set X it belongs in set X. So, z=11010 is an element of X.

Let z be the n-1 bit number 11010. To obtain z in Y we start with the n-bit value in A 110010, then we remove a 0 to obtain 11010 (which is z), which by our definition of set Y it belongs in set Y. So, z=11010 is an element of Y.

Since we can see that there exists a value z which is an element of X and an element of Y, we can see that the intersection of X and Y cannot be empty. Therefore, the algorithm in question cannot exist as there is no unique relation.