Function to flip the bit of the $nth$ binary digit

Question

In programming, every number is expressed in binary-- for example, the number $5$ is $101$. In this concept, we can "flip the bit" of a specific digit. For example, flipping 5's first digit yields $100$ (first digit is the rightmost one, and the last digit is the leftmost one in this case).

Is there a mathematical function, $F_n(x)$, that inputs any number $x$ and outputs another number $y$ where $y$ is $x$ with the $nth$ bit flipped?

I found a solution for the case with a maximum of $2$ bits:

$F_1(x) = -x + 1 \: (mod \: 4)$ flips the first bit

$F_2(x) = x + 2 \: (mod \: 4)$ flips the second bit

However, this only works for the case of $2$ bits, as if we input $5$, we don't get $4$, but rather $0$.

Also, this function makes use of modulus, and is not continuous or differentiable. This function would only need to work with integers, and can output anything for fractional inputs.

Is there a "nice" function that does this?

Answer 1

You're not going to get something continuous or differentiable, because the bit-flipping operation inherently has jumps in it. Even if we define it for all real numbers (since the fractional part doesn't matter anyway), the flipping-the-$k^{\text{th}}$-bit function is going to be:

• $x + 2^{k-1}$ for $0 \le x < 2^{k-1}$ (since the bit is flipped from $0$ to $1$);
• $x - 2^{k-1}$ for $2^{k-1} \le x < 2^k$ (since the bit is flipped from $1$ to $0$);
• $x + 2^{k-1}$ for $2^k \le x < 3 \cdot 2^{k-1}$;
• and so on.

At every multiple of $2^{k-1}$, there will be a jump, breaking any semblance of continuity.

We can compute which multiple of $2^{k-1}$ we're at by $\lfloor \frac{x}{2^{k-1}}\rfloor$, where $\lfloor \cdot \rfloor$ denotes rounding down. Then the function can be expressed as $$ F_k(x) = x + (-1)^{\left\lfloor \frac{x}{2^{k-1}}\right\rfloor} \cdot 2^{k-1} $$ though, again, this will not be continuous.

I should note that this is useful for typing into a calculator (or in some scenarios, into a computer). But if you're communicating with humans, "flip the $k^{\text{th}}$ bit, where the rightmost bit is bit $1$" is a better description than the formula.

Answer 2

How about $F_n(x)=x\oplus 2^{n-1}$ where $\oplus$ denotes binary addition without carry.