前言
lab1实验分为位操作、补码和浮点数三大部分，这两天尝试的是位操作和补码的实验，今天先总结位操作的解题。
位操作
每个题都规定了只能使用的操作符号，以及0-255的常数，声明int变量以及赋值，其余的操作都不行。
- bitAnd
要求：只能用非～和或 来实现与&操作。
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
return ~((~x)|(~y));
}
- getByte
取出第i字节（i=0,1,2,3），一个Byte是两个16进制数，也就是8bits，所以可以直接右移8×n位，然后取最后八位，就是&0xff
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int getByte(int x, int n) {
return (x>>(n<<3))&0xff;
}
- logicalShift
要求：实现一个integer的逻辑右移
思路：需要先计算出，原最高位在右移了n次之后在哪里，也就是31-n，但是这里不能用减法，只能用加法，所以就是y=31+（n的负数），n的负数位运算表示为~n+1。然后把x右移n位，去&一个低y全为1的数，这个数为(1«(y+1))-1。
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 0 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int logicalShift(int x, int n) {
int y = 32+(~n);
return (x>>n)&((1<<y)+(~0)+(1<<y));
}
- bitCount
要求：只用40次操作，并且不能用循环和if，计算x二进制表示中1的个数。
原理：首先需要设计5个常数，分别为0x55555555，0x33333333，0x0f0f0f0f，0x00ff00ff，0x0000ffff。然后下面的计算方法，和间隔对应，分别右移1,2,4,8,16次。
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) {
int _mask1 = (0x55)|(0x55<<8);
int _mask2 = (0x33)|(0x33<<8);
int _mask3 = (0x0f)|(0x0f<<8);
int mask1 = _mask1|(_mask1<<16);
int mask2 = _mask2|(_mask2<<16);
int mask3 = _mask3|(_mask3<<16);
int mask4 = (0xff)|(0xff<<16);
int mask5 = (0xff)|(0xff<<8);
int ans = (x & mask1) + ((x>>1) & mask1);
ans = (ans & mask2) + ((ans>>2) & mask2);
ans = (ans & mask3) + ((ans>>4) & mask3);
ans = (ans & mask4) + ((ans>>8) & mask4);
ans = (ans & mask5) + ((ans>>16) & mask5);
return ans;
}
ps:这一题和记忆中复试机试中一题很类似。
- bang
要求：对0返回1，其他数字返回0。
解题思路：发现只有0和-0的二进制中，最高位都不是1，其他数字x，x或者-x中总有一个的最高位为1，这个性质就可以很好的解决这个题，把x和-x或起来之后就解决了。
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
return ((~(x|(~x+1)))>>31)&1;
}
