Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 16 kết quả

Đề tài: Thuật toán đếm số bit 1 trong 1 triệu kí tự (1 kí tự 8bit)

  1. #1
    Ngày gia nhập
    12 2011
    Bài viết
    8

    Mặc định Thuật toán đếm số bit 1 trong 1 triệu kí tự (1 kí tự 8bit)

    Cho 1 file chứa 1 triệu kí tự 8 bit. Hãy trình bày thuật toán đếm số bit 1 trong 1 triệu kí tự sao cho tối ưu về thời gian thực thi.
    Ai giúp mình giải câu này với được không. Cảm ơn mọi người nhiều.

  2. #2
    Ngày gia nhập
    08 2010
    Nơi ở
    Moscow, Russia Federation
    Bài viết
    913

    Theo mình nghĩ thì bạn vẫn phải kiểm tra số bites 1 của từng kí tự thôi!
    Mời các bạn ghé thăm blog cá nhân của tôi

  3. #3
    Ngày gia nhập
    03 2011
    Bài viết
    67

    Trích dẫn Nguyên bản được gửi bởi duykhoa1310 Xem bài viết
    Cho 1 file chứa 1 triệu kí tự 8 bit. Hãy trình bày thuật toán đếm số bit 1 trong 1 triệu kí tự sao cho tối ưu về thời gian thực thi.
    Ai giúp mình giải câu này với được không. Cảm ơn mọi người nhiều.
    Cái này trên mạng có nhiều, theo mình nhanh nhất là sử dụng các phép toán trên bit.
    Tham khảo :

  4. #4
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Phương pháp đó áp dụng cho số nguyên 32 bit, vì thế nếu muốn áp dụng cho bài của bạn thì bạn phải đọc ra từng 4 ký tự đấy.

  5. #5
    Ngày gia nhập
    03 2011
    Bài viết
    67

    Trích dẫn Nguyên bản được gửi bởi duykhoa1310 Xem bài viết
    Code phần Precompute-8bit mình không hiểu lắm, bạn có thể viết ra rõ hơn chút được không.
    Cảm ơn các bạn nhiều.
    Code demo cho bạn, đếm số bit 1 của một triệu phần tử. Hàm đếm số bit mình tham khảo ở đây:
    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3. unsigned char CountOnes(unsigned char x);
    4. const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
    5. int Random(int min,int max);
    6. int main()
    7. {
    8.     int sum = 0;
    9.     unsigned char *target = new unsigned char[1000000];
    10.     srand((unsigned int) time(NULL)); //Tránh hàm random lặp lại giá trị
    11.     for (int i = 0; i < 1000000; i++) //Khởi tạo 1 triệu phần tử ngẫu nhiên
    12.     {
    13.         target[i] = Random(0,255); // unsigned char
    14.         sum += CountOnes(target[i]);
    15.     }
    16.     cout << sum <<endl;
    17.     delete[] target;
    18.     system("pause");
    19.     return 0;
    20. }
    21. unsigned char CountOnes(unsigned char x)
    22. {
    23.     unsigned char results;
    24.     results = oneBits[x&0x0f];
    25.     results += oneBits[x>>4];
    26.     return results;
    27. }
    28.  
    29. int Random(int min, int max)
    30. {
    31.    
    32.     if(min >= max)
    33.         return 0;
    34.     int d = max - min;
    35.     return (rand() % (d+1) + min);
    36. }
    Bạn có thể viết tiếp hàm đọc file vào lưu vào target
    Đã được chỉnh sửa lần cuối bởi quandaso : 23-12-2011 lúc 04:44 PM.
    An Incompetent

  6. #6
    Ngày gia nhập
    08 2010
    Nơi ở
    Moscow, Russia Federation
    Bài viết
    913

    Mặc định Thuật toán đếm số bit 1 trong 1 triệu kí tự (1 kí tự 8bit)

    Trích dẫn Nguyên bản được gửi bởi duykhoa1310 Xem bài viết
    Mình biết là đầu tiên phải kiểm tra trước một kí tự, sau đó thì mới kiểm tra nhiều kí tự. Nhưng code để kiểm tra bit 1 trên một kí tự mình không biết viết. Mấy phép dịch bit và thao tác trên bit mình không giỏi lắm nên nhờ mọi người chỉ dùm với.
    Cái này đơn giản thôi. Kí tự 8 bites của bạn chắc là kí tự kiểu char, Công thức toán học Latex trạng thái nhận được bằng việc đảo trạng thái tương ứng của các bites này.

    Để tách số bites 1 của kí tự nào đó ta dùng phép logic & sử dụng biến đó và 1 với số dịch bites cần thiết (từ 0 đến 7) làm các toán hạng.

    Nếu dữ liệu của bạn là char 8 bites thì có thể làm theo ví dụ mình viết dưới đây
    C++ Code:
    1. #include <iostream>
    2.  
    3. size_t bitCount(const unsigned char& ch);
    4.  
    5. int main ()
    6. {
    7.     // test bitCount
    8.     std::cout << bitCount('a');
    9.     return EXIT_SUCCESS;
    10. }
    11.  
    12. size_t bitCount(const unsigned char& ch)
    13. {
    14.     size_t count(0);
    15.     for(int i = 0; i < 8; ++i)
    16.         ch&1<<i ? ++count : count;
    17.     return count;
    18. }

    Nếu là các dữ liệu khác, chẳng hạn như int 32 bites thì bạn cần tách ra các đoạn 8 bites để gọi hàm hoặc modify hàm bitCount.

    C++ Code:
    1. unsigned char CountOnes(unsigned char x)
    2. {
    3.     unsigned char results;
    4.     results = oneBits[x&0x0f];
    5.     results += oneBits[x>>4];
    6.     return results;
    7. }
    Hàm này viết rất hay đếm số bites của một char 8 bites bằng cách chia nó ra 4 bites để liệt kê trạng thái bằng một mảng tĩnh, như thế này sẽ tiết kiệm được thời gian thực thi rất nhiều và thao tác đơn thuần trên bites làm giảm độ phức tạp tính toán.
    Đã được chỉnh sửa lần cuối bởi mp121209 : 23-12-2011 lúc 05:40 PM. Lý do: làm liền các bài viết spam
    Mời các bạn ghé thăm blog cá nhân của tôi

  7. #7
    Ngày gia nhập
    03 2009
    Nơi ở
    %appdata%\Temp
    Bài viết
    819

    Theo mình ta nên tính trước số bit 1 trong 1 kí tự char bằng 1 mảng 256 phần tử. Như vậy việc tính toán sẽ nhanh hơn thay vì mỗi lần đọc ra lại đếm số bit 1
    .::[The best way to predict the future is to invent it]::.
    __________________________________________________ _ - Alan Kay -

  8. #8
    Ngày gia nhập
    12 2011
    Bài viết
    8

    Code:
    #include <conio.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <iostream.h>
    void main()
    {
    	char c='a';
    	int i,j=0,b;
    	for(i=0;i<8;i++)
    	{
    		b = c >> i;
    		if(0x01 & b)
    			j++;		
    	}
    	printf("\n So bit 1: %d",j);
    }
    Đây là chương trình đếm bit 1 trong 1 ký tự của mình.
    Code:
    unsigned char CountOnes(unsigned char x)
    {
        unsigned char results;
        results = oneBits[x&0x0f];
        results += oneBits[x>>4];
        return results;
    }
    Bạn nào có thể giải thích cho mình rõ hơn phần này với được không. Nếu được mong các bạn có thể debug cho mình 1 ký tự. Cảm ơn các bạn nhiều.
    Đã được chỉnh sửa lần cuối bởi duykhoa1310 : 23-12-2011 lúc 05:26 PM.

  9. #9
    Ngày gia nhập
    08 2010
    Nơi ở
    Moscow, Russia Federation
    Bài viết
    913

    Trích dẫn Nguyên bản được gửi bởi Wazi Armstrong Xem bài viết
    Theo mình ta nên tính trước số bit 1 trong 1 kí tự char bằng 1 mảng 256 phần tử. Như vậy việc tính toán sẽ nhanh hơn thay vì mỗi lần đọc ra lại đếm số bit 1
    Ý tưởng của bạn được hiện thực hóa trong hàm unsigned char CountOnes(unsigned char x); rồi đấy thôi. Bởi vì tạo ra một mảng 256 phần tử lâu, phức tạp và có thể nhiều khi gây khó khăn nên ng ta đã sử dụng mảng 16 phần tử. Dịch phải 4 bites và lại sử dụng mảng 16 phần tử, có gì là lâu hơn 256 phần tử của bạn đâu!
    Mời các bạn ghé thăm blog cá nhân của tôi

  10. #10
    Ngày gia nhập
    12 2011
    Bài viết
    8

    Trích dẫn Nguyên bản được gửi bởi mp121209 Xem bài viết
    Ý tưởng của bạn được hiện thực hóa trong hàm unsigned char CountOnes(unsigned char x); rồi đấy thôi. Bởi vì tạo ra một mảng 256 phần tử lâu, phức tạp và có thể nhiều khi gây khó khăn nên ng ta đã sử dụng mảng 16 phần tử. Dịch phải 4 bites và lại sử dụng mảng 16 phần tử, có gì là lâu hơn 256 phần tử của bạn đâu!
    Bạn có thể debug cho mình một ký tự để giải thích hàm unsigned char CountOnes(unsigned char x). Ví dụ như ta cho x là ký tự z thì hàm này sẽ chạy như thế nào.

Các đề tài tương tự

  1. Trả lời: 2
    Bài viết cuối: 19-04-2013, 10:48 PM
  2. Thuật toán C# Thuật toán chuyển ảnh bitmap 24bit về 8bit như thế nào?
    Gửi bởi thuccoi trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 09-01-2013, 09:14 PM
  3. Code saturation 8bit, có cách nào tối ưu hơn được không?
    Gửi bởi quanganh12 trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 7
    Bài viết cuối: 18-09-2011, 09:50 AM
  4. Xây dựng hàm tính đảo 4 bít đầu và 4 bít cuối cho nhau của một số 8bit
    Gửi bởi bossnguyen86 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 20
    Bài viết cuối: 04-08-2010, 08:54 AM
  5. Biển và Đảo ! Giải thuật và cách triển khai trong C++
    Gửi bởi rox_rook trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 01-02-2008, 01:51 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn