e455 - 二進位的絕對值
題目描述
題目給定一個 16 位元的二進位整數，要求輸出其十進位絕對值。題目限制不能使用 <bitset>，並強調考驗演算法和優化。
解題思路
這題的核心在於理解二進位的絕對值計算。由於輸入是 16 位元的二進位數，我們可以將其視為一個有號整數。如果最高位是 0，則直接將二進位數轉換為十進位即可。如果最高位是 1，則表示該數為負數，需要計算其二補數，然後取絕對值。二補數的計算方式是將所有位元反轉，然後加 1。然而，程式碼中採用了更簡潔的方式：如果最高位是 1，則將其視為負數，直接用 32768 (2^15) 減去其正數表示的值，即可得到其絕對值。
程式碼使用 getchar_unlocked() 逐一讀取二進位位元，並使用位移運算 k >>= 1 來計算每個位元的權重。write() 函數用於輸出十進位結果，它避免了使用標準輸出流，以提高效率。
複雜度分析
- 時間複雜度: O(16) (因為輸入固定為 16 位元)
- 空間複雜度: O(1) (使用固定大小的陣列
stk來儲存十進位數字)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline void write(int x) {
if(x==0)putchar_unlocked('0');
int stk[5],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
char a,a0;
int main(){
while(a0=getchar_unlocked()){
if(a0==EOF)break;
int ans(0);
for(int i(1),k(16384);i<16;++i,k>>=1){
a=getchar_unlocked();
if(a=='1')ans+=k;
}
if(a0=='1')ans=32768-ans;
write(ans);
putchar_unlocked('\n');
a0=getchar_unlocked();
}
}