HCI Data Representation Practice Question 2
(a) Decimal numbers to binary numbers
Non-Recursive
# Non-Recursive
def dec_to_bin(number):
# Special case
if number == 0:
return "0"
answer = ""
while number > 0:
# Remainder becomes the next binary digit
remainder = str(number % 2)
# Put the remainder at the front of the answer
answer = remainder + answer
# Update number to the quotient so the loop progresses
number = number // 2
return answer
Recursive
# Recursive
def dec_to_bin(number):
# base case
if number < 2:
return str(number)
return dec_to_bin(number // 2) + str(number % 2)(b) Decimal numbers to hexadecimal numbers
Non-Recursive
# Non-Recursive
HEX_DIGITS = "0123456789ABCDEF"
def dec_to_hex(number):
if number == 0:
return "0"
answer = ""
while number > 0:
# Remainder is an integer from 0 to 15
remainder = number % 16
# Convert it to the corresponding hexadecimal character
hex_digit = HEX_DIGITS[remainder]
# Add the digit to the front
answer = hex_digit + answer
# Continue converting the quotient
number = number // 16
return answer
Recursive
# Recursive
HEX_DIGITS = "0123456789ABCDEF"
def dec_to_hex(number):
# base case
if number < 16:
return HEX_DIGITS[number]
# recursive case
return dec_to_hex(number // 16) + HEX_DIGITS[number % 16]
# Example
dec_to_hex(2748)
= dec_to_hex(171) + "C"
= dec_to_hex(10) + "B" + "C"
= "A" + "B" + "C"
= "ABC"(c) Binary numbers to decimal numbers
Non-Recursive
# Non-Recursive
def bin_to_dec(number):
answer = 0
no_of_bin = len(number)
for digit in number:
answer = answer + int(digit) * 2 ** (no_of_bin - 1)
no_of_bin -= 1
return answerChatGPT Ver:
def bin_to_dec(number):
answer = 0
for i in number:
answer = answer * 2 + int(i)
return answerRecursive
# Recursive
def bin_to_dec(number):
# base case
if len(number) == 1:
return int(number)
# recursive case
return bin_to_dec(number[:-1]) * 2 + int(number[-1])Trace "1101"
bin_to_dec("1101")
= bin_to_dec("110") × 2 + 1bin_to_dec("110")
= bin_to_dec("11") × 2 + 0bin_to_dec("11")
= bin_to_dec("1") × 2 + 1到达 base case：
bin_to_dec("1") = 1开始返回：
bin_to_dec("11")
= 1 × 2 + 1
= 3bin_to_dec("110")
= 3 × 2 + 0
= 6bin_to_dec("1101")
= 6 × 2 + 1
= 13(d) Hexadecimal numbers to decimal numbers
Non-Recursive
# Non-Recursive
HEX_DIGITS = "0123456789ABCDEF"
def hex_to_dec(number):
answer = 0
for i in number:
value = HEX_DIGITS.index(i)
answer = answer * 16 + value
return answerRecursive
# Recursive
HEX_DIGITS = "0123456789ABCDEF"
def hex_to_dec(number):
# base case
if len(number) == 1:
return HEX_DIGITS.index(number)
# recursive case
return hex_to_dec(number[:-1]) * 16 + HEX_DIGITS.index(number[-1])(e) Binary numbers to hexadecimal numbers
Use Mapping:
since there are only 16 variations
HEX_DIGITS = "0123456789ABCDEF"
BINARY_NIBBLES = [
"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"
]
Non-Recursive
# Non-Recursive
# Mapping
HEX_DIGITS = "0123456789ABCDEF"
BINARY_NIBBLES = [
"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"
]
# Code
def bin_to_hex(number):
# Step 1: add leading zeroes
while len(number) % 4 != 0:
number = "0" + number
answer = ""
# Step 2: process four digits at a time
for i in range(0, len(number), 4):
nibble = number[i:i + 4]
# Step 3: convert the nibble into a value
# (value is a digit 0-15)
value = BINARY_NIBBLES.index(nibble)
# Step 4: convert the value into a hexadecimal digit
hex_digit = HEX_DIGITS[value]
# Step 5: add the digit to the answer
answer = answer + hex_digit
return answer
Trace "101101"
使用 bin_to_hex("101101") 作为 test case。
Step 1 — Add leading zeroes
"101101" 的 length 是 6，不是 4 的倍数，所以 while loop 在左边加入 leading zeroes：
101101 length 6
0101101 length 7
00101101 length 8现在 8 % 4 == 0，所以 while loop 停止，number 是 "00101101"。
Step 2 — Initialise the accumulator
answer = ""answer 是 accumulator，用来逐个储存转换完成的 hexadecimal digits。
Step 3 — Process one nibble per iteration
for i in range(0, len(number), 4):此时相当于 range(0, 8, 4)，所以 i 依次是 0 和 4。number[i:i + 4] 从 index i 开始读取四个 digits；ending index 不包括在 slice 内。
| iteration | i | number[i:i + 4] | value | hex_digit | answer |
|---|---|---|---|---|---|
| 1 | 0 | "0010" | 2 | "2" | "2" |
| 2 | 4 | "1101" | 13 | "D" | "2D" |
First iteration：
number = 0 0 1 0 1 1 0 1
index 0 1 2 3 4 5 6 7
└─────┘
"0010"
BINARY_NIBBLES.index("0010") = 2
HEX_DIGITS[2] = "2"
answer = "" + "2" = "2"Second iteration：
BINARY_NIBBLES.index("1101") = 13
HEX_DIGITS[13] = "D"
answer = "2" + "D" = "2D"Final result
101101₂ → 0010 1101₂ → 2D₁₆因此 return answer 返回 "2D"。
Recursive
# Recursive
HEX_DIGITS = "0123456789ABCDEF"
BINARY_NIBBLES = [
"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"
]
def bin_to_hex_recursive(number):
# base case
if len(number) <= 4:
nibble = number.zfill(4) # zfill(4) add leading 0
value = BINARY_NIBBLES.index(nibble)
return HEX_DIGITS[value]
# recursive case
previous_digits = number[:-4]
last_nibble = number[-4:]
value = BINARY_NIBBLES.index(last_nibble)
hex_digit = HEX_DIGITS[value]
return bin_to_hex_recursive(previous_digits) + hex_digit(f) Hexadecimal numbers to binary numbers
Non-Recursive
# Non-Recursive
# Mapping
HEX_DIGITS = "0123456789ABCDEF"
BINARY_NIBBLES = [
"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"
]
answer = "" # DONT FORGET THIS
def hex_to_bin(number):
for i in number:
value = HEX_DIGITS.index(i)
answer = answer + BINARY_NIBBLES[value]
return answerRecursive
# Recursive
HEX_DIGITS = "0123456789ABCDEF"
BINARY_NIBBLES = [
"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"
]
def hex_to_bin(number):
# base case
if len(number) == 1:
value = HEX_DIGITS.index(number)
return BINARY_NIBBLES[value]
# recursive case
previous_digits = number[:-1] # how it reduces to the base case by kicking out the last digit
last_digit = number[-1]
value = HEX_DIGITS.index(last_digit)
return hex_to_bin(previous_digits) + BINARY_NIBBLES[value]
Trace hex_to_bin("2AF")
Call 1
hex_to_bin("2AF")检查 base case：
len("2AF") == 1 # False执行 recursive case：
previous_digits = "2A"
last_digit = "F"
value = 15因此：
hex_to_bin("2AF")
= hex_to_bin("2A") + "1111"但 hex_to_bin("2A") 还没有答案，所以这个 function call 会在 call stack 中等待。
Call 2
hex_to_bin("2A")检查：
len("2A") == 1 # False执行：
previous_digits = "2"
last_digit = "A"
value = 10因此：
hex_to_bin("2A")
= hex_to_bin("2") + "1010"它也要等待 hex_to_bin("2") 的答案。
Call 3：到达 base case
hex_to_bin("2")检查：
len("2") == 1 # True所以：
value = HEX_DIGITS.index("2") # 2
return BINARY_NIBBLES[2] # "0010"现在不再产生新的 recursive call，开始返回答案。
从 call stack 返回
hex_to_bin("2") 返回：
"0010"所以等待中的 hex_to_bin("2A") 可以完成：
hex_to_bin("2A")
= hex_to_bin("2") + "1010"
= "0010" + "1010"
= "00101010"然后最外层也可以完成：
hex_to_bin("2AF")
= hex_to_bin("2A") + "1111"
= "00101010" + "1111"
= "001010101111"最终答案：
hex_to_bin("2AF") # "001010101111"整个过程的简写
hex_to_bin("2AF")
= hex_to_bin("2A") + "1111"
= hex_to_bin("2") + "1010" + "1111"
= "0010" + "1010" + "1111"
= "001010101111"