Perl Weekly Challenge 120: Swap Odd/Even bits

This is almost the same exercise as last week's. We just have to swap a different set of bits.

If we take a number not exceeding \(255\), and look at its binary representation, we have:

\[ b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0 \]

Swapping the odd positioned bits with the even positioned bits, we get:

\[ b_6 b_7 b_4 b_5 b_2 b_3 b_0 b_1 \]

Now, we could take the number, get a binary representation, swap the two sets of bits using a regular expression or substrings, and turn this back into a decimal number.

But we can achieve the same things by manipulating the bits directly. To do this, we first split the original number, which will call \(N\), into two parts:

\[ \begin{array}{cccccccc|rcl} b_7 & 0 & b_5 & 0 & b_3 & 0 & b_1 & 0 & (N & \& & \text{0x55}) \\ 0 & b_6 & 0 & b_4 & 0 & b_2 & 0 & b_0 & (N & \& & \text{0xAA}) \\ \hline b_7 & b_6 & b_5 & b_4 & b_3 & b_2 & b_1 & b_0 & & & \end{array} \]

We can now shift each part one bit the right or left:

\[ \begin{array}{cccccccc|rclcc} 0 & b_7 & 0 & b_5 & 0 & b_3 & 0 & b_1 & (N & \& & \text{0x55}) & >> & 1 \\ b_6 & 0 & b_4 & 0 & b_2 & 0 & b_0 & 0 & (N & \& & \text{0xAA}) & << & 1 \\ \hline b_6 & b_7 & b_4 & b_5 & b_2 & b_3 & b_0 & b_2 & & & & & \end{array} \]

We can now use a bitwise-or (|) or just plain addition to of the three parts above to get the final result.

Our solutions looks a lot like the ones in the previous week; only the languages lacking bitwise operations looks slightly different.

For languages lacking bitwise operations, we will not be manipulating the bits. Instead, we will treat the number as a sum of powers of \(2\):

\[ N = \sum_{i = 0}^7 b_i 2^i, 0 \leq b_i \leq 1 \]

We can split this into two groups:

\[ N = \sum_{i = 0, i \text{ odd}}^7 b_i 2^i + \sum_{j = 0, j \text{ even}}^7 b_j 2^j \]

We can now multiply the first group by \(2\), while we divide the second group by \(2\), to get our wanted answer \(N'\):

\[ N' = \left(\sum_{i = 0, i \text{ odd}}^7 b_i 2^i\right) \div 2 + \left(\sum_{j = 0, j \text{ even}}^7 b_j 2^j\right) * 2 \]

Which we can rewrite as:

\[ N' = \sum_{i = 0, i \text{ odd}}^7 b_i 2^{i - 1} + \sum_{j = 0, j \text{ even}}^7 b_j 2^{j + 1} \]

and

\[ N' = \sum_{i = 0}^7 b_i 2^{i \% 2 = 1 \text{ ? } i - 1 \text{ : } i + 1} \]

With the input number in $_:

say + ($_ & 0x55) << 1 | ($_ & 0xAA) >> 1

Find the full program on GitHub.

Our implementations in Bash, C, Go, Java, Node.js, Pascal, Python, R, Ruby, Scheme and Tcl are very similar to our Perl implementation.

AWK doesn't have bitwise operations. So, we're using arithmetic to get the powers of 2 the number is composed off. Each power of 2 is either multiplied by 2 or divided by 2, depending on whether the power is even or odd.

This leads to:

{
    out = 0
    num = $1
    for (i = 0; i < 8; i ++) {
        bit = int ((num - (num % 2 ^ i)) / 2 ^ i) % 2;
        if (bit) {
            out += 2 ^ (i + (i % 2 ? -1 : 1))
        }
    }
    print out
}

Find the full program on GitHub.

There are not bitwise operations in bc either. So we're using a similar solution as the AWK solution. With the input number in num:

out = 0
for (i = 0; i < 8; i ++) {
    bit = ((num - (num % 2 ^ i)) / 2 ^ i) % 2
    if (bit == 1) {
        if (i % 2 == 1) {
            out += 2 ^ (i - 1)
        }
        if (i % 2 == 0) {
            out += 2 ^ (i + 1)
        }
    }
}
out

Find the full program on GitHub.

The lua solution is very similar to the AWK solution. With the input number in num, we have:

out = 0
for i = 0, 7 do
    bit = math . floor ((num - (num % (2 ^ i))) / (2 ^ i)) % 2
    if bit == 1
    then
        if i % 2 == 1
        then
            out = out + 2 ^ (i - 1)
        else
            out = out + 2 ^ (i + 1)
        end
    end
end
print (out)

Find the full program on GitHub.

>>>>> & :1+!#@_ : 2% 2*   \ 2/ : 2%      \ 2/ : 2% 8*     \ 2/ : 2% 4* \ 2/ v
    ^                                                                       v
>>>> >>>>>>>>>> : 2% 48** \ 2/ : 2% 44** \ 2/ : 2% 844*** \ 2/   2% 88** v  >>>
    ^                                                                    v
    ^<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<  ,+55 . +++++++ <