Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: toán tử dịch bit <<= có nghĩa gì?

  1. #1
    Ngày gia nhập
    04 2008
    Bài viết
    244

    Mặc định toán tử dịch bit <<= có nghĩa gì?

    anh em trong diễn đàn chắc là biết toán tử dịch bit << nhưng sao trong 1 bài mình thấy có toán tử như thế này

    <<= vậy là sao
    mình sẽ cho 1 VD đơn giản nhé
    /* shift current byte left one *///cái này trong bài tập nó ghi thía
    current_byte <<= 1;
    với current_byte ở định dạng (int)
    int current_byte;


    còn anh em nào muốn cụ thể thì mình đưa code đầy đủ bài đó lên

    Bài toán nén file txt bằng Huffman
    C Code:
    1. /* Huffman Coding in C . This program reads a text file named on the command line, then compresses it using Huffman coding. The file is read twice, once to determine the frequencies of the characters, and again to do the actual compression. */
    2. #include <stdio.h>
    3. #include <stdlib.h>
    4. #include <string.h>
    5. #include <time.h>
    6. /* there are 256 possible characters */
    7. #define NUM_CHARS 256
    8. /* tree node, heap node */
    9. typedef struct _treenode treenode;
    10. struct _treenode
    11. {
    12.     int freq; /* frequency; is the priority for heap */
    13.     unsigned char ch; /* character, if any */
    14.     treenode *left, /* left child of Huffman tree (not heap!) */
    15.     *right; /* right child of Huffman tree */
    16. };
    17. /* this is a priority queue implemented as a binary heap */
    18. typedef struct _pq
    19. {
    20.     int heap_size;
    21.     treenode *A[NUM_CHARS];
    22. } PQ;
    23. /* create an empty queue */
    24. void create_pq (PQ *p)
    25. {
    26.     p->heap_size = 0;
    27. }
    28. /* this heap node's parent */
    29. int parent (int i)
    30. {
    31.     return (i-1) / 2;
    32. }
    33. /* this heap node's left kid */
    34. int left (int i)
    35. {
    36.     return i * 2 + 1;
    37. }
    38. /* this heap node's right kid */
    39. int right (int i)
    40. {
    41.     return i * 2 + 2;
    42. }
    43. /* makes the subheap with root i into a heap , assuming left(i) and
    44. * right(i) are heaps
    45. */
    46. void heapify (PQ *p, int i)
    47. {
    48.     int l, r, smallest;
    49.     treenode *t;
    50.  
    51.     l = left (i);
    52.     r = right (i);
    53. /* find the smallest of parent, left, and right */
    54.  
    55.     if (l < p->heap_size && p->A[l]->freq < p->A[i]->freq)
    56.     smallest = l;
    57.     else
    58.         smallest = i;
    59.     if (r < p->heap_size && p->A[r]->freq < p->A[smallest]->freq)
    60.         smallest = r;  
    61.     /* swap the parent with the smallest, if needed. */
    62.     if (smallest != i)
    63.     {
    64.         t = p->A[i];
    65.         p->A[i] = p->A[smallest];
    66.         p->A[smallest] = t;
    67.         heapify (p, smallest);
    68.     }
    69. }
    70. /* insert an element into the priority queue. r->freq is the priority */
    71. void insert_pq (PQ *p, treenode *r)
    72. {
    73.     int i;
    74.    
    75.     p->heap_size++;
    76.     i = p->heap_size - 1;
    77. /* we would like to place r at the end of the array,
    78. * but this might violate the heap property. we'll start
    79. * at the end and work our way up
    80. */
    81.     while ((i > 0) && (p->A[parent(i)]->freq > r->freq))
    82.     {
    83.         p->A[i] = p->A[parent(i)];
    84.         i = parent (i);
    85.     }
    86.     p->A[i] = r;
    87. }
    88. /* remove the element at head of the queue (i.e., with minimum frequency) */
    89. treenode *extract_min_pq (PQ *p)
    90. {
    91.     treenode *r;
    92.     if (p->heap_size == 0)
    93.     {
    94.         printf ("heap underflow!\n");
    95.         exit (1);
    96.     }
    97. /* get return value out of the root */ 
    98.     r = p->A[0];
    99. /* take the last and stick it in the root (just like heapsort) */
    100.    
    101.     p->A[0] = p->A[p->heap_size-1];
    102.  
    103. /* one less thing in queue */  
    104.     p->heap_size--;
    105. /* left and right are a heap, make the root a heap */
    106.    
    107.     heapify (p, 0);
    108.     return r;
    109. }
    110. /* read the file, computing the frequencies for each character
    111. * and placing them in v[]
    112. */
    113. unsigned int get_frequencies (FILE *f, unsigned int v[])
    114. {
    115.     int r, n;
    116. /* n will count characters */  
    117.     for (n=0;;n++) {
    118. /* fgetc() gets an unsigned char, converts to int */
    119.     r = fgetc (f);
    120. /* no more? get out of loop */ 
    121.     if (feof (f)) break;
    122. /* one more of this character */
    123.     v[r]++;
    124.     }
    125.     return n;
    126. }
    127. /* make the huffman tree from frequencies in freq[] (Huffman's Algorithm) */
    128. treenode *build_huffman (unsigned int freqs[])
    129. {
    130.     int i, n;
    131.     treenode *x, *y, *z;
    132.     PQ p;
    133. /* make an empty queue */
    134.     create_pq (&p);
    135. /* for each character, make a heap/tree node with its value
    136. * and frequency
    137. */
    138.     for (i=0; i< NUM_CHARS; i++)
    139.     {
    140.         x = malloc (sizeof (treenode));
    141.  
    142. /* its a leaf of the Huffman tree */
    143.         x->left = NULL;
    144.         x->right = NULL;
    145.         x->freq = freqs[i];
    146.         x->ch = (char) i;
    147. /* put this node into the heap */
    148.         insert_pq (&p, x);
    149.     }
    150. /* at this point, the heap is a "forest" of singleton trees */
    151.     n = p.heap_size-1; /* heap_size isn't loop invariant! */
    152. /* if we insert two things and remove one each time,
    153. * at the end of heap_size-1 iterations, there will be
    154. * one tree left in the heap
    155. */
    156.     for (i=0; i< n; i++)
    157.     {
    158. /* make a new node z from the two least frequent
    159. * nodes x and y
    160. */
    161.         z = malloc (sizeof (treenode));
    162.         x = extract_min_pq (&p);
    163.         y = extract_min_pq (&p);
    164.         z->left = x;
    165.         z->right = y;
    166. /* z's frequency is the sum of x and y */
    167.         z->freq = x->freq + y->freq;
    168. /* put this back in the queue */
    169.         insert_pq (&p, z);
    170.     }
    171. /* return the only thing left in the queue, the whole Huffman tree */
    172.     return extract_min_pq (&p);
    173. }
    174. /* traverse the Huffman tree, building up the codes in codes[] */
    175. void traverse (treenode *r, /* root of this (sub)tree */
    176. int level, /* current level in Huffman tree */
    177. char code_so_far[], /* code string up to this point in tree */
    178. char *codes[])
    179. {/* array of codes */
    180. /* if we're at a leaf node, */
    181.     if ((r->left == NULL) && (r->right == NULL))
    182.     {
    183.         /* put in a null terminator */     
    184.         code_so_far[level] = 0;
    185. /* make a copy of the code and put it in the array */
    186.         codes[r->ch] = strdup (code_so_far);
    187.     }
    188.     else
    189.     {
    190.         /* not at a leaf node. go left with bit 0 */
    191.         code_so_far[level] = '0';
    192.         traverse (r->left, level+1, code_so_far, codes);
    193. /* go right with bit 1 */
    194.         code_so_far[level] = '1';
    195.         traverse (r->right, level+1, code_so_far, codes);
    196.     }
    197. }
    198. /* global variables, a necessary evil */
    199. int nbits, current_byte, nbytes;
    200. /* output a single bit to an open file */
    201. void bitout (FILE *f, char b)
    202. {[COLOR="Red"]
    203. /* shift current byte left one */
    204.     current_byte <<= 1;[/COLOR]
    205. /* put a one on the end of this byte if b is '1' */
    206.     if (b == '1') current_byte |= 1;
    207. /* one more bit */
    208.     nbits++;
    209. /* enough bits? write out the byte */
    210.     if (nbits == 8) {
    211.         fputc (current_byte, f);
    212.         nbytes++;
    213.         nbits = 0;
    214.         current_byte = 0;
    215.     }
    216. }
    217. /* using the codes in codes[], encode the file in infile, writing
    218. * the result on outfile
    219. */
    220. void encode_file (FILE *infile, FILE *outfile, char *codes[])
    221. {
    222.     unsigned char ch;
    223.     char *s;
    224. /* initialize globals for bitout() */
    225.     current_byte = 0;
    226.     nbits = 0;
    227.     nbytes = 0;
    228. /* continue until end of file */
    229.     for (;;)
    230.     {
    231. /* get a char */
    232.         ch = fgetc (infile);
    233.         if (feof (infile)) break;
    234. /* put the corresponding bitstring on outfile */
    235.         for (s=codes[ch]; *s; s++)
    236.             bitout (outfile, *s);
    237.     }
    238. /* finish off the last byte */
    239.     while (nbits) bitout (outfile, '0');
    240. }
    241. /* main program */
    242. int main (int argc, char *argv[])
    243. {
    244.     FILE *f, *g;
    245.     treenode *r; /* root of Huffman tree */
    246.     unsigned int n, /* number of bytes in file */
    247.         freqs[NUM_CHARS]; /* frequency of each char */
    248.     char *codes[NUM_CHARS], /* array of codes, 1 per char */
    249.         code[NUM_CHARS], /* a place to hold one code */
    250.         fname[100]; /* what to call output file */
    251. /* hassle user */
    252. /* set all frequencies to zero */
    253.     memset (freqs, 0, sizeof (freqs));
    254. /* open command line argument file */
    255.     f = fopen ("test.txt", "r");
    256.     if (!f)
    257.     {
    258.         perror ("test.txt");
    259.         printf("ko ton tai file");
    260.         system("pause");
    261.         exit (1);
    262.     }
    263. /* compute frequencies from this file */
    264.     n = get_frequencies (f, freqs);
    265.     fclose (f);
    266. /* make the huffman tree */
    267.     r = build_huffman (freqs);
    268. /* traverse the tree, filling codes[] with the codes */
    269.     traverse (r, 0, code, codes);
    270. /* name the output file something.huf */
    271.     sprintf (fname, "%s.huf", "C:\\test");
    272.     g = fopen (fname, "w");
    273.     if (!g)
    274.     {
    275.         perror (fname);
    276.         system("pause");
    277.         exit (1);
    278.     }
    279. /* write frequencies to file so they can be reproduced */
    280.     fwrite (freqs, NUM_CHARS, sizeof (int), g);
    281. /* write number of characters to file as binary int */
    282.     fwrite (&n, 1, sizeof (int), g);
    283. /* open input file again */
    284.     f = fopen ("test.txt", "r");
    285.     if (!f)
    286.     {
    287.         perror ("test.txt");
    288.         printf("khong ton tai file test.txt");
    289.         system("pause");
    290.         exit (1);
    291.     }
    292. /* encode f to g with codes[] */
    293.     encode_file (f, g, codes);
    294.     fclose (f);
    295.     fclose (g);
    296.     /* brag */
    297.     printf ("%s is %0.2f%% of %s\n",fname, (float) nbytes / (float) n, "test.txt");
    298.     system("pause");
    299.     exit (0);
    300. }


    chú ý,bài toán chạy trên TC nhé,nó sẽ nén cái file test.txt ở ngay cạnh nó và đặt vào ổ C:\test.huf

  2. #2
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    Đơn giản lắm, nó giống như toán tử += vậy thôi, lấy giá trị của biến dịch 1 bit rồi gán ngược trở lại vào biến.
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

  3. #3
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,006

    a<<=1
    chính là a=a<<1;


    đây là toán tử kép bạn à
    ^_,^

    Tổng hợp các câu chuyện hài hước vui nhộn, sử dụng Speech Synthesis để đọc : https://www.youtube.com/channel/UCLk...Tjrg/playlists


    Bùi Tấn Quang

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

  1. Liên thông trung cấp nghề,cao đẳng nghề lên đại học chính quy 2012
    Gửi bởi cafetrungnguyen trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 31-07-2012, 02:03 PM
  2. Trả lời: 0
    Bài viết cuối: 02-08-2011, 03:26 PM
  3. Nhập ký tự đầu tiên của một nghề sẽ xuất ra nghề đó bằng việc sử dụng enum?
    Gửi bởi sasadudu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 05-03-2011, 09:25 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