图片中题目的代码中位运算的部分不理解。
void main(){
int match;
int n;
scanf("%d", &n);
int count = 0;
for (int i = 0; i < (1 << n); i ++)
{
match = 0;
for (int j = 0; j <= n - 3; j++)
{
if (((i & (7 << j)) ^ (5 << j)) == 0) // bin(7)=111; bin(5)=101
{
match = 1;
break;
}
}
if (match == 0)
count ++;
}
if (((i & (7 << j)) ^ (5 << j)) == 0) 这部分^(5<<j)这个我是理解的,比较各个位置的101.但是前面i&(7<<j)这部分猜想是2^n个10组合,但是不理解是如何得出的,在纸上硬算发现也不对头。求解答
回答:
使用7<<j
保留有效的3个检查位(循环,一位一位检查),如果有则(i & (7 << j)
为<n-3-j个0>101<j个0>
,举个例子:
n=7, i=44, j=3的场景:
i(被检查数): 001011007<<j: 00111000
i & (7<<j): 00101000
5<<j: 00101000
((i & (7 << j)) ^ (5 << j)): 00000000 // == 0
回答:
提供一个更侧重数学分析的思路,可缩短运行时间至O(lg n)。记fx(n) = 长度为n的01串个数,且这些01串(1)不含101;(2)结尾为x,x=(00,01,10,11)。通过观察可以得到递推关系:
- 以00结尾:
f0(n+1) = f0(n) + f2(n)
- 以01结尾:
f1(n+1) = f0(n)
- 以10结尾:
f2(n+1) = f1(n) + f3(n)
- 以11结尾:
f3(n+1) = f1(n) + f3(n)
因此从初始值
f(2) = (f0(2), f1(2), f2(2), f3(2))' = (1, 1, 1, 1)'
通过计算矩阵乘方可以推出:
f(n) = M^(n-2) * f(2)
其中
M = 1 0 1 0 1 0 0 0
0 1 0 1
0 1 0 1
耗时集中在计算M^n。用递归可以节省大量时间,比如计算M^8 = M^2^2^2,即复杂度为O(lg n)。
还可以进一步将M对角化,得到一个复对角矩阵。如果编程语言或库函数支持复数的话,甚至可将复杂度降低到O(1)。
回答:
void main(){
int match;
int n;
scanf("%d", &n);
int count = 0;
// < 1<<n ,若n= 4,则遍历所有小于10000的数据
for (int i = 0; i < (1 << n); i ++)
{
match = 0;
// 与101 匹配,至少要三位
for (int j = 0; j <= n - 3; j++)
{
// 若 满足该等式,认为匹配。 ^ 相同为0,不同为1。
// 这里的意思就是一位一位的左移,判断您是否有匹配的,如果有匹配的就match = 1
// 这个是在i中去三位连续数据 形如 11101 & (7 << 0) 就是 最后三位101, 11101 & (7 << 1) 就是110 ,然后与101比较。
if (((i & (7 << j)) ^ (5 << j)) == 0) // bin(7)=111; bin(5)=101
{
match = 1;
break;
}
}
if (match == 0)
count ++;
}
回答:
7的二进制为111
5的二进制为101
(i&(7<<j))
是找到i的第j位到第j+1位上的01情况5<<j
是找到5左移j位后的01情况
(i&(7<<j))^(5<<j)
是判断i的第j位到第j+1位是不是101
以上是 图片中题目的代码中位运算的部分不理解。 的全部内容, 来源链接: utcz.com/p/194848.html