Perl Weekly Challenge 121: Invert Bit

Third week in a row where we have to manipulate bits! See Swap Nibbles and Swap Odd/Even Bits.

If we take a number, and look at its binary representation, we have:

\[ \ldots b_{n+1} b_{n} b_{n-1} \ldots b_3 b_2 b_1 \]

Inverting bit \(n\), we get:

\[ \ldots b_{n+1} \overline{b_{n}} b_{n-1} \ldots b_3 b_2 b_1 \]

We can do this by some bit fiddling. Recall the truth table for the exclusive or operation:

\[ \begin{array}{|c|c|c|} \hline a & b & a \oplus b \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \hline \end{array} \]

So, we can achieve the given task by taking the bitwise exclusive-or of the original number, and \(1\) shifted \(n - 1\) places the the left:

\[ \begin{array}{|cccccccc|c|} \hline \ldots & b_{n+1} & b_{n} & b_{n-1} & \ldots & b_3 & b_2 & b_1 & M \\ \ldots & 0 & 1 & 0 & \ldots & 0 & 0 & 0 & 1 << (N - 1) \\ \hline \ldots & b_{n+1} & \overline{b_{n}} & b_{n-1} & \ldots & b_3 & b_2 & b_1 & M \oplus (1 << (N - 1)) \\ \hline \end{array} \]

For all solutions, we assuming the input consists of lines with two numbers, $m, and $n on each line. For each input line, we output a single number.

With the command line options -pla:

$_=$F[0]^1<<--$F[1]

The -p option reads the input line by line, executing the program for each line, and printing whatever is left in $_.

The -a autosplits each input line on white space, putting the results in the array @F. So, for our program, it means that $m is available in $F [0], and $n in $F [1].

Hence, this simply calculates the wanted number.

Find the full program on GitHub.

The implementations in languages with bitwise operations, and all look similar. We'll just give the code fragments doing the calculations:

AWK doesn't have bitwise operations, but GNU AWK does:

print xor ($1, lshift (1, $2 - 1))

Find the full program on GitHub.

printf ("%d\n", m ^ (1 << -- n));

fmt . Printf ("%d\n", m ^ (1 << (n - 1)))

System . out . println (m ^ (1 << (n - 1)));

console . log (m ^ (1 << -- n))

writeln (m xor (1 shl (n - 1)));

print (m ^ (1 << (n - 1)))

cat (bitwXor (m, (bitwShiftL (1, n - 1))), "\n")

puts (m ^ (1 << (n - 1)))

(format #t "~d\n" (logxor m (ash 1 (- n 1))))

puts [expr $m ^ (1 << ($n - 1))]

Without bitwise operations, we have to use arithmetic. First, we find out whether the bit is on by dividing (using integer division) the number \(M\) by \(2^{N-1}\) and checking whether the result is odd or even. If it's even, we add \(2^{N-1}\) to \(M\), else we subtract \(2^{N-1}\) from \(M\).

((n = 2 ** (n - 1)))
if  (((m / n) % 2))
then ((m = m  - n))
else ((m = m  + n))
fi
echo $m

p = 2 ^ (n - 1)
b = (m / p) % 2
if (b == 1) {
    m = m - p
}
if (b == 0) {
    m = m + p
}
m

x = 1
for i = 1, n - 1 do
    x = x * 2
end
if  math . floor (m / x) % 2 == 1 then
    m = m - x
else
    m = m + x
end
print (m)

>>> & :1+!#@_ :& 1- 1 >> \ :! #v_ 1- \ 2* v
^                     ^        $          v
^                     ^<<<<<<<   <<<<<<<<<<
^         v - <                v
^< ,+55 . <   | %2 \g11 / p11: <
          ^ + <