Elias omega编码:编码

Question

背景

Elias omega编码是一种通用代码，它可以将任意大小的正整数编码成一个比特流。

给定正整数N，编码算法如下：

1. 从输出中的单个零开始。
2. 如果N=1，停下来。
3. 将N的二进制数字准备到当前输出。
4. 让N是刚才加在前面的数字，减去1。回到第二步。

在类似Python的伪代码中：

n = input()
s = "0"
while n > 1:
    # bin(n) is assumed to give a plain string of bits, without "0b" prefix
    s = bin(n) + s
    n = len(bin(n)) - 1
output(s)

Illustration

数字1被编码到一个0中。

数字21以块的形式编码到10100101010或10 100 10101 0中，其中每个块按以下顺序添加到输出流中:首先默认情况下为"0“，然后是二进制的21，然后是4(位长为21减去1)，然后是2，然后停止。

任务

给定一个正整数N，输出它的Elias代码。

您可以以任何方便的格式获取输入数字N，包括其二进制表示形式。

输出必须是平坦的位流的有效表示形式，其中包括：

• 普通字符串或0和1的数组，或
• 二进制表示对应于比特流的单个整数。

不允许反向输出比特或输出嵌套位结构(例如，["10", "100", "10101", "0"]用于21)。

以字节为单位的最短代码获胜。

测试用例

N     => Omega(N)
1        0
2        100
3        110
4        101000
5        101010
6        101100
7        101110
8        1110000
12       1111000
16       10100100000
21       10100101010
100      1011011001000
345      1110001010110010
1000     11100111111010000
6789     11110011010100001010
10000    111101100111000100000
1000000  1010010011111101000010010000000

这是OEIS A281193。

Answer 1

JavaScript (ES6)，50字节

与.toString(2)

f=(n,s=0,b=n.toString(2))=>n-1?f(b.length-1,b+s):s

在网上试试！

无

.toString(2)

f=(n,i,q=n*2>>i)=>n>!!i?q?f(n,-~i)+q%2:f(i-2,1):''

在网上试试！

Answer 2

红宝石，39字节

f=->n,s=?0{n>1?f[/.$/=~x="%b"%n,x+s]:s}

在网上试试！

将N作为整数的递归函数。regex匹配返回N二进制表示中的最后一个位的索引，它比N的位长少一个。

Answer 3

Scala，74字节

x=>{var n->r=x->"0";while(n>1){val b=n.toBinaryString;r=b+r;n=b.size-1};r}

在网上试试！

这有点令人尴尬:命令式版本缩短了13字节。

Scala，87个字节

Seq.unfold(_){n=>val b=n.toBinaryString;Option.when(n>1)(b,b.size-1)}./:("0")(_.++:(_))

在网上试试！