One-man hackathon #Day2

The image was brought from here.

Today’s problem is about a bit swap in the chapter 4.2. So let’s get started.

Question 2; How would implement code that takes as an input a 64-bit integer and swaps the bits at indices i and j?

A 64-bit integer can be viewed as an array of 64 bits, with the bit at index 0 corresponding to the least significant bit (LSB), and the bit at index 63 corresponding to the most significant bit (MSB).

Metrics

To evaluate the codes, I used the following functions. This will compare the execution time for two different 64-bit integers with two different indices. The function entitled “swap_bit( )” is the function we will develop. Here, we assume the index starts from 0, with the LSB being at index 0.

My Solution

Swapping (1,60) 
     Original: 1001010110101010101000010101111101010110101101010110101101011101 
     swapped : 1000010110101010101000010101111101010110101101010110101101011111, 
     calculated within 0.000018 sec.
Swapping (3,52) 
     Original: 1001010110101010101000010101111101010110101101010110101101011101 
     swapped : 1001010110111010101000010101111101010110101101010110101101010101, 
     calculated within 0.000016 sec.
Swapping (6,58) 
     Original: 1001010110101010101000010101111101101010100011100010111010010101 
     swapped : 1001000110101010101000010101111101101010100011100010111011010101, 
     calculated within 0.000018 sec.
Swapping (5,61) 
     Original: 1001010110101010101000010101111101101010100011100010111010010101 
     swapped : 1001010110101010101000010101111101101010100011100010111010010101, 
     calculated within 0.000011 sec.

As we can see, my solution successfully swapped all cases. The key idea I used here is to convert a 64-bit integer into a string. That is, my answer could be 𝑂(2). Besides, there are no significant differences in the execution time, supporting this complexity estimation. However, the calculation time and complexity in string conversion and the other pythonic built-in functions, this answer could require more time. With regard to other solutions in the textbook, I am going to write them down. The first solution is the brute-force algorithm using iterative tests.

The best solution in the textbook

Swapping (1,60) 
     Original: 1001010110101010101000010101111101010110101101010110101101011101 
     swapped : 1000010110101010101000010101111101010110101101010110101101011111, 
     calculated within 0.000010 sec.
Swapping (3,52) 
     Original: 1001010110101010101000010101111101010110101101010110101101011101 
     swapped : 1001010110111010101000010101111101010110101101010110101101010101, 
     calculated within 0.000004 sec.
Swapping (6,58) 
     Original: 1001010110101010101000010101111101101010100011100010111010010101 
     swapped : 1001000110101010101000010101111101101010100011100010111011010101, 
     calculated within 0.000006 sec.
Swapping (5,61) 
     Original: 1001010110101010101000010101111101101010100011100010111010010101 
     swapped : 1011010110101010101000010101111101101010100011100010111010110101, 
     calculated within 0.000005 sec.

Obviously, the execution time clearly illustrates this solution is way quicker than mine; this algorithm is 𝑂(1). The key idea of this solution is a bitmask that applies only the two bits.

Realisations

• I should use a bitmask and a bit shift instead of built-in function.