e351 - And 運算
題目描述
題目要求計算兩個整數 a 和 b 之間（包含 a 和 b）所有整數進行按位 AND 運算的結果。
解題思路
題目要求計算 a & (a+1) & (a+2) & ... & b 的結果。觀察到，如果 a 和 b 的二進位表示不同，那麼結果一定會受到低位 0 的影響，使得某些位變成 0。因此，可以將 a 和 b 轉換為二進位，從最高位開始比較，如果 a 和 b 的對應位都為 1，則結果的該位也為 1；否則，結果的該位為 0。程式碼中，先將 a 和 b 轉換為二進位表示，然後從最低位開始比較，如果 a 和 b 的對應位都為 1，則結果的該位為 1，否則為 0。
複雜度分析
- 時間複雜度: O(log(b))，其中 b 是輸入的較大值。因為程式碼需要遍歷 a 和 b 的二進位表示，而二進位表示的長度與 b 的大小有關。
- 空間複雜度: O(log(b))，因為需要儲存 a 和 b 的二進位表示。
程式碼
#include <iostream>
using namespace std;
int main(){
unsigned long long a,b;
while(cin >> a >> b){
if(a>b)swap(a,b);
unsigned long long bit[101],bit2[101],it=0,it2=0,tmp=a,tmp2=b,t=1,ans=0;
for(int i=0;i<101;++i){
bit[i]=bit2[i]=0;
}
while(tmp){
bit[it++]=tmp%2;
tmp/=2;
}
while(tmp2){
bit2[it2++]=tmp2%2;
tmp2/=2;
}
for(int i=it2-1;i>=0;--i){
if(bit2[i]!=bit[i]){
t=0;
}
if(t==0){
bit2[i]=0;
}
}
for(int i=it2-1;i>=0;--i){
ans*=2;
if(bit2[i]){
++ans;
}
}
cout << ans << "\n";
}
}