Chuyển số nhị phân sang số thập phân trong C++

giang3 · August 28, 2020, 10:40am

Đề bài: Cho số tự nhiên N (0<=N<=10^1000) được biểu diễn dưới dạng nhị phân. Hãy chuyển đổi về dạng thập phân của nó.

string n;
cin>>n;
long long sum=0;
long long j=n.size() - 1;
for(long long i=0;i<n.size();i++) {
    if((s[i] - '0') == 1) {
        sum = sum + pow(2,j);
        j--;
    }
    else j--;
}

Code của em làm theo cách thông thường tuy k sai kết quả nhưng lại không thể chạy được với n lớn do hàm pow. Anh chị có cách nào khác để giải quyết bài toán không ạ.Em cám ơn!

kisuluoibieng · August 28, 2020, 9:16am

thì rõ ràng mục đích của bài này đâu phải để giải như vậy
chủ yếu là để rèn kiên nhẫn và sử dụng cấu trúc dữ liệu thôi, không khó nhưng sẽ hơi tốn công
dùng mảng để lưu số lớn, viết hàm để cộng 2 số lớn
long long int có thể lên tới 10^18, như vậy mỗi đơn vị nên biểu diễn dưới cơ số 10^18
giả sử như số 34567890 có thể biểu diễn thành [34567890]
giả sử như số 123456789123456789123 (21 số) có thể biểu diễn thành [123456789123456789, 123]

hoặc nếu bạn thấy khó hiểu thì mỗi số là một phần tử luôn, đúng cơ số 10, implement phép cộng như cộng toán học bình thường

thanhtrung2314 · August 28, 2020, 2:27pm

hàm pow không take được số lớn thì không dùng hàm pow, chuyển thế này thử xem
giả sử chuỗi vào là s = 11001
bạn đi từ trái sang phải
khởi tạo res = 0
s[0] = 1 => res += 1 = 1
tiếp theo
res *= 2 = 2
nhân với 2 tức bạn đã thực hiện phép toán dời bit << hay nói cách là
1 << = 10
trong khi đó s[1] = 1, nên từ 10, ta muốn thành 11 thì 10 + 1 = 11
res += 1 = 3
tiếp theo lại dời bit
res *= 2 = 6
thành 110
s[2] = 0, nên ko cần + 1 nữa
lại tiếp tục dời
res *= 2 = 12
thành 1100
dời phát nữa
res *= 2 = 24
thành 11000
cơ mà s[5] = 1, khi đó + 1 vào ta được 11000 + 1 = 11001
res += 1 = 25
tới đây thì hết length rồi, stop
return res

nitro2 · August 28, 2020, 2:49pm

N = 10^1000 là 1 số rất rất lớn.
Mục đích của bài này là xây dựng các hàm để thao tác phép tính cộng và nhân trên các số biểu diễn qua string
Ví dụ : "1242905430594350923409329042034923043249032423094" * "2"

giang3 · August 29, 2020, 1:16am

cách anh hay quá.đỡ mất công nhân thực hiện nhân 2 số lớn

rogp10 · August 29, 2020, 1:44am

Dùng sơ đồ Horner chỉ cần cộng 1 với nhân 2 (đều dễ) thôi.

giang3 · August 29, 2020, 1:51am

Em đã thử.tuy đúng nhưng vẫn không thể thực hiện được với số lớn 10^1000

rogp10 · August 29, 2020, 3:27am

Thì bạn trải ra 1 mảng 310 slot (thực ra 18 slot uint64 là được)

thanhtrung2314 · August 29, 2020, 3:45am

bạn thấy rằng làm theo cách mình chỉ có chốt lại là dùng + 1 và nhân 2 mà nhân 2 chính là cộng với chính nó
giờ bạn xây dựng một số = mảng kí tự để có thể đơn giản và viết hàm con + hai số là 2 mảng kí tự thôi
còn bước xử lí thì như trên.