I am trying to implement Double Dabble to convert binary to BCD and back, but it doesn't work. I understand the steps but somehow I can't make it work. First I initialize a list of length (n.bit_length() + 2) // 3 and fill with 0s, each element is used to represent a single decimal digit. Because there are ten decimal digits, 4 binary bits are needed. So I first shift the lowest digit by 1 and set the last bit to ith bit of n from the left. This is simple enough, the digit requires a carry if and only if the digit is greater than or equal to 8. I use bitwise-AND with 15 to get the least significant four bits of the digit, and then if the digit is greater than or equal to 5, add 3. I do this branchlessly by indexing [0, 1, 2, 3, 4, 8, 9, 10, 11, 12]. Now this procedure needs to happen for all the digits if there is a carry, I just repeatedly do the same procedure while there needs to be a carry. BCD = [0, 1, 2, 3, 4, 8, 9, 10, 11, 12] def double_dabble(n: int) -> list[int]: if n == 0: return [0] bits = n.bit_length() digits = [0] * ((bits + 2) // 3) for i in range(bits - 1, -1, -1): one = digits[0] carry = one >= 8 digits[0] = BCD[((one << 1) | ((n >> i) & 1)) & 15] j = 1 while carry: place = digits[j] digits[j] = BCD[((place << 1) + 1) & 15] carry = place >= 8 j += 1 return digits My code doesn't work and I have no idea how to fix it. How can I fix my code? Example: In [355]: double_dabble(123456789) Out[355]: [12, 8, 1, 3, 0, 0, 0, 0, 0] Expected output: [9, 8, 7, 6, 5, 4, 3, 2, 1] Continue reading...
