#ABC336B. CTZ

CTZ

AT_abc336_b [ABC336B] CTZ

题目描述

\hspace{15pt}对于正整数 xx,用 22 进制表示时,末尾连续 00 的个数记作 ctz(x)\mathrm{ctz}(x)。

\hspace{15pt}如果 xx 的二进制表示末尾是 11,则 ctz(x)=0\mathrm{ctz}(x)=0。

\hspace{15pt}给定一个正整数 nn,请输出 ctz(n)\mathrm{ctz}(n)。

输入格式

\hspace{15pt}在一行上输入一个整数 n(1≦n≦109)n \left(1 \leqq n \leqq 10^9 \right),代表给定的正整数。

输出格式

\hspace{15pt}在一行上输出一个整数,代表 ctz(n)\mathrm{ctz}(n)。

测试样例

2024
3

样例 1 解释

2024\hspace{15pt}2024 的二进制表示为 "11111101000"\texttt{"11111101000"},末尾有 33 个连续的 00,因此 ctz(2024)=3\mathrm{ctz}(2024)=3。

18
1

样例 2 解释

18\hspace{15pt}18 的二进制表示为 "10010"\texttt{"10010"},因此 ctz(18)=1\mathrm{ctz}(18)=1。请注意,00 必须是从末尾连续出现的。

5
0