从 1 到 n 的数的集合位之和至少为 k
Sum of set bits of numbers from 1 to n is atleast k
找到最小的N，使得从1到N的数字的集合位之和至少为k。
例如
k = 11, output N = 7, as SB(1) + SB(2) + .. +SB(7) = 12
k = 5, output N = 4, as SB(1) + SB(2) +..+SB(4) = 5
我想首先通过存储设置位的总和然后应用二进制搜索至少 k 来解决它。但是，这里的问题是 1 <= k <= 10^18。所以显然DP是不能用的。那么如何解决这个问题。时间限制为 1.5 秒
假设您的电话号码是 13。在二进制中，它是 1101。让我们 table 看看我们是否能看到规律。我将插入一些换行符以供稍后使用。此外，我将添加 0，因为它没有伤害（它没有设置位）。
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1011
我们可以这样写n下的所有组：
000
001
010
011
100
101
110
111
1000 + 00
1000 + 01
1000 + 10
1000 + 11
1000 + 100 + | (no digits, equal to 0 in sum)
请注意，n=1101 的第 3 位我们有一组大小为 2^3 的组；我们有一组大小为 2^2 的第二位；和 LSB 的一组大小 2^0。我们称组大小为 s=2^b，其中 b 是 n 中所有设置位的位置（即 b=[3, 2, 0], s=[8, 4, 1]）。注意每组中最右边的被加数的位模式：有 b 列位，并且在每一列中恰好设置了 s/2 ；因此，对于每个设置位，最右边的列中有 2^(b-1)*b 个设置位。但是每一行也有等于组的序号的设置位数：0、1、2（当我们添加对应于 n 中的设置位的组时），总计 2^b*i + 2^(b-1)*b 设置每组位数：
Group 0: 2^3*0 + 2^2*3 = 12
Group 1: 2^2*1 + 2^1*2 = 8
Group 2: 2^0*2 + 2^(-1)*0 = 2
这是所有设置位的数量，最多 n-1。要获取 n 的位数，我们需要为 n 本身中设置的每个位再获取一位 - 这正是我们拥有的组数。因此总数是 12+8+2 +3 = 25.
这里是 Ruby。请注意 2^x * y 等同于 y << x.
def sum_bits_upto(n)
set_bits = n.to_s(2).reverse.each_char.with_index.map { |c, b|
b if c == "1"
}.compact.reverse
set_bits.each_with_index.sum { |b, i|
(i << b) + (b << b - 1) + 1
}
end
希望我没有在任何地方搞砸我的逻辑。顺便说一句，我的代码说从 1 到 1_000_000_000_000_000_000 有 29761222783429247000 位，循环只有 24 次迭代。那应该够快了:)
编辑：显然我有金鱼记忆。总和单调递增（对于每个连续的数字，运行 总数中添加了正数的位数）。这意味着，我们可以使用二进制搜索，即使我们不通过存储临时结果来帮助它，它也应该在目标上快速归零（这在我的 Mac 上以 0.1 秒执行）：
max = 1_000_000_000_000_000_000_000_000_000
k = 1_000_000_000_000_000_000
n = (1..max).bsearch { |n|
sum_bits_upto(n) >= k
}
# => 36397208481162321
必须有一个很好的公式来计算理论上可能的最大 n 以基于 k 搜索，但我懒得理会，所以我只是输入了足够大的东西。 bsearch就是这么好
EDIT2：bsearch 条件的一些调整，一开始搞砸了。
在Amadan的答案之后贴出我的答案，因为它带来了关于计算设置为N的位数的不同观点；问题的解决是通过二进制搜索进行的，这是合适的，因为位集计算很便宜
让我们看看 N 是 2 的幂，比如 8
dcba
----
000
001
010
011
100
101
110
111
1000
在 a 列中，我们交替使用 1 和 0，在 b 列中，相同但每个两个 (21) 个数字，在 c 中每四个 (22) 个数字。
无论如何，我们在每一列中得到相同数量的 1，N/2。因此，1 的 2 次方数是（+1 为 2 本身的次方）
log2(N) * N/2 + 1
任何整数都是 2 的幂之和，比如 13
1000 + 0100 + 0001
1到N的个数是上述等式N的所有2次方中每一个的总和，在每个次方的左边加上1sx = 2P（因为 count 到那个幂，更高位的幂 > P 在那里）
bitsets = P * x/2 + 1 + x * number of bits set on the left to that power x
比如1310
1000 => 3 x 8/2 +1 = 13 + 0 (no 1 left)
0100 => 2 x 4/2 +1 = 5 + 4 x 1 (one bit on the left, the 8)
0001 => 0 x 1/2 +1 = 1 + 1 x 2 (the 8 and the 4)
有 25 1 最多 13。
计算速度O(log(N))，即使是 1018（大约 60 次迭代）也是如此。
二进制搜索将在 O(log2) 中工作，找到最大值 k 是从 1 开始设置的位数1018以上的2的次方，可以用上面的公式计算出来。
喜欢这个问题，所以花了一些时间来编码。
Python 下面的代码适用于位位置，因此复杂性限于 10^18 中存在的最大位数。
# Store sum of 1-bits upto max number formed by N bits.
# For example - sumToNBits of 1 bit is 1, 2 bit numbers 01,10,11 is 4 and 3 bit
# numbers 01,10,11,100,101,110,111 is 12
# and so on.
sumToNBits = []
prevSum = 0
for i in range(1, 65):
prevSum = (1 << (i-1)) + 2*prevSum
sumToNBits.append(prevSum)
# Find maximum possible number (2 to power P - 1) which has sum of 1-bits up to K.
def findClosestPowerTwo(K):
index = 1
prevEntry = 0
for entry in sumToNBits:
if (entry > K):
return (K-prevEntry, index-1)
prevEntry = entry
index += 1
return (K-prevEntry, index-1)
# After finding max 2 to power P, now increase number up to K1 = K - bits used by 2 to power P.
def findNextPowerTwo(K, onBits):
index = 1
prevTotalBits = 0
totalBits = onBits * ((1 << index) - 1) + sumToNBits[index-1]
while(K >= totalBits):
prevTotalBits = totalBits
index += 1
totalBits = onBits * ((1 << index) - 1) + sumToNBits[index-1]
return (K-prevTotalBits, index-1)
def findClosestNumber(K):
(K, powerTwo) = findClosestPowerTwo(K)
number = (1 << (powerTwo)) - 1
# Align to 2 to power P
if (K >= 1):
K = K - 1
number += 1
onBits = 1
while(K > 0):
(K, powerTwo) = findNextPowerTwo(K, onBits)
if (powerTwo == 0):
return number+1
number += ((1 << (powerTwo)) - 1)
# Align to 2 to power P
if (K >= (onBits + 1)):
K = K - (onBits + 1)
number += 1
onBits += 1
return number
num = 1
while num < 100:
print(num, end = " ")
print(findClosestNumber(num))
num += 1
找到最小的N，使得从1到N的数字的集合位之和至少为k。
例如
k = 11, output N = 7, as SB(1) + SB(2) + .. +SB(7) = 12
k = 5, output N = 4, as SB(1) + SB(2) +..+SB(4) = 5
我想首先通过存储设置位的总和然后应用二进制搜索至少 k 来解决它。但是，这里的问题是 1 <= k <= 10^18。所以显然DP是不能用的。那么如何解决这个问题。时间限制为 1.5 秒
假设您的电话号码是 13。在二进制中，它是 1101。让我们 table 看看我们是否能看到规律。我将插入一些换行符以供稍后使用。此外，我将添加 0，因为它没有伤害（它没有设置位）。
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1011
我们可以这样写n下的所有组：
000
001
010
011
100
101
110
111
1000 + 00
1000 + 01
1000 + 10
1000 + 11
1000 + 100 + | (no digits, equal to 0 in sum)
请注意，n=1101 的第 3 位我们有一组大小为 2^3 的组；我们有一组大小为 2^2 的第二位；和 LSB 的一组大小 2^0。我们称组大小为 s=2^b，其中 b 是 n 中所有设置位的位置（即 b=[3, 2, 0], s=[8, 4, 1]）。注意每组中最右边的被加数的位模式：有 b 列位，并且在每一列中恰好设置了 s/2 ；因此，对于每个设置位，最右边的列中有 2^(b-1)*b 个设置位。但是每一行也有等于组的序号的设置位数：0、1、2（当我们添加对应于 n 中的设置位的组时），总计 2^b*i + 2^(b-1)*b 设置每组位数：
Group 0: 2^3*0 + 2^2*3 = 12
Group 1: 2^2*1 + 2^1*2 = 8
Group 2: 2^0*2 + 2^(-1)*0 = 2
这是所有设置位的数量，最多 n-1。要获取 n 的位数，我们需要为 n 本身中设置的每个位再获取一位 - 这正是我们拥有的组数。因此总数是 12+8+2 +3 = 25.
这里是 Ruby。请注意 2^x * y 等同于 y << x.
def sum_bits_upto(n)
set_bits = n.to_s(2).reverse.each_char.with_index.map { |c, b|
b if c == "1"
}.compact.reverse
set_bits.each_with_index.sum { |b, i|
(i << b) + (b << b - 1) + 1
}
end
希望我没有在任何地方搞砸我的逻辑。顺便说一句，我的代码说从 1 到 1_000_000_000_000_000_000 有 29761222783429247000 位，循环只有 24 次迭代。那应该够快了:)
编辑：显然我有金鱼记忆。总和单调递增（对于每个连续的数字，运行 总数中添加了正数的位数）。这意味着，我们可以使用二进制搜索，即使我们不通过存储临时结果来帮助它，它也应该在目标上快速归零（这在我的 Mac 上以 0.1 秒执行）：
max = 1_000_000_000_000_000_000_000_000_000
k = 1_000_000_000_000_000_000
n = (1..max).bsearch { |n|
sum_bits_upto(n) >= k
}
# => 36397208481162321
必须有一个很好的公式来计算理论上可能的最大 n 以基于 k 搜索，但我懒得理会，所以我只是输入了足够大的东西。 bsearch就是这么好
EDIT2：bsearch 条件的一些调整，一开始搞砸了。
在Amadan的答案之后贴出我的答案，因为它带来了关于计算设置为N的位数的不同观点；问题的解决是通过二进制搜索进行的，这是合适的，因为位集计算很便宜
让我们看看 N 是 2 的幂，比如 8
dcba
----
000
001
010
011
100
101
110
111
1000
在 a 列中，我们交替使用 1 和 0，在 b 列中，相同但每个两个 (21) 个数字，在 c 中每四个 (22) 个数字。
无论如何，我们在每一列中得到相同数量的 1，N/2。因此，1 的 2 次方数是（+1 为 2 本身的次方）
log2(N) * N/2 + 1
任何整数都是 2 的幂之和，比如 13
1000 + 0100 + 0001
1到N的个数是上述等式N的所有2次方中每一个的总和，在每个次方的左边加上1sx = 2P（因为 count 到那个幂，更高位的幂 > P 在那里）
bitsets = P * x/2 + 1 + x * number of bits set on the left to that power x
比如1310
1000 => 3 x 8/2 +1 = 13 + 0 (no 1 left)
0100 => 2 x 4/2 +1 = 5 + 4 x 1 (one bit on the left, the 8)
0001 => 0 x 1/2 +1 = 1 + 1 x 2 (the 8 and the 4)
有 25 1 最多 13。
计算速度O(log(N))，即使是 1018（大约 60 次迭代）也是如此。
二进制搜索将在 O(log2) 中工作，找到最大值 k 是从 1 开始设置的位数1018以上的2的次方，可以用上面的公式计算出来。
喜欢这个问题，所以花了一些时间来编码。 Python 下面的代码适用于位位置，因此复杂性限于 10^18 中存在的最大位数。
# Store sum of 1-bits upto max number formed by N bits.
# For example - sumToNBits of 1 bit is 1, 2 bit numbers 01,10,11 is 4 and 3 bit
# numbers 01,10,11,100,101,110,111 is 12
# and so on.
sumToNBits = []
prevSum = 0
for i in range(1, 65):
prevSum = (1 << (i-1)) + 2*prevSum
sumToNBits.append(prevSum)
# Find maximum possible number (2 to power P - 1) which has sum of 1-bits up to K.
def findClosestPowerTwo(K):
index = 1
prevEntry = 0
for entry in sumToNBits:
if (entry > K):
return (K-prevEntry, index-1)
prevEntry = entry
index += 1
return (K-prevEntry, index-1)
# After finding max 2 to power P, now increase number up to K1 = K - bits used by 2 to power P.
def findNextPowerTwo(K, onBits):
index = 1
prevTotalBits = 0
totalBits = onBits * ((1 << index) - 1) + sumToNBits[index-1]
while(K >= totalBits):
prevTotalBits = totalBits
index += 1
totalBits = onBits * ((1 << index) - 1) + sumToNBits[index-1]
return (K-prevTotalBits, index-1)
def findClosestNumber(K):
(K, powerTwo) = findClosestPowerTwo(K)
number = (1 << (powerTwo)) - 1
# Align to 2 to power P
if (K >= 1):
K = K - 1
number += 1
onBits = 1
while(K > 0):
(K, powerTwo) = findNextPowerTwo(K, onBits)
if (powerTwo == 0):
return number+1
number += ((1 << (powerTwo)) - 1)
# Align to 2 to power P
if (K >= (onBits + 1)):
K = K - (onBits + 1)
number += 1
onBits += 1
return number
num = 1
while num < 100:
print(num, end = " ")
print(findClosestNumber(num))
num += 1