Int 2048

时间限制：$1 \mathrm{s}$
空间限制：$1024 \mathrm{MB}$

题目描述

这是一道交互题。

注意本交互库不提供Pascal\C支持，只支持C++。

L语言之父Lunk最近声称用该语言编写计数问题不要取模，因为Lunk发明了$256 \mathrm{\ Byte}$的int2048_t，并且已经内置到L语言中。

然而屁民们并不相信，因为Lunk的int2048_t还不支持Xntel公司的CSB指令 (Count Set Bits，计数被设置的位的数量)，于是众人D之。Lunk为了挽回自己的脸面，决定实现一个CSB命令来教训一下这群智障。

CSB指令是一个这样的指令：它用于计数一个整型的二进制表示中的$1$的个数。例如下面的整型中：

$$01001101$$

其执行CSB的结果是$4$。

Lunk不想再搞个新东西来支持这个垃圾玩意，他只准备利用现有的功能来实现它。目前int2048_t所支持的功能如下表所示：

符号	说明	示例	代价	实际复杂度
`(constructor)`	构造一个`int2048_t`	`int2048_t`	$0$	$\Theta(n)$
`(constructor)`	从一个字符串构造一个`int2048_t`	`int2048_t("110")`	$0$	$\Theta(n)$
`+`	加法	`0011 = 0010 + 0001`	$1$	$\Theta(n)$
`-`	取负数 (计算其补码)	`1111 = -0001`	$1$	$\Theta(n)$
`-`	减法 (需要执行一个取负数和加法)	`1101 = 1111 - 0010`	$2$	$\Theta(n)$
`~`	将各位取反	`1010 = ~0101`	$1$	$\Theta(n)$
`&`	按位与	`0010 = 1011 & 0110`	$1$	$\Theta(n)$
`\|`	按位或	`1111 = 1011 \| 0110`	$1$	$\Theta(n)$
`^`	按位异或	`1101 = 1011 ^ 0110`	$1$	$\Theta(n)$
`<<`	左移	`1100 = 1011 << 2`	$1$	$O(n)$
`>>`	右移	`0010 = 1011 >> 2`	$1$	$O(n)$
`==`	判断是否相等	`0010 == 0010`	$1$	$\Theta(n)$
`!=`	判断是否不等	`0010 != 1010`	$1$	$\Theta(n)$
`<`	小于	`0010 < 0100`	$1$	$O(n)$
`>`	大于	`0110 > 0100`	$1$	$O(n)$
`<=`	小于等于	`0100 <= 0100`	$1$	$O(n)$
`>=`	大于等于	`0010 >= 0010`	$1$	$O(n)$
`(bool)`	转为`bool`类型 (如果为$0$则为$\mathrm{false}$，否则为$\mathrm{true}$)	`if (a)`	$1$	$O(n)$

在上表中，代价是智障们评定运行快慢的标准，实际复杂度是在实际运行 (即你的程序) 中的时间复杂度，其中$n$表示int2048_t的二进制位数，即$2048$。

智障屁民们将会给出一堆的测试，如果Lunk的CSB指令写挂了，那么它们将会打$0$分。如果Lunk的CSB指令太慢，它们就又不高兴。于是Lunk请你帮他编写一个快速的CSB指令的实现。

实现

选手目录下将会下发int2048_t.hpp和int.h两个文件。

int2048_t.hpp是Lunk的int2048_t的实现，已经被int.h包含，选手不用自行包含。

选手需要实现一个evaluate函数，表示CSB指令。其函数原型如下：

1	int evaluate(const int2048_t &num);

当交互库运行时，会将测试数据通过num传入，而该函数的目的就是返回CSB指令在num上的结果。

样例交互库

选手目录下将会下发implementer.cpp这个文件。

假设你的实现的源文件是int.cpp，那么使用下面的编译命令来编译：

1	g++ int.cpp implementer.cpp -std=c++11 -o exec

然后将会得到可执行文件exec。

输入格式

此处的输入格式值针对样例交互库而言的。

输入只有一行，表示测试的整形，以二进制形式给出。请确保输入不超过2048位，否则将导致不正常结果。

由于int2048_t是有符号整型，出于一些原因，最终测试数据的输入的最高位都是$0$。

输出格式

此处的输出格式是针对样例交互库而言的。

样例交互库将会从输入得知答案，并将输入转为int2048_t，然后执行evaluate得到你的答案。如果两者答案一致，将会输出你所使用的代价总和。否则将输出Wrong answer，并给出正确答案和你的答案。

样例输入

01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

样例答案

评分标准

此题共$10$个数据点，每个数据点$10$分。

对于每一个数据点而言，如果你的答案不正确，那么将记$0$分。
否则，记$a$为你的evaluate执行的代价总和，$v_{\min}$和$v_{\max}$是每个数据点的特定的参数，那么你的得分将是：

$$ \left\lfloor \max\left\{ 10 \cdot\min\left\{ 1, \; { v_{\max} - a \over v_{\max} - v_{\min} } \right\}, \; 0 \right\} \right\rfloor $$

数据限制

对于每一个数据点，其限制如下表所示 (其中$x$表示答案)：

数据点编号	$x$	$v_{\min}$	$v_{\max}$
$1$，$2$，$3$	$ \leqslant 400 $	$6140$	$6144$
$4$，$5$，$6$	$ \leqslant 200 $	$801$	$1201$
$7$，$8$，$9$，$10$	$ \leqslant 2047 $	$76$	$120$

提示

一个整型的原码就是其二进制表示：

$$ 13 \rightarrow 00001101 $$

其反码就是将除了符号位 (即最高位) 的所有取反：

$$ 00001101 \rightarrow 01110010 $$

对于负数，其符号位为$1$：

$$ 01110010 \rightarrow 11110010 $$

二进制数的补码就是将其反码加上$1$，同时对于溢出的位直接丢弃，符号位也参与计算：

$$ -13 \rightarrow 11110011 \\ -0 \rightarrow 11111111 + 1 \rightarrow 100000000 \rightarrow 00000000 $$

因此采用补码存储负数，原码存储自然数，这样减法可以变为加法：

$$ 1 - 13 = 1 + (-13) \rightarrow 00000001 + 11110011 = 11110100 \rightarrow -12 $$

所以减法需要花费$2$的代价。