algorithm - 将十进制转换为只有两位数的二进制 : 1 and 2

Question

我的大学书上的练习有问题。这里是:

We are interested in a binary system representing positive integers with only two digits: 1 and 2 (no zeroes!). The subsequent positions correspond to the successive powers of the two, as in the usual binary notation: at the k-th position there is a digit whose value is multiplied by 2^k for k = 0, 1, 2... . In this system - as there are no leading zeros - in addition to formerly mentioned number representation, we use a value that specifies the number of selected digits, let's call it c. Each number is therefore represented by a pair (a, c), where a is a finite sequence of 1 and 2, and c determines the length of that sequence. For example, the pair (12, 3) represents the number 4, and the pair (221, 3) represents the number 13. Write a function which, for a positive number x, determines the representation of its value in the system in question and passes it through the parameter y. Let's agree that in case x is not positive, the value of field c should be 0.

我发现我可以轻松地将十进制输入转换为二进制系统，然后将二进制转换为练习中提到的系统。从右边开始，我需要通过将较高的数字 1 转换为较低的数字 2 来删除零。
例如:十进制 = 21。二进制 = 10101。系统形成练习 = 101 0 1 -> 10 02 1 ; 10 0 21 -> 02 021 -> 0 12 21
但是，可能有更有效的解决方案可以将十进制直接转换为练习中的系统。感谢您在寻找算法思维路径方面的帮助。然后我会自己编码以确保我理解它。
这是我在论坛上的第一篇文章，英语不是我的母语。如果我表达得不够清楚，我很抱歉。
亲切的问候

Answer 1

让 n 是我们试图表示的数字。数 c 必须满足

2⁰ + 2¹ + … + 2^c−1 = 2^c − 1 ≤ n ≤ 2^c+1 - 2 = 2 (2⁰ + 2¹ + … + 2^c−1).

通过检查，这些范围划分了自然数，因此唯一解是 c = ⌊log2 (n+1)⌋。 floor-log 通常可以用一条指令计算，或者你可以使用 bit-twiddling hack .
一旦我们知道了 c，我们只需要找到 n − (20 + 21 + … + 2c−1) = n − (2c − 1) 的通常二进制表示，并在每个数字上加一。