我想知道在计算案例数时如何位。
SITUAITION
检查整个可能的 N/2 例。
我的方法
布尔可能(整数状态)
它是在状态中计数"1"的函数。 如果 CNT 等于 N/2，则返回 true，或返回 false。
inline bool possible(int state){
int cnt=0;
for(int t=1;;t*=2){
if(t==(1<<n)) break;
if(cnt>n/2) break;
if((t&state)==t) ++cnt;
}
if(cnt==n/2) return true;
else return false;
}
无效查询()
它搜索所有可能的状态。
inline void query(){
int tar=n/2;
int ss=(1<<tar)-1;
int ee=(1<<n)-1;
for(int i=ss;i<=ee;++i){
if(possible(i)) process(i);
}
}
我想使用位掩码来解决 n 的整个可能的 n/2 种情况。 但我认为 query() 函数是无效的，因为它搜索整个案例。有没有有效的方法来解决这个问题？
位上的含义
例如，如果 n=4，那么我们必须位上两个索引， 在从 0 开始的索引中，
0001 [失败]
0010 [失败]
0011 [0,1 位的索引]
0100 [失败]
0101 [0,2 位的索引]
0110 [1,2 位的索引]
0111 [失败]
1000 [失败]
1001 [0,3 位的索引]
1010 [1,3 位的索引]
1011 [失败]
1100 [2,3 位的索引]
1101 [失败]
1110 [失败]
1111 [失败]
显然，选择了 4C2=6 个案例，所以状态，
[0011， 0101， 0110，1001， 1010， 1100]将被检索。
这个问题可以递归解决
- 首先，您选择最左边的"1"的位置
- 然后递归调用该函数以放置剩余的"1">
- 当没有"1"可以放置时，递归结束
这意味着您需要定义一个更通用的函数，该函数在n位数中生成k"1"。
避免返回和处理子结果的一个方便技巧是向下传递累加器。您可以在递归的深层调用process()函数。
Python 中的示例代码。应该很容易翻译成 C。
def process(i):
'''prints decimal and binary representation of i'''
print(i, bin(i))
def helper1(length, ones, acc):
if ones == 0:
process(acc)
else:
for i in range(ones-1, length): # iterates from ones-1 to length-1
helper1(i, ones-1, acc | (1<<i))
def solution1(n):
helper1(n, n >> 1, 0)
在现代 CPU 上，这应该运行良好。不过，可以通过使用位掩码而不是索引作为参数来"改进"。但是，代码变得更加难以理解。
def helper2(first_mask, last_mask, acc):
if last_mask == 0:
process(acc)
else:
mask = last_mask
while mask <= first_mask:
helper2(mask >> 1, last_mask >> 1, acc | mask)
mask = mask << 1
def solution2(n):
helper2(1 << (n-1), 1 << (n//2 -1), 0)
first_mask表示可以插入"1"的最左侧位置last_mask表示可以插入"1"的最右侧位置(以便仍然有足够的空间容纳剩余的"1")。它兼作剩余"1"的计数器。
比特叽叽喳喳的黑客
我只是想到你也可以在没有递归的情况下解决问题：
从最小的数字开始，然后在循环中找到下一个较大的数字。 要找到更大的数字，您需要将"1"移动到左侧下一个"0"的位置，然后将新"1"右侧的所有"1"移动到最右侧。
虽然这听起来很复杂，但可以使用比特-twiddling-hacks快速完成。
def helper3(total, ones):
if ones == 0:
process(0)
return
i = (1 << ones) - 1
while i < (1 << total):
process(i)
last_one_mask = (((i - 1) ^ i) >> 1) + 1
temp = i + last_one_mask
i = temp | (((temp ^ i) // last_one_mask) >> 2)
def solution3(n):
helper3(n, n >> 1)
如果您的语言具有恒定宽度整数，则在计算temp时可能会出现溢出。为避免不良行为，您必须中止循环，如果temp<i。