有效位在计数的情况下
Effective bit-on in counting the number of case
我在想bit-on是如何计算case数量的
情况
检查 n 个可能的 n/2 个案例。
我的方法
布尔可能（整数状态）
是状态下计数'1'的函数。如果 cnt 等于 n/2 return true，或 return 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() 函数是无效的，因为它搜索了整个案例。有什么有效的方法可以解决这个问题吗？
BIT-ON的含义
例如，如果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 上，这应该 运行 就好了。它可以是 "improved" 虽然通过使用位掩码而不是索引作为参数。但是，代码变得更难理解。
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"s). It doubles as a counter for remaining "1”还有足够的空间。
位-twiddling-hack
我突然想到，不用递归也可以解决这个问题：
从最小的数字开始，循环寻找下一个更大的数字。
要找到更大的数字，您需要将“1”移动到左侧下一个“0”的位置，然后将所有“1"s that are on the right of your new "1”移动到最右侧。
虽然这听起来很复杂，但可以使用 bit-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.
时中止循环
我在想bit-on是如何计算case数量的
情况
检查 n 个可能的 n/2 个案例。
我的方法
布尔可能（整数状态）
是状态下计数'1'的函数。如果 cnt 等于 n/2 return true，或 return 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() 函数是无效的，因为它搜索了整个案例。有什么有效的方法可以解决这个问题吗？
BIT-ON的含义
例如，如果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 上，这应该 运行 就好了。它可以是 "improved" 虽然通过使用位掩码而不是索引作为参数。但是，代码变得更难理解。
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"s). It doubles as a counter for remaining "1”还有足够的空间。
位-twiddling-hack
我突然想到，不用递归也可以解决这个问题：
从最小的数字开始，循环寻找下一个更大的数字。 要找到更大的数字，您需要将“1”移动到左侧下一个“0”的位置，然后将所有“1"s that are on the right of your new "1”移动到最右侧。
虽然这听起来很复杂，但可以使用 bit-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.