首页 > > 程序设计 > C/C++ >

Binary mod and divide（模拟+大数）

2018-06-17 21:19:49来源：未知阅读 ()

描述

Most people know that the binary operations. Do you know the binary mod and divide?

Now give the Binary number N and a integer number M ,Can you tell me the answer of N%(2^M) and N/(2^M)?

输入

Input contains multiple test cases.

The first line of each test case contains an binary number N no more than 128 bits and an integer M (1 <= M <= 64).

when N=0&&M=0 ,test is over.

输出

output the answer the N%(2^M) and N/(2^M).

样例输入

111 2

1111 2

0 0

样例输出

mod=3, divide=1
mod=3, divide=3

题目大意是：给一个不超过128位的二进制数N，和一个整数M，求N%(2^M)和N/(2^M).

1.把2^M次转化成二进制，即1后面M个0；N的最小位开始数M位，把N分成两部分，左边为倍数，右边为余数。

　eg:1010101101,5 .即倍数的二进制为10101，余数的二进制为01101.

2.计算的话，2^128次longlong存不下，所以用数组存了。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 using namespace std;
 5 char a[150];
 6 void add(int l,int r,int b[])
 7 {
 8     for(int i=l;i<r;i++)
 9     {
10         for(int j=0;j<40;j++)
11             b[j]*=2;
12         b[0]+=a[i]-'0';
13         for(int j=0;j<40;j++)
14         {
15             if(b[j]>=10)
16             {
17                 b[j+1]+=b[j]/10;
18                 b[j]%=10;
19             }
20         }
21     }
22 }
23 int main()
24 {
25     int m,i,l;
26     int b[45],c[45];
27     while(scanf("%s%d",a,&m))
28     {
29         if(!m&&a[0]=='0') break;
30         memset(b,0,sizeof(b));
31         memset(c,0,sizeof(c));
32         l=strlen(a);
33         add(0,l-m,b);
34         add(max(0,l-m),l,c);
35         printf("mod=");
36         for(i=39;i>=0;i--)
37             if(c[i]) break;
38         if(i==-1) printf("0");
39         for(;i>=0;i--)
40             printf("%d",c[i]);
41　　　　　 printf(", divide=");
42         for(i=39;i>=0;i--)
43             if(b[i]) break;
44         if(i==-1) printf("0");
45         for(;i>=0;i--)
46             printf("%d",b[i]);
47         putchar(10);
48     }
49 }