這題要以二進位來思考,
假設 A=100100010,
則滿足 A+B=A|B 條件的 B,
在 A 中為 1 的位元必定為 0,
也就是 B=0xx0xxx0x,
其中的 x 可為 0 或 1,
因此只要數一下 A 裡面有幾個位元是 0,
算出 2 的次方就可以得到答案。
但是題目又規定 B <=X ,
所以我們要將 X 分段處理,
假設 X=1001000100,
先找出最左邊第一個出現的 1 為 1000000000,
分出第一段數字 xxxxxxxxx,(不含上面的數)
也就是 0 ~ 111111111 (1000000000-1),
再用這一段去找有幾個位元在 A 中是 0。
接下來再找出第二個出現的 1 為 1000000,
而第二段數字為 1000xxxxxx,
也就是 1000000000 ~ 1000111111 (1001000000-1),
數字的最前面固定是 1000,
一樣找出後面的位元有幾個在 A 中是 0。
要注意的是,如果這個位元在 X 和在 A 中同時為 1,
則後面就不會再有答案,必須中斷。
再來,因為這個做法只能處理到 X-1,
所以 X 要另外處理。
最後,因為題目要求要正整數,
但這個做法會包含 0,
所以答案要再減一。
核心程式碼:
for (bit=(1<<30), ans=0; bit; bit>>=1)
{
if ((bit&x)==0) continue;
for (bit2=(bit>>1), c=0; bit2; bit2>>=1)
if ((bit2&a)==0) c++;
ans+=A[c];
if (bit&a) break;
}
if ((a|x)==(a+x)) ans++;
printf("%d\n", ans-1);
PS. A[ i ] 為 2i, 可在程式一開始先算出它們的值。