C++: Binary để Decimal chuyển đổi

Question

Tôi cố gắng để chuyển đổi một mảng nhị phân để thập phân theo cách sau:

uint8_t array[8] = {1,1,1,1,0,1,1,1} ; 
int decimal = 0 ;  

for(int i = 0 ; i < 8 ; i++) 
    decimal = (decimal << 1) + array[i] ; 

Thật sự tôi có để chuyển đổi 64 bit mảng nhị phân để thập phân và tôi phải làm điều đó cho triệu lần .

Ai có thể giúp tôi, có cách nào nhanh hơn để thực hiện điều này không? Hoặc là ở trên là tốt đẹp?

Answer 1

phương pháp của bạn là đầy đủ, để gọi nó là đẹp tôi sẽ chỉ không pha trộn các hoạt động Bitwise và cách "toán học" chuyển đổi sang thập phân, tức là sử dụng một trong hai

decimal = decimal << 1 | array[i]; 

hoặc

decimal = decimal * 2 + array[i]; 

Answer 2

Điều quan trọng là, trước khi cố gắng tối ưu hóa bất kỳ, để cấu hình mã. Hãy xem mã nguồn đang được tạo và chỉ tối ưu hóa khi bạn hiểu những gì đang diễn ra.

Và như đã được chỉ ra, tối ưu hóa tốt nhất là không làm điều gì đó, nhưng để thực hiện một thay đổi cấp cao hơn mà loại bỏ sự cần thiết.

Tuy nhiên ...

Hầu hết các thay đổi mà bạn có thể muốn trivially thực hiện ở đây, có thể sẽ là điều các trình biên dịch đã được thực hiện (một sự thay đổi cũng giống như một nhân để trình biên dịch). Một số có thể thực sự ngăn không cho trình biên dịch thực hiện tối ưu hóa (thay đổi add thành or sẽ hạn chế trình biên dịch - có nhiều cách để thêm số và chỉ bạn biết rằng trong trường hợp này kết quả sẽ giống nhau).

Số học con trỏ có thể tốt hơn, nhưng trình biên dịch không phải là ngu ngốc - nó phải đã tạo mã phong nha để dereferencing mảng, vì vậy bạn cần phải kiểm tra xem bạn có thực sự làm vấn đề tồi tệ hơn bằng cách giới thiệu một biến bổ sung.

Trong trường hợp này, số vòng lặp được xác định rõ và bị giới hạn, vì vậy việc kiểm tra có thể có ý nghĩa.

Thêm nữa tùy thuộc vào cách bạn muốn kết quả phụ thuộc vào kiến ​​trúc đích của bạn. Nếu bạn muốn tính di động, thật khó (er) để tối ưu hóa.

Ví dụ, sau đây tạo ra mã tốt hơn ở đây:

unsigned int x0 = *(unsigned int *)array; 
unsigned int x1 = *(unsigned int *)(array+4); 

int decimal = ((x0 * 0x8040201) >> 20) + ((x1 * 0x8040201) >> 24); 

tôi có lẽ cũng có thể cuộn một phiên bản 64-bit mà đã 8 bit tại một thời điểm thay vì 4.

Nhưng nó rất chắc chắn không phải mã di động. Tôi có thể sử dụng nó ở địa phương nếu tôi biết những gì tôi đã chạy trên và tôi chỉ muốn số khủng hoảng nhanh chóng. Nhưng tôi có lẽ sẽ không đặt nó trong mã sản xuất. Chắc chắn không phải không ghi lại những gì nó đã làm, và không có bài kiểm tra đơn vị đi kèm để kiểm tra xem nó có thực sự hoạt động hay không.

Answer 3

Bạn có thể sử dụng accumulate, với gấp đôi và thêm phép toán hai ngôi:

int doubleSumAndAdd(const int& sum, const int& next) { 
    return (sum * 2) + next; 
} 

int decimal = accumulate(array, array+ARRAY_SIZE, 
         doubleSumAndAdd); 

này tạo ra số nguyên lớn về cuối nhỏ, trong khi OP đang sản xuất ít về cuối nhỏ.

Answer 4

Nén 'nhị phân' có thể được khái quát hóa như một vấn đề về tổng trọng số - và cho rằng có một số kỹ thuật thú vị.

• X mod (255) có nghĩa là tổng hợp về tất cả các số 8 bit độc lập.

• X mod 254 phương tiện tổng hợp mỗi chữ số với trọng lượng tăng gấp đôi, từ 1 mod 254 = 1, 256 mod 254 = 2, 256 * 256 mod 254 = 2 * 2 = 4 vv

  Nếu mã hóa là endian lớn, sau đó * (unsigned long long) mảng% 254 sẽ tạo ra một tổng trọng số (với phạm vi cắt ngắn là 0..253). Sau đó, xóa giá trị có trọng số 2 và thêm giá trị theo cách thủ công sẽ tạo kết quả chính xác:

  mảng uint64_t a = * (uint64_t *); return (a & ~ 256)% 254 + ((a >> 9) & 2);

cơ chế khác để có được trọng lượng là để premultiply mỗi chữ số nhị phân bằng 255 và mặt nạ bit đúng:

uint64_t a = (*(uint64_t *)array * 255) & 0x0102040810204080ULL; // little endian 
uint64_t a = (*(uint64_t *)array * 255) & 0x8040201008040201ULL; // big endian 

Trong cả hai trường hợp sau đó ai có thể lấy phần còn lại của 255 (và chính xác bây giờ với weight 1):

return (a & 0x00ffffffffffffff) % 255 + (a>>56); // little endian, or 
return (a & ~1) % 255 + (a&1); 

Vì lý do hoài nghi: Tôi thực sự đã lập hồ sơ phiên bản modulus (nhanh hơn) lặp lại trên x64.

Để tiếp tục câu trả lời của JasonD, việc chọn bit song song có thể được sử dụng lặp lại. Nhưng trước tiên bày tỏ phương trình ở dạng đầy đủ sẽ giúp trình biên dịch để loại bỏ phụ thuộc nhân tạo được tạo ra bởi phương pháp lặp đi lặp lại sử dụng tích lũy:

ret = ((a[0]<<7) | (a[1]<<6) | (a[2]<<5) | (a[3]<<4) | 
     (a[4]<<3) | (a[5]<<2) | (a[6]<<1) | (a[7]<<0)); 

vs

HI=*(uint32_t)array, LO=*(uint32_t)&array[4]; 
LO |= (HI<<4); // The HI dword has a weight 16 relative to Lo bytes 
LO |= (LO>>14); // High word has 4x weight compared to low word 
LO |= (LO>>9); // high byte has 2x weight compared to lower byte 
return LO & 255; 

Thêm một kỹ thuật thú vị sẽ được sử dụng crc32 như một hàm nén; sau đó nó chỉ xảy ra rằng kết quả sẽ là LookUpTable [crc32 (array) & 255]; vì không có va chạm với tập hợp con nhỏ được cho là 256 mảng riêng biệt này. Tuy nhiên để áp dụng điều đó, người ta đã chọn con đường của tính di động thậm chí ít hơn và cũng có thể kết thúc bằng cách sử dụng nội tại SSE.

Answer 5

Hãy thử điều này, tôi chuyển đổi một chữ số nhị phân lên tới 1020 bit

#include <sstream> 
#include <string> 
#include <math.h> 
#include <iostream> 
using namespace std; 

long binary_decimal(string num) /* Function to convert binary to dec */ 
{ 
    long dec = 0, n = 1, exp = 0; 
    string bin = num; 
     if(bin.length() > 1020){ 
      cout << "Binary Digit too large" << endl; 
     } 
     else { 

      for(int i = bin.length() - 1; i > -1; i--) 
      { 
       n = pow(2,exp++); 
       if(bin.at(i) == '1') 
       dec += n; 
      } 

     } 
    return dec; 
} 

Về mặt lý thuyết phương pháp này sẽ làm việc cho một chữ số nhị phân có độ dài infinate