首页程序设计基础R - 2024 级程序设计基础复习赛
时间限制 内存限制
1000 ms 65536 KB

# 题目描述

给出两个整数 A,BA,B 和一个四进制位运算符 opop，求 AA 和 BB 在四进制下进行 opop 运算的结果。

op∈op∈ {与 & , 或 | }，记 a,ba,b 为一位的四进制数，真值表如下：

  • 与运算：
aa 与 bb b=0b = 0 b=1b = 1 b=2b = 2 b=3b = 3
a=0a = 0 00 00 00 00
a=1a = 1 00 11 11 11
a=2a = 2 00 11 22 22
a=3a = 3 00 11 22 33
  • 或运算：
aa 或 bb b=0b = 0 b=1b = 1 b=2b = 2 b=3b = 3
a=0a = 0 00 11 22 33
a=1a = 1 11 11 22 33
a=2a = 2 22 22 22 33
a=3a = 3 33 33 33 33

# 输入格式

不定组输入，不超过 100000100000 组，每组一行：

每行依次为 A,op,BA,op,B，中间用一个空格间隔。

保证 A,BA,B 均为十进制表示的 unsigned int 范围内整数；opop 一定是 & ， | 中的一个。

# 输出格式

每组一行，11 个 十进制表示的 无符号整数，为 A,BA,B 在四进制下进行 opop 运算的结果。

# 输入样例

6 & 9
6 | 9

# 输出样例

5
10

# 提示

不妨观察一下对于四进制位 a,ba, b， a & b 跟 a | b 与 a,ba, b 之间的关系吧。

# 题解：位运算

不难发现，与运算就是该位两个数取最小值，或运算就是取最大值，于是我们按题意模拟即可。

时间复杂度：O(Tlog⁡n)O(T \log n)，其中 TT 为数据组数，nn 为值域。

参考代码：

#include <stdio.h>
typedef unsigned int uint;
uint a, b;
char op;
uint min(uint a, uint b)
{
    return (a < b) ? a : b;
}
uint max(uint a, uint b)
{
    return (a > b) ? a : b;
}
int main()
{
    // freopen("X.in", "r", stdin);
    // freopen("X.out", "w", stdout);
    while (~scanf("%u %c %u", &a, &op, &b))
    {
        int cnt = 0;
        uint res = 0;
        while (a || b)
        {
            uint bitA = a & 3, bitB = b & 3;
            uint bit;
            if (op == '&')
                bit = min(bitA, bitB);
            else
                bit = max(bitA, bitB);
            
            res |= bit << (cnt << 1);
            a >>= 2, b >>= 2, ++ cnt;
        }
        printf("%u\n", res);
    }
    return 0;
}