CGAC2022第9天:玩比特

Question

代码:高尔夫预告牌2022事件的一部分。有关详细信息，请参阅链接的元帖子。

精灵们喜欢玩数字游戏。有一天，斌(芬的一个朋友)提出了一个新的游戏:给定一个正整数n，每个Elf表示一个数字，它的n运行在二进制中。第一个精灵必须说最小的数，下一个精灵必须说最小的数大于最后一个。

任务

给定n，输出序列。

您可以使用任何序列 I/O方法：

• 给定n，无穷地输出相应的序列
• 给定n和索引k (可能是1-或0-索引)，按n的顺序输出k第四位数。
• 给定n和k，输出n序列的第一个k数

适用标准的密码-高尔夫规则。以字节为单位的最短代码获胜。

测试用例

n = 1
1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 16, 24, 28, 30, 31, 32, 48, 56, 60, 62, 63,
64, 96, 112, 120, 124, 126, 127, ...

n = 2
5, 9, 10, 11, 13, 17, 18, 19, 20, 22, 23, 25, 26, 27, 29, 33, 34, 35, 36, 38,
39, 40, 44, 46, 47, 49, 50, 51, 52, 54, 55, 57, 58, 59, 61, 65, 66, 67, 68, ...

n = 3
21, 37, 41, 42, 43, 45, 53, 69, 73, 74, 75, 77, 81, 82, 83, 84, 86, 87, 89,
90, 91, 93, 101, 105, 106, 107, 109, 117, ...

n = 4
85, 149, 165, 169, 170, 171, 173, 181, 213, 277, 293, 297, 298, 299, 301, 309,
325, 329, 330, 331, 333, 337, 338, 339, 340, 342, 343, 345, ...

n = 5
341, 597, 661, 677, 681, 682, 683, 685, 693, 725, 853, 1109, 1173, 1189, 1193,
1194, 1195, 1197, 1205, 1237, 1301, 1317, 1321, 1322, 1323, 1325, ...

n = 6
1365, 2389, 2645, 2709, 2725, 2729, 2730, 2731, 2733, 2741, 2773, 2901, 3413,
4437, 4693, 4757, 4773, 4777, 4778, 4779, 4781, 4789, 4821, 4949, 5205, ...

相应的OEIS序列是A023758 (不带前导0)、A043682、A043683、A043684、A043685和A043686。

Answer 1

帕里/GP，55字节

n->for(i=1,oo,sumdigits(bitxor(i,2*i),2)-2*n||print(i))

在网上试试！

无限地输出序列。

对于每个正整数i，如果\operatorname{bitxor}(i,2i)的二进制数字之和为2n，则打印它。

Answer 2

JavaScript (V8)，56字节

-2多亏了@dingledooper

无限地打印序列。其他版本也是如此。

使用[医]阿氏法更简单、更短。k \operatorname{XOR} 2\times k没有一个一个地递增每个运行，而是同时隔离所有的运行。

n=>{for(k=0;g=k=>k&&.5+g(k&k-1);)g(++k^2*k)-n||print(k)}

在网上试试！

JavaScript (V8)，61字节

n=>{for(k=0;g=k=>k&&k%2+g(++k/(k&-k)>>1);)g(++k)-n||print(k)}

在网上试试！

递归逻辑

下面是在g for k=441=110111001_2中发生的递归的一个例子，它有3次1‘S的运行：

 0110111001 | odd -> we have a first run of 1's
 0110111010 | increment
 011011101  | divide by (k & -k) --> remove the trailing zeros
 01101110   | right-shift by 1
------------+--------------------------------------------------
 01101110   | even -> this is not a run of 1's
 01101111   | increment
 01101111   | divide by (k & -k) --> no change here
 0110111    | right-shift by 1
------------+--------------------------------------------------
 0110111    | odd -> we have a 2nd run of 1's
 0111000    | increment
 0111       | divide by (k & -k) --> remove the trailing zeros
 011        | right-shift by 1
------------+--------------------------------------------------
 011        | odd -> we have a 3rd run of 1's
 100        | increment
 1          | divide by (k & -k) --> remove the trailing zeros
 0          | right-shift by 1
------------+--------------------------------------------------
 0          | stop

JavaScript (V8)，63字节

使用正则表达式的更长、更慢、更少乐趣的解决方案。

n=>{for(k=1;;k++)k.toString(2).split(/1+/).length+~n||print(k)}

在网上试试！

Answer 3

生锈，52字节

|j|(1u32..).filter(move|i|(i^i*2).count_ones()==j*2)

在网上试试！

使用xor技巧。可以通过使用u8和滥用“忽略数字限制”规则节省1个字节。