折半歸零要幾次
1.0s 256M給你一個正整數 \(n\)。
每次操作時,請把目前的 \(n\) 做整數除以 \(2\),也就是小數部分直接捨去。請問至少要操作幾次,\(n\) 才會變成 \(0\)?
例如 \(n = 13\) 時,變化過程是:
13 -> 6 -> 3 -> 1 -> 0
總共操作了 \(4\) 次,所以答案是 \(4\)。
語法限制
本題採用語法書第四單元〈迴圈〉的語法限制。你可以使用 if、else、迴圈、比較運算、邏輯運算、整數變數、cin、cout 與 cout << endl;但不可使用陣列或容器,也不可使用 main 以外的任何函式(包含內建函式與自定義函式)。其中 endl 只有作為輸出換行用法時允許,不能寫成函式呼叫。
評測時會自動檢查你的程式碼,違反限制的判定會是 SR(語法限制),評測回饋會列出違規的位置。
點我展開:本題允許與禁止的語法清單
允許使用:
#include <iostream>或其他一般 include(但不需要額外標頭)using namespace std;int main()主函式與return 0;- 整數、布林與字元變數,例如
int、long long、bool、char cin >>讀入、cout <<輸出,可以使用cout << endlif、else、for、while- 算術、比較與邏輯運算子,例如
+、-、*、/、%、<、<=、==、&& - 指派與遞增遞減,例如
=、+=、++、-- - 註解(
//與/* */)
禁止使用(列出常見項目):
- 陣列與索引語法
[] vector、array、string、deque、map、set等容器或類似工具new、delete等動態配置語法main以外的任何函式呼叫或函式宣告,包含max、min、abs、sqrt、pow、sort、swap、getline、printf、scanf#define等非 include 的前置處理指令
輸入格式
輸入只有一行,包含一個正整數 \(n\)。
限制
- \(1 \le n \le 2 \times 10^9\)
- 記憶體限制為 \(256\) MB
輸出格式
輸出一個整數,代表 \(n\) 變成 \(0\) 前需要做幾次整數除以 \(2\) 的操作。
範例輸入 1
13
範例輸出 1
4
範例輸入 2
1
範例輸出 2
1
範例輸入 3
2000000000
範例輸出 3
31
題目來源
改編自 AACPOJ 語法書上冊 4.2 while 迴圈 中的「折半歸零要幾次」例題。