列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

這題要以二進位來思考，
假設 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 ] 為 2ⁱ， 可在程式一開始先算出它們的值。