cho em hỏi tý về thuật toán ạ !
em đang làm bài tập là chuyển lưu trữ số 16 bytes và thực hiện các phép toán .
em đã làm được phép +,-,* và còn thiếu chia nữa thôi ạ !
cụ thể là cấu trúc lưu số là mảng long long array[2] để lưu bits rồi ạ ,
vd : nhập vào dãy bit gồm 100 ký tự (10101000…011)
thì 64 bits đầu sẽ lưu vào array[0] ,còn các bit còn lại sẽ lưu vào array[1]
thao tác chia khá là khó không biết có ai cho định hướng(hay cách giải quyết) với ạ ( em định chuyển về hệ 10 rồi chia cho dễ nhưng có vẻ không tối ưu lắm ).
Thao tác chia số lớn C++
- Dấu câu (
.,?!;) nằm liền với từ phía trước (không có dấu cách). Như này! - Viết hoa các chữ cái đầu câu. Như này!
- Các cặp ngoặc phải bao sát nội dung [ngoặc vuông], (ngoặc đơn), không có dấu cách.
- Phần chính: học tiểu học, chia như nào thì giờ chia như thế. Gì mà từ trái sang phải và vay mượn gì đấy.
Bạn muốn chia theo hệ nhị phân luôn à? Chẳng khác gì cách chia tiểu học theo hệ thập phân cả, chỉ khác: không phải là 10 mà là 2.
1000 | 11 1000 (8) / 11 (3)
_____|__ Kết quả: 8 / 3 = 2 (dư 2)
100 | 1 10 / 11 không được, mượn số 0 tiếp theo 100 / 11 = 1 (dư 1)
10 | 0 số 1 dư và số 0 thành 10 / 11 = 0 (dư 10), kết thúc phép chia vì không còn số nào nữa.
10 |
1000 / 11 = 10 (dư 10)
Vì sao bước chia thứ nhất 100 chia cho 11 lại bằng 1 và dư 1?
Nhị phân 11 + 1 = 100 như thập phân 9 + 1 = 10 => 10 / 9 = 1 (dư 1).
6 Likes
Ta chỉ cần hiệu chỉnh 1 lần duy nhất (cho mỗi phép chia) bằng cách nhân cả số bị chia và số chia với hệ số k<=2^32, sao cho chữ số hàng cao nhất của số chia không dưới 2^32. Lúc này không cần ước lượng nữa, thương giữ nguyên và số dư chỉ chia lại cho k thôi.
5 Likes
Anh có thể demo chi tiết hơn tý được không ạ! Em vẫn chưa hình dung ra ạ
Đặt tính: 19'6'0\div26
do 26 < 31 nên nhân 2: 392'0\div52
39 \div 5 = 7 \rightarrow 392 - 52*7 = 28
28 \div 5 = 5 \rightarrow 280 - 52*5 = 20
vậy 1960 \div 26 = 75\ dư\ 10
16'81'72\div678
nhân 2: 33'63'84\div1356
33\div13 = 2 \rightarrow 3363 - 1356*2 = 651
65184 \div 1356 = 48\ dư\ 96
vậy 168172 \div 678 = 248\ dư\ 48
6 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?