位运算实验(上)

Data Lab: Manipulating Bits #1 - 对于实验一(Data Lab)的一些想法(上)。

这个实验要求学生实现简单的逻辑和算术运算函数,但是只能使用一个非常有限的C语言子集。比如,只能用位级操作来计算一个数字的绝对值。这个实验可帮助学生了解 C语言数据类型的位级表示,以及数据操作的位级行为。

Puzzle 1 - isAsciiDigit

isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters ‘0’ to ‘9’)
Examples: isAsciiDigit(0x35) = 1
isAsciiDigit(0x3a) = 0
isAsciiDigit(0x05) = 0
Legal ops: ! ~ & ^ | + << >>
Max ops: 15
Rating: 3

本题应首先判断参数x是否介于0x300x39之间,但实验要求不可使用if等语句,应该考虑位运算的方法。

我们知道,参数x介于0x300x39之间,等价于x - 0x30的结果为非负,且x - 0x3a的结果为负。从而可以利用正数与负数的符号位的区别进行进一步运算。

同时注意实验要求不可使用减法运算符,可以用“取反加一”的方法代替之。

1
2
3
4
5
6
7
8
int isAsciiDigit(int x)
{
int lowCmp = x + ~0x30 + 1;
int highCmp = x + ~0x3a + 1;
lowCmp >>= 31;
highCmp >>= 31;
return ((!lowCmp) & !!(highCmp));
}

Puzzle 2 - anyEvenBit

anyEvenBit - return 1 if any even-numbered bit in word set to 1
Examples: anyEvenBit(0xA) = 0, anyEvenBit(0xE) = 1
Legal ops: ! ~ & ^ | + << >>
Max ops: 12
Rating: 2

本题需要对参数x的偶数位进行判断,故可以利用偶数位全为1、奇数位全为0的“模版”辅助判断。

注意实验要求使用的常数应保证在0~255之间,故可以多次左移来将模版扩大为需要的长度。

同时注意要求中的any even-numbered bit in word set to 1意为只要存在某一偶数位为1即可,并非要求所有偶数位全部为1。所以其反义为“所有偶数位全为0”。

1
2
3
4
5
6
7
8
int anyEvenBit(int x)
{
int a = 0x55;
int b = (a << 8) + a;
int c = (b << 8) + a;
int d = (c << 8) + a;
return !!(x & d);
}

Puzzle 3 - copyLSB

copyLSB - set all bits of result to least significant bit of x
Examples: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
Legal ops: ! ~ & ^ | + << >>
Max ops: 5
Rating: 2

本题可以利用算术右移时高位填充与符号位有关的特点来解。

1
2
3
4
int copyLSB(int x)
{
return x << 31 >> 31;
}

Puzzle 4 - leastBitPos

leastBitPos - return a mask that marks the position of the least significant 1 bit. If x == 0, return 0
Example: leastBitPos(0x60) = 0x20
Legal ops: ! ~ & ^ | + << >>
Max ops: 6
Rating: 2

一个数的编码中,“1”所在的位权最小的位的低位全为0,即为“…100…0”的形式(记作1)。按位取反,变为“…011…1”的形式(记作2),再加1得到“…100…0”的形式(记作3)。其中形式3中的“1”的高位与形式2的对应位相同,即与形式1(原数)相反。

形式3即原数的相反数,故可以将参数x与其相反数按位与,较高位均变为0,只保留了“1”所在位权最小位。

1
2
3
4
5
int leastBitPos(int x)
{
int _x = ~x + 1;
return x & _x;
}

Puzzle 5 - divpwr2

divpwr2 - Compute x/(2^n), for 0 <= n <= 30
Round toward zero
Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
Legal ops: ! ~ & ^ | + << >>
Max ops: 15
Rating: 2

首先可能想到直接对参数x进行右移,但注意右移为算术右移,负数的右移可能会得到错误的结果。

负数除以$2^n$,可以看作它的相反数除以$2^n$后再取相反数。取相反数即“取反加一”,也就是说,当参数x < 0时,x / $2^n$ 与~((~x + 1) >> n) + 1等价。基于此,下面讨论一下此表达式具体的算法。

前提x < 0。首先计算(~x + 1) >> n,不难看出结果与~x的低n位有密切联系,而~xx按位取反而来,有以下两种情况:

  • x的低n位全部为0时,~x运算后的低n位全部变为1,再加1即“等价于”(对较高位来说)在第n位加1(整体加上1 << n),故~x + 1n位至第31位(认为最低位为第0位,下同)与~x + (1 << n))的相同。则~((~x + 1) >> n) + 1 = ~((~x + (1 << n)) >> n) + 1 = ~(~x >> n + 1) + 1,此即~x >> n + 1的相反数。而~(~x >> n) + 1~x >> n的相反数,即满足~(~x >> n) + 1 + ~x >> n = 0,故所求~x >> n + 1的相反数为~(~x >> n),即x >> n
  • x的低n位不全为0时,即至少某一位为1,~x运算后该位变成0,其他位为1,再加1后的进位一定进到了最低的0上,而不会影响到较高位。故~x + 1n位至第31位~x的相同。则~((~x + 1) >> n) + 1 = ~(~x >> n) + 1 = (x >> n) + 1

可以看出,当x为负数时,只有低n位不全为0时才需要加1。

1
2
3
4
5
6
7
int divpwr2(int x, int n)
{
int sig = !!(x >> 31);
int msk = (1 << n) + ~0;
int xLowN = msk & x;
return (x >> n) + ((!!xLowN) & sig);
}

Puzzle 6 - bitCount

bitCount - returns count of number of 1’s in word
Examples: bitCount(5) = 2, bitCount(7) = 3
Legal ops: ! ~ & ^ | + << >>
Max ops: 40
Rating: 4

查找“1”一共有多少位,首先可能想到按照每一位进行查找,但此时运算符总数会超出上限。所以我们可以把参数x划分为8部分,用“模版”0001 0001 0001 0001 0001 0001 0001 0001来比较,并比较4次。

获得模版的方法同Puzzle 2

设比较的结果为sum,比较完成之后可以发现,我们已经把参数x的8部分中各自“1”的总数存放在了sum对应的$1/8$部分中,然后将这8部分进行3次“对折”,即可将8部分各自总数加到一起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int bitCount(int x)
{
int msk, sum;

msk = 0x11 | (0x11 << 8);
msk = msk | (msk << 16);

sum = x & msk;
sum += (x >> 1) & msk;
sum += (x >> 2) & msk;
sum += (x >> 3) & msk;

msk = 0xff | (0xff << 8);
sum = (sum >> 16) + (sum & msk);

msk = 0xf | (0xf << 8);
sum = ((sum >> 4) & msk) + (sum & msk);

msk = 0xff;
sum = (sum & msk) + (sum >> 8);

return sum;
}

Puzzle …

同时也要注意代码的规范问题,利用辅助工具可以协助提高代码的质量。

例如,运行./btest以检查函数功能的正确性:

btest

运行./dlc -e bits.c以检查每个函数的运算符使用情况:

dlc

运行./driver.pl以同时输出dlcBDD checker的结果:

driver