algorithm - 查找从 0 到 (2^n) - 1 的总设置位

Question

让我们将 F(n) 定义为

F(n) = total set bits in binary representation of 0 to (2^n) -1.

Eg:

F(1) = number of bits set in 0 + number of bits set in 1 = 1
F(2) = number of bits set in 0 + ...... number of bits set in 3 = 4

是否有 O(log n) 算法来计算 F(n)，其中 n 可以大到 10^6。

Answer 1

^{如果您要询问在从 0 到 2 n} –1的所有整数的二进制表示中设置的位数，这很简单：

1. 这样的数字有n位。
2. 有 2 ^{n 个}这样的数字。
3. 每个位值都设置为该集合数字的一半。
4. 设置的位数是总位数的一半。
5. 设置位数为n × 2 ⁿ ÷ 2 = n × 2 ^{n –1}。

请记住在你的作业中引用这个网页：v）。

Answer 2

我闻到作业的味道，所以我省略了代码

一个简单的解决方案，使用对于第 i 个最低有效位的事实，答案将是

(N/2^i)*2^(i-1)+ X
where X = N%(2^i) - (2^(i-1)-1) iff N%(2^i)>=(2^(i-1)-1)

考虑从 1 到 N 的数字的第 i 个最低有效位（基于 1 的索引），然后它们以等于 2^i 的周期重复。在周期中，值的前半部分为 0，下半部分为 1。对于示例：- 对于从 0 到 7 的数字，（0 不会产生任何影响，因此没有效果）

000
001
010
011
100
101
110
111
1st least significant bit = 01010101 Period=2
2nd least significant bit = 00110011 Period=4
3rd least significant bit = 00001111 Period=8
and so on.

So for the ith least significant bit ,answer will be (N/Period)*(Half of Period Size) + (N%(2^i - 1) - Half of Period Size + 1)
The second term will only be taken when N%Remainder is greater than or equal to Half of Period Size.
Also , N%(2^i) can be written as N&(2^i - 1)

礼貌：http ://www.geeksforgeeks.org