[c]实现位图

liangzhishao

   假设需要一个位图用来存储一个用户(A)的日期分布. 如果只保留60天的话, 那么用long long就
够用了

1. flag >>= 1; //删除一天
   
2. if(用户A今天出现)
   
3.    flag |= (1ll<<59); //新增一天
   
4. 
   
5. //统计出现天数
   
6. while(flag)
   
7. {
   
8.    if(flag & 1)
   
9.      validbit++;
   
10.    flag >>= 1;
    
11. }

复制代码

现在需要保存100天的, 怎么做呢?

bruceteen

你的意思是想要个 100bits 的数据类型 ？
C++的话用 std::bitset
C的话用 unsigned char[ (100+7)/8 ] 简单，用 unsigned int[ (100+sizeof(unsigned int)-1)/sizeof(unsigned int) ] 高效

liangzhishao

太大

liangzhishao

    刚写的,  还不知道正确不正确, 在我的机器上可以运行, 感兴趣的帮看看,
统计出现次数的功能还没有编写.....

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. typedef struct _state {
   
6.   unsigned char input[13];
   
7.   unsigned char output[13];
   
8.   int ining;
   
9.   int outing;
   
10.   unsigned short bi_buf;
    
11.   int bi_valid;
    
12. } state;
    
13. 
    
14. void send_bits(state *s, unsigned char value, int len)
    
15. {
    
16.   int rm = 16 - s->bi_valid;
    
17.   if(len > rm)
    
18.   {
    
19.     unsigned short val = value;
    
20.     s->bi_buf <<= rm;
    
21.     s->bi_buf |=  val>>(8-rm);
    
22.     //MSB first
    
23.     s->output[s->outing++] = (unsigned char)((s->bi_buf) >> 8);
    
24.     s->output[s->outing++] = (unsigned char)((s->bi_buf) & 0xff);
    
25.    
    
26.     s->bi_buf = val << rm;
    
27.     s->bi_valid = len - rm;
    
28.   }
    
29.   else
    
30.   {
    
31.     s->bi_buf <<= len;
    
32.     s->bi_buf |= value & (1<<len)-1;
    
33.     s->bi_valid += len;
    
34.   }
    
35.   return;
    
36. }
    
37. 
    
38. void fflush_bits(state *s)
    
39. {
    
40.   if(s->bi_valid > 8)
    
41.   {
    
42.     //MSB first
    
43.     s->output[s->outing++] = (unsigned char)((s->bi_buf) >> 8);
    
44.     s->output[s->outing++] = (unsigned char)((s->bi_buf) & 0xff);
    
45.   }
    
46.   else
    
47.   {
    
48.     s->output[s->outing++] = (unsigned char)((s->bi_buf) & ((1<<s->bi_valid) - 1));
    
49.   }
    
50.   s->bi_buf = 0;
    
51.   s->bi_valid = 0;
    
52.   return;
    
53. }
    
54. 
    
55. int main()
    
56. {
    
57.   state *s;
    
58.   s = calloc(1, sizeof(state));
    
59. 
    
60.   strcpy(s->input, "123456789abc");
    
61. 
    
62.   unsigned char ch;
    
63.   
    
64.   //删除一天
    
65.   ch = s->input[s->ining++];
    
66.   send_bits(s, ch, 7);
    
67.   
    
68.   while(s->ining < strlen(s->input))
    
69.   {
    
70.     ch = s->input[s->ining++];
    
71.     send_bits(s, ch, 8);
    
72.   }
    
73.   
    
74.   //新增一天, 假设1
    
75.   if(1)
    
76.   {
    
77.     send_bits(s, 0x8, 1);
    
78.   }
    
79.   else
    
80.   {
    
81.     send_bits(s, 0x0, 1);
    
82.   }
    
83.   
    
84.   //清空buf
    
85.   fflush_bits(s);
    
86.   
    
87.   int i;
    
88.   for(i = 0; i < strlen(s->input); i++)
    
89.   {
    
90.     printf("%02hhx ", s->output[i]);
    
91.   }
    
92.   printf("%02hhx\n", s->output[i]);
    
93.    
    
94.   return(0);
    
95. }
    

复制代码

qakito

如果只是要位图的话，有现成的fd_set可以使用。