MUL2COM - Binary multiplication

Đây là một số kiến thức về biểu diễn số trên máy tính trước khi các bạn giải bài toán này. Với n bit, máy tính có thể biểu diễn được 2n số trong phạm vi -2n-1..(2n-1-1). Máy tính sử dụng các số bù 2 để biểu diễn các số âm. Trong cách biểu diễn số bù 2 có n bit thì:

  • Số x ≥ 0 được biểu diễn bằng chính số x.
  • Số x < 0 được biểu diễn bằng số 2n - x.

Dưới đây là bảng biểu diễn số bù 2 với 3 bit:

Biễu diễn số bù 2 Giá trị
0000
0011
0102
0113
100-4
101-3
110-2
111-1

Ưu điểm của số bù 2 là phép cộng có thể thực hiện hoàn toàn như các số không dấu. Với x > 0, x + (-x) = 2n = 0 vì các số chỉ được biểu diễn bởi n bit. Ví dụ, xét phép cộng (-2) + 3 trong biểu diễn số bù hai 3 bit:

 110
+011
 ---
 001

Kết quả bằng 1.

Với x ≥ 0, biểu diễn số bù 2 của -x sẽ thu được bằng cách đảo toàn bộ bit của x và cộng thêm 1 đơn vị. Nói cách khác -x = (NOT x) + 1. Để chỉ ra biểu thức này đúng, ta nhận xét rằng NOT x = 2n-1-x, do đó (NOT x) + 1 = 2n-x chính là biểu diễn của số -x. Với x < 0, ta cũng có -x = (NOT x) + 1.

Trong bài toán này, bạn cần thực hiện phép nhân hai số bù hai có n bit. Kết quả trả về cũng là một số bù hai n bit. Bạn hãy thông báo lỗi nếu kết quả vượt quả phạm vi biểu diễn.

Dữ liệu

Gồm nhiều bộ test, mỗi bộ test có dạng như sau:

Dòng đầu tiên chứa số n (0 ≤ n ≤ 1024) là số bit. n=0 cho biết kết thúc dữ liệu nhập. Nếu n>0, hai dòng tiếp theo, mỗi dòng chứa một số bù hai có n bit.

Có không quá 40 bộ test.

Kết quả

Gồm nhiều dòng, mỗi dòng tương ứng với một test chứa một số bù hai với số bit tương ứng là kết quả của phép nhân hoặc chứa chuỗi 'overflow' nếu kết quả vượt qua phạm vi biểu diễn.

Ví dụ

Dữ liệu
3
110
011
4
0011
1110
0

Kết quả
overflow
1010

Được gửi lên bởi:Jimmy
Ngày:2008-09-10
Thời gian chạy:0.204s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Nguồn bài:© VNOI

hide comments
2009-06-03 05:52:37 RR
http://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.