思考:仅用一个变量存储影院占座信息

问题描述


如下图所示,我们需要用一个long变量存储一场电影的占座信息(假如电影的座位是5x9个)。并实现:占座购买,判断是否已购,取消占座, 三个业务接口。

解决方法


显然,上图中每个座位的状态只有两种:1.已购 2.可购。我们很容易能想到二进制有这样的特点,所以,我们只需要将long变量看成是一个能存储1和0两个状态位的长条形纸张就行了。

比如下图这样:

我们需要做的有这么几件事情:
1.将x排y座转换成上图中的编号(0~63)
2.设置存储编号i的数据状态位 (1 或 0)
3.读取编号i的数据状态位 (1 或 0 )

我们来根据上诉需求设计接口,先是位运算相关的4个底层接口:

// 获取data中第i位的数据
unsigned char getBit( unsigned long data , int i  );
// 设置data的第i位数据为bit
void setBit(unsigned long *data , unsigned char bit , int i  );
// 2维坐标转一唯
int _2dTo1D(int y ,int x ) ;
 // 输出一个long变量的位信息,(测试用)
void print_bits(unsigned long d );

然后是应用层的接口:

// 判断是否购买
int isBuy(unsigned long data,int y,int x );
// 购买占座
void buy(unsigned long *data,int y ,int x );
// 取消购买占座
void cancleBuy(unsigned long *data,int y ,int x);

补充一些基础


位运算操作符

& 按位与 例如 1001 & 1010 = 1000
| 按位或 例如 1001 | 1010 = 1011
^ 按位异或 例如 1001 ^ 1010 = 0011
<< 左移 例如 1001 << 2 = 100100
>> 右移 例如 1001 >> 2 = 10
~ 按位求反 例如 ~1001 = 0110

按位与 常常用于屏蔽某些二进制位,比如,10101 & 11100 = 10100 ,最后两位被屏蔽了,还有我们熟悉的子网掩码也是这个道理。
按位或 常常用于将某些二进制位设置为 1 ,比如 x = x | SET_BIT ,将x中对应 SET_BIT中为1的那些二进制设置位 1

实现接口 & 案例测试


getBit接口的原理图

setBit接口的原理图

然后将第i位设置为我们期待的数据(0或1两种情况)
将第i位设置为0的情况

将第i位设置为1的情况

最上面生成屏蔽第i位掩码m生成的原理

完整的代码


#include 
#include 
#include 
#include 
#define MAX_SIZE 100
/*
    底层接口
 */

unsigned char getBit( unsigned long data , int i  ) {
    data  = data >> i ;
    return data & 1 ;
}

void setBit(unsigned long *data , unsigned long bit , int i  ){
    unsigned long mask = ~(1 << i) ; //0001 -> 0100 ->1011 设置掩码
    *data = *data & mask; // 将第 i 位设置位0
    *data = *data | bit << i;
}

int _2dTo1D(int y ,int x ) {
    return (y-1) * 9 + (x-1);
}

void print_bits(unsigned long d ) {
    if( !d ) {  return; }
    print_bits(d>>1);
    printf("%ld",d & 1);
}

/*
 业务层接口
 */
int isBuy(unsigned long data,int y,int x ){
    return getBit(data, _2dTo1D(y, x ));
}
void buy(unsigned long *data,int y ,int x ){
    // 将指定位置的二进制设置为 1
    setBit(data, 1, _2dTo1D(y, x));
}
void cancleBuy(unsigned long *data,int y ,int x){
    // 将指定位置的二进制设置为 0
    setBit(data, 0, _2dTo1D(y, x));
}
int main(int argc, const char * argv[]) {

    unsigned long data = 0; // 存储电影院占座信息的变量
    // 设置图中的已购信息 分别是
    // 2排4座 3排3座 3排4座 3排4座 3排5座 3排6座 5排3座

    buy(&data, 2, 4); // 2排4座 已购
    buy(&data, 3, 3); // 3排3座 已购
    buy(&data, 3, 4); // 3排4座 已购
    buy(&data, 3, 5); // 3排5座 已购
    buy(&data, 3, 6); // 3排6座 已购
    buy(&data, 5, 3); // 5排3座 已购
    print_bits(data);
    printf("\n");
    // 输出 100000000000000111100000001000000000000

    // 接着我们尝试下判断某个座位是否已被购买
    char * out[2]={"未被购买","已购"};
    printf("%d排%d座 %s\n",3,6,out[isBuy(data, 3, 6)]);
    printf("%d排%d座 %s\n",5,3,out[isBuy(data, 5, 3)]);
    printf("%d排%d座 %s\n",5,1,out[isBuy(data, 5, 1)]);
    printf("%d排%d座 %s\n",1,3,out[isBuy(data, 1, 3)]);
    /*
     输出结果为:
     3排6座 已购
     5排3座 已购
     5排1座 未被购买
     1排3座 未被购买
     */

    // 然后我们尝试 购买 5排1座 和 1排3座这两个座位
    buy(&data, 5, 1);
    buy(&data, 1, 3);

    printf("%d排%d座 %s\n",3,6,out[isBuy(data, 3, 6)]);
    printf("%d排%d座 %s\n",5,3,out[isBuy(data, 5, 3)]);
    printf("%d排%d座 %s\n",5,1,out[isBuy(data, 5, 1)]);
    printf("%d排%d座 %s\n",1,3,out[isBuy(data, 1, 3)]);

    /*
        这次的输出结果:
     3排6座 已购
     5排3座 已购
     5排1座 已购
     1排3座 已购
     */

    // 尝试取消购买  1排3座
    cancleBuy(&data, 1, 3);
    printf("%d排%d座 %s\n",3,6,out[isBuy(data, 3, 6)]);
    printf("%d排%d座 %s\n",5,3,out[isBuy(data, 5, 3)]);
    printf("%d排%d座 %s\n",5,1,out[isBuy(data, 5, 1)]);
    printf("%d排%d座 %s\n",1,3,out[isBuy(data, 1, 3)]);
    /*
     这次的输出:
     3排6座 已购
     5排3座 已购
     5排1座 已购
     1排3座 未被购买
     */
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注