Edabit: Convert a Number to Base-2
Table of Contents
The Problem Statement (from Edabit)
This is the first time I took a look at edabit, their problems seem simpler than LeetCode, although I haven't gone too deep into it. Here's there description of the problem.
Create a function that returns a base-2 (binary) representation of a base-10 (decimal) string number. To convert is simple: ((2) means base-2 and (10) means base-10) 010101001(2) = 1 + 8 + 32 + 128.
Going from right to left, the value of the most right bit is 1, now from that every bit to the left will be x2 the value, value of an 8 bit binary numbers are (256, 128, 64, 32, 16, 8, 4, 2, 1).
Examples:
binary(1) ➞ "1"
binary(5) ➞ "101"
binary(10) ➞ "1010"
Notes
- Numbers will always be below 1024 (not including 1024).
- The strings will always go to the length at which the most left bit's value gets bigger than the number in decimal.
- If a binary conversion for 0 is attempted, return "0".
A Tester
Now that I have the problem statement I can create a test function for it. First, I'll do some importing.
# python
import math
import random
from typing import Callable
# from pypi
from expects import equal, expect
The Built-In Solution
It turns out that python has a built-in function (bin) that solves the problem. They don't explicitly say not to use it, but I'll assume that it isn't what's intended to be used as a solution and use it instead to test any solution I create.
def built_in(integer: int) -> str:
"""Convert an integer to a string of bits
Args:
- `integer`: the base-10 number to convert
Returns:
bit-string equivalent of the input
"""
return bin(integer).lstrip("-0b")
print(built_in(5))
101
The Tester
And now a test function that will compare the output of a function passed in to it to the built_in function's output.
def tester(testee: Callable[[int], str], value: int) -> None:
"""Tests an integer to binary function's output
Args:
- `testee`: function that converts an integer to a bit-string
- `value`: integer to test
Raises:
AssertionError if bit-string is incorrect.
"""
if value == 0:
expect(testee(value)).to(equal("0"))
else:
expect(testee(value)).to(equal(built_in(value)))
return
The Tester Tester
After running the tester a few times I decided to add a runner around it to add a random number to the tests cases.
def tester_tester(testee: Callable[[int], str], verbose: bool=False) -> None:
"""Runs the testee over the given examples and a random number
Args:
- `testee`: function to convert integer to binary string
- `verbose`: output the test-cases if true
Raises:
AssertionError if a case is fails
"""
random_case = random.randrange(2, 1024)
for test_case in ((0, 1, 5, 10, random_case)):
try:
tester(solution_one, test_case)
except ValueError as error:
print("error test-case: {}".format(test_case))
break
if verbose:
print("decimal: {} binary: {}".format(test_case,
solution_one(test_case)))
return
I can't really remember the circumstances anymore, but I think I'm trapping the ValueError because that's raised of the input to the function can't be converted to a binary string. This was probably the 0 test-case.
The First Python Solution
There's probably an even more brute-force way to do this, but the first thing that came into my mind was to use the \(\log_2\) function to find out what exponent of 2 is needed to create the input (without going over) so I'd know how many bits I'd need (this actually gives one less than what you need, since we need an extra bit for the \(2^0\) digit). After finding the exponent the function will then traverses a range in backwards order \(\{n, n-1, \ldots, 1, 0\}\), using the values as the exponent for the next power of 2 to test. If the power is less than the amount remaining to convert I add a 1 to the bit-list and subtract the power from the remainder and if not I add a 0 to the list and move to the next exponent to check.
def solution_one(value: int) -> str:
"""Convert the integer to a binary string
Args:
- value: base-10 integer to convert
Returns:
- binary string version of the input
"""
ZERO, ONE = "0", "1"
if value == 0:
return ZERO
digits = math.floor(math.log2(value)) + 1
remainder = value
bits = []
for exponent in reversed(range(digits)):
if 2**exponent <= remainder:
bits.append(ONE)
remainder -= 2**exponent
else:
bits.append(ZERO)
return "".join(bits)
tester_tester(solution_one, verbose=True)
decimal: 0 binary: 0 decimal: 1 binary: 1 decimal: 5 binary: 101 decimal: 10 binary: 1010 decimal: 242 binary: 11110010
A Python 3 Solution
While I was checking out python's Power and Logarithmic functions I noticed that there was a helpful box noting that python's integers have a built in method called bit_length that will tell you how many bits you need to represent the integer. This should give the the same result as what I did with floor and log2 but since they went to all the trouble of adding it as a method it seemed like it'd be a shame not to use it.
def solution_three(value: int) -> str:
"""Convert the integer to a binary string
Args:
- value: base-10 integer to convert
Returns:
- binary string version of the input
"""
ZERO, ONE = "0", "1"
digits = value.bit_length()
bits = []
remainder = value
for exponent in reversed(range(digits)):
if 2**exponent <= remainder:
bits.append(ONE)
remainder -= 2**exponent
else:
bits.append(ZERO)
return "".join(bits) if bits else ZERO
tester_tester(solution_three, verbose=True)
decimal: 0 binary: 0 decimal: 1 binary: 1 decimal: 5 binary: 101 decimal: 10 binary: 1010 decimal: 926 binary: 1110011110
The End
So, there you go. I wasn't expecting to learn anything from this problem, but I didn't know the bit_length method exists so I guess it just goes to show that there's always something more to learn. Not that I can think of a use for it…