图片中题目的代码中位运算的部分不理解。

Question

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组合,但是不理解是如何得出的，在纸上硬算发现也不对头。求解答

Answer 1

使用7<<j保留有效的3个检查位（循环，一位一位检查)，如果有则(i & (7 << j)为<n-3-j个0>101<j个0>，举个例子：
n=7, i=44, j=3的场景：

i（被检查数）:                00101100
7<<j:                        00111000
i & (7<<j):                  00101000
5<<j:                        00101000
((i & (7 << j)) ^ (5 << j)): 00000000 // == 0

Answer 2

提供一个更侧重数学分析的思路，可缩短运行时间至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)。

Answer 3

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 ++;
 }

Answer 4

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