圖片中題目的代碼中位運(yùn)算的部分不理解。

7的二進(jìn)制為111
5的二進(jìn)制為101

(i&(7<<j)) 是找到i的第j位到第j+1位上的01情況
5<<j是找到5左移j位后的01情況

(i&(7<<j))^(5<<j) 是判斷i的第j位到第j+1位是不是101

使用7<<j保留有效的3個(gè)檢查位（循環(huán)，一位一位檢查)，如果有則(i & (7 << j)為<n-3-j個(gè)0>101<j個(gè)0>，舉個(gè)例子：
n=7, i=44, j=3的場(chǎng)景：

i（被檢查數(shù)）:                00101100
7<<j:                        00111000
i & (7<<j):                  00101000
5<<j:                        00101000
((i & (7 << j)) ^ (5 << j)): 00000000 // == 0

提供一個(gè)更側(cè)重?cái)?shù)學(xué)分析的思路，可縮短運(yùn)行時(shí)間至O(lg n)。記fx(n) = 長(zhǎng)度為n的01串個(gè)數(shù)，且這些01串(1)不含101；(2)結(jié)尾為x，x=(00,01,10,11)。通過觀察可以得到遞推關(guān)系：

• 以00結(jié)尾：f0(n+1) = f0(n) + f2(n)
• 以01結(jié)尾：f1(n+1) = f0(n)
• 以10結(jié)尾：f2(n+1) = f1(n) + f3(n)
• 以11結(jié)尾：f3(n+1) = f1(n) + f3(n)

因此從初始值

f(2) = (f0(2), f1(2), f2(2), f3(2))' = (1, 1, 1, 1)'

通過計(jì)算矩陣乘方可以推出：

f(n) = M^(n-2) * f(2)

其中

M = 1    0    1    0
    1    0    0    0
    0    1    0    1
    0    1    0    1

耗時(shí)集中在計(jì)算M^n。用遞歸可以節(jié)省大量時(shí)間，比如計(jì)算M^8 = M^2^2^2，即復(fù)雜度為O(lg n)。

還可以進(jìn)一步將M對(duì)角化，得到一個(gè)復(fù)對(duì)角矩陣。如果編程語言或庫(kù)函數(shù)支持復(fù)數(shù)的話，甚至可將復(fù)雜度降低到O(1)。

void main()
{
 int match;
 int n;
 scanf("%d", &n);

 int count = 0;
 // < 1<<n  ,若n= 4,則遍歷所有小于10000的數(shù)據(jù)
 for (int i = 0; i < (1 << n); i ++)
 {
  match = 0;
  // 與101 匹配，至少要三位
  for (int j = 0; j <= n - 3; j++)
  {
      // 若 滿足該等式，認(rèn)為匹配。 ^ 相同為0，不同為1。
      // 這里的意思就是一位一位的左移，判斷您是否有匹配的，如果有匹配的就match = 1
      // 這個(gè)是在i中去三位連續(xù)數(shù)據(jù)  形如 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 ++;
 }