Perl Weekly Challenge 120: Swap Odd/Even bits

by Abigail

Challenge

You are given a positive integer $N less than or equal to 255.

Write a script to swap the odd positioned bit with even positioned bit and print the decimal equivalent of the new binary representation.

Example

Input: $N = 101
Output: 154

Binary representation of the given number is 01 10 01 01. The new binary representation after the odd/even swap is 10 01 10 10. The decimal equivalent of 10011010 is 154.

Input: $N = 18
Output: 33

Binary representation of the given number is 00 01 00 10. The new binary representation after the odd/even swap is 00 10 00 01. The decimal equivalent of 100001 is 33.

Solutions

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.

No bitwise operations

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} \]

Perl

With the input number in $_:

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

Find the full program on GitHub.

Other languages with bitwise operations

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

AWK

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.

bc

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.

Lua

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.

Befunge-93

Without further comments:

>>>>> & :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 . +++++++ <

Find the full program on GitHub.


Please leave any comments as a GitHub issue.