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.

--

--

--

DPhil Candidate in Machine Learning at the University of Oxford. https://www.masaki-adachi.com

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Week in OSINT #2019–20

{UPDATE} パトカーのエスケープ3D Hack Free Resources Generator

Daily newsletter of Fernand0 — Issue #155

How OQEX Global protects its customers

{UPDATE} ナゾトキの時間 - 謎解きで推理力を試す面白いゲーム Hack Free Resources Generator

NFT seized by HMRC in £1.4m fraud case

NFT seized by HMRC in £1.4m fraud case

​​​​​🔥 Giveaway- $300 🔥

Announcement on the 4 Million WTC Pool GMN Airdrop 03

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Masaki Adachi

Masaki Adachi

DPhil Candidate in Machine Learning at the University of Oxford. https://www.masaki-adachi.com

More from Medium

How Python Evolved as a Programming Language

Python Inheritance

Get To Know Python, The Famous Programming Language Today

Why python is a dynamically typed language?