@[幻想繁星](/user/649095) 高精度十进制输入吗？
by critnos @ 2024-03-09 20:29:54
@[critnos](/user/203623) 假设数的操作都是 $O(1)$ 的。
by 幻想繁星 @ 2024-03-09 20:48:38
@[critnos](/user/203623) 乘方应该被认为是log 的
by 幻想繁星 @ 2024-03-09 20:53:34
呃呃呃如果数的操作包含 `__builtin_clz` 就直接结束了，否则直接倍增是不是更优。也许可以先从小到大倍增得到一个上界，然后再从上界从大到小枚举，$O(\log\log n)$。
by yukimianyan @ 2024-03-09 20:53:37
@[yukimianyan](/user/509229) 倍增怎么做到怎么快的？我算的 $O(\log^2 \log n)$
by 幻想繁星 @ 2024-03-09 21:00:38
@[幻想繁星](/user/649095) 提供一个 $\mathcal O(\log \log n)$ 的做法。假设内存访问是 $\mathcal O(1)$ 的。
令 `WIDTH` 为整数类型的二进制宽度，例如 `int` 是 $32$ 位宽，`long long` 是 $64$ 位宽。假设 `WIDTH` 是 2 的幂。
令 `LOGWIDTH` 为 `WIDTH` 的对数，以 2 为底。例如 `int` 就是 $5$ 而 `long long` 就是 $6$。显然 `LOGWIDTH` 就是 $\log \log V$ 级别（$V$ 是值域）。
先
```
x |= x >> (1 << 0);
x |= x >> (1 << 1);
x |= x >> (1 << 2);
x |= x >> (1 << 3);
x |= x >> (1 << 4); // 到 LOGWIDTH - 1 为止
```
这样这个数变成 000000011111111 这样，就是右边全都是 1。
然后加上 1：`x = x + 1`。
这个时候变成求一个 2 的次幂到底是几次幂，用 de Bruijn 序列即可：
> $n$ 阶 de Bruijn 序列是长度为 $2^n$ 的 01 序列，满足其从任意位置往右数连续 $n$ 位都能组成不同的 $n$ 位 01 串（从最右端往右数的时候补 0），且最左端的 $n$ 个字符均为 0。
>
> 例如 3 阶 de Bruijn 序列的例子有 00010111。写成十进制数是 23。
考虑将这个 2 的次幂乘以某个 de Bruijn 序列，这相当于把 de Bruijn 序列左移若干位（溢出的就不管了）。然后提取最左侧的 $n$ 位时，查表就可以知道左移了多少位。
这个查表的表需要预先处理。
写成代码大概是 `return table[(x * magic_number) >> ((1 << n) - n)]`。
by 小粉兔 @ 2024-03-09 21:13:14
变到“求一个 2 的次幂到底是几次幂”这一步之后，也可以直接硬编码二分。后面就也是 $\mathcal O(\log \log V)$
by 小粉兔 @ 2024-03-09 21:14:48
@[小粉兔](/user/10703) thx
by 幻想繁星 @ 2024-03-09 21:18:50