Times 17

Link: nowcoder-945-J
Description:
After realizing that there is much money to be made in software development, Farmer John has launched a small side business writing short programs for clients in the local farming industry.
Farmer John's first programming task seems quite simple to him -- almost too simple: his client wants him to write a program that takes a number N as input, and prints 17 times N as output. Farmer John has just finished writing this simple program when the client calls him up in a panic and informs him that the input and output both must be expressed as binary numbers, and that these might be quite large.
Please help Farmer John complete his programming task. Given an input number N, written in binary with at most 1000 digits, please write out the binary representation of 17 times N.
输入描述:

  • Line 1: The binary representation of N (at most 1000 digits).

输出描述:

  • Line 1: The binary representation of N times 17.

示例1
输入

10110111

输出

110000100111

说明

OUTPUT DETAILS:
The binary number 10110111 is equal to 183 in decimal form.
183 x 17 = 3111 is 110000100111 in binary format.

Intentional analysis:
When I first saw this problem,I think it's so easy if I use bitset.But then I find the string input is at most 1000 digits,obviously,even long long can't save.So we must choose another way.I search the Binary multiplication on the internet.

How can we perform Binary multiplication?

I think this following picture is a good way to explain.

And in this problem,we need to multiply by 17.And the binary of 17 is 10001.So what we should do is add s+'0000' to s(s is the string we input).After this,a less easy problem has also appeared.How do we do binary addition?Just simulation.Just like the simulation we did before adding large numbers.You can see the sode to understand.

Click to see Chinese Intentional analysis 一开始想用bitset很简单，然后发现数据范围是2^1000,long long都存不下。然后去搜索了一下二进制相乘，上面那个图片就很好理解，这道题我们只需要跟17相乘。而17的二进制形式是10001.所以我们只需要将s后面接四个0与s（例如我们输入的是111，那我们只需要将‘1110000’与‘111’加起来）加起来就好（s是我们输入的字符串）。这个二进制相加只需要模拟就行了，就像我们之前模拟大数相加的时候一样模拟。

Code:

#include <bits/stdc++.h>
using namespace std;
char ans[1005];
int main()
{
    string s, mid;
    int    i = 0;
    cin >> s;
    mid = s + "0000";
    int temp = 0;
    reverse(s.begin(), s.end());//binary addition
    reverse(mid.begin(), mid.end());
    for (i = 0; i < max(s.size(), mid.size()); i++)
    {
        if (i < s.size() && i < mid.size())
            temp += s[i] + mid[i] - '0' - '0';
        if (i >= s.size() && i < mid.size())
            temp += mid[i] - '0';
        if (i < s.size() && i >= mid.size())
            temp += s[i] - '0';
        ans[i] = temp % 2 + '0';
        temp  /= 2;
    }
    if (temp == 1)
    {
        ans[i] = '1'; i++;
    }
    for (int j = i - 1; j >= 0; j--)
        cout << ans[j];
    return 0;
}

I have to say,python is easy and amazing this time.

print(bin(int(input(),2)*17)[2:])

Because you don't need to care how big the number is.Just calculate.

赏