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。系统形成练习 = 10101 -> 10021 ； 10021 -> 02021 -> 01221

但是，可能有更有效的解决方案，可以将练习中的十进制直接转换为系统。我非常感谢您帮助找到算法思维路径。然后我会自己编写代码以确保我理解它。

这是我在论坛上的第一篇文章，英语不是我的母语。如果我没有表达得足够清楚，我很抱歉。

亲切的问候

Answer 1

让n成为我们想要表示的数字。数字c必须满足

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

通过检查，这些范围对自然数进行了划分，因此唯一的解决方案是c = ⌊log₂ (n+1)⌋ 。通常可以使用单个指令来计算楼层日志，或者您可以使用 bit-twiddling hack .

一旦我们知道c，我们只需找到n的通常二进制表示 - (2⁰ + 2¹ + … + 2^c−1) = n − (2^c − 1) 且每个数字加一。