本笔记仅仅只是用于记录，内容为提示性，题主做的不一定完全符合规范！！！！。
本实验中，只有整型只能使用“+”和位运算符。后面浮点数可以用控制循环。
1.异或运算
直接用公式，或者像我这样利用真值表凑的
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
* bitXor - returns ~(x&y),where 0 <= x <= 31 and 0 <= y <= 31
* 在此处我们可以知道，异或可以检测x,y为不同数时，返回为1.
*/
int bitXor(int x, int y) {
return ~(x&y) & ~(~x&~y);
}
2.最小数
在有符号整数中，整数和负数的连接是一个类似循环队列，它利用模将数字限制在区间内。
也就是负数在(\(2^{w-1}-1 \thicksim 2^w\))
/*
* ! is negative logic result
* ~ is negative bits
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
* timin - returns 1<<31
*/
int tmin(void) {
return 1<<31;
}
3.判断x为最大值
在有符号数中，|Tmin|=|Tmax|+1:也就是说Tmin按位取反等于Tmax.
比如-8~7.1000按位取反0111.而0111+1发生正溢出,因为要限制在区间2^4,所以0111+1=1000=-8.
{还不熟悉，建议翻翻整数编码2.2.x小节}
此处Tmax先加1，正溢出后，Tmax转为Tmin，在按位取反变回Tmax，通过异或验证x是否为Tmax.
而minusOne就单纯是为了处理出现-1时的情况，因为其他情况都已经由(~(x+1)^x)决定。
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
int isTmax(int x) {
int minusOne = !(~x);
return !((~(x+1)^x)|minusOne);
}
4.所有奇数位是否都为1
提示:在异或中,我们已经说过，其可用于比较两数中是否存在不相同部分.
步骤:先利用掩码提取对应掩码数据，再利用异或判断，是否完全对应
若与mask完全对应，则~(xmask)mask为0，否则为1。
/*
* allOddBits - return 1 if all odd-numbered bits in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) {
int mask = 0xAA<<24;
mask = mask+(0xAA<<16)+(0xAA<<8)+(0xAA);
return !((x&mask)^mask);
}
5.相反数
提示:补码
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}
6.判断x是否为0~9ASCII码
输入数要求是正数，我们首先想到，当输入x时，其条件为48 <= x <= 57。
当x与这个条件的边界值相加后，利用符号进行判断位，查看是否是发生溢出，下届负溢出，上界正溢出
其中下届和上界都是补码表示形式
/*
* isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
* Example: isAsciiDigit(0x35) = 1.
* isAsciiDigit(0x3a) = 0.
* isAsciiDigit(0x05) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 3
*/
int isAsciiDigit(int x) {
int signflag = 1<<31; //signflag 符号位设置
int great = ~(0x30)+1; //下界
int less = ~(signflag+0x39);//上界
less = signflag & (less+x)>>31;
great = signflag & (great+x)>>31;
return !(great|less);
}
7.实现三元运算符
/*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
x = !!x; //转为是否为0或者1
x = ~x + 1; //取反
return (x&y)|(~x&z); //关键：当x为全1时,x&y=y，而~x&z=0；否则，反之
}
8.比较x<=y
提示：先判断x和y大于或小于0。笔者当时做的时候x和y是四种情况，然后再写结果情况。
最终建立真值表形式，就写出来了结果式。
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int result = y + ~x + 1;//y-x;
int signbit = (result>>31) &1;//取y-x结果的符号位,当y>=x时结果为0，否则为1
int sign_x = (x>>31) &1;//取x的符号位
int sign_y = (y>>31) &1;//取y的符号位
int sign_xXory = sign_x ^ sign_y;//判断x和y的符号位是否相同，即x和y是否同正负
return (!(sign_xXory|signbit)) | (sign_xXory&sign_x); //需要注意的是，当x<0，y>0时的情况
}
9.判断是否为0
/*
* logicalNeg - implement the ! operator, using all of
* the legal operators except !
* Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*
*/
int logicalNeg(int x) {
return !(x&(~0x0));//关注0就行，只有0与它的补码的与结果为0x0;
}
10.以二进制补码表示 x 所需的最小位数
提示：就是找第一次出现1的位置。此题因为在补码条件下所以更好做一点。
利用折半查找的思想，先查找高16位是否含1，如果含有，则继续查找确定第一次出现1的位置，一直查找到遍历结束。
/* howManyBits - return the minimum number of bits required to represent x in
* two's complement
* Examples: howManyBits(12) = 5
* howManyBits(298) = 10
* howManyBits(-5) = 4
* howManyBits(0) = 1
* howManyBits(-1) = 1
* howManyBits(0x80000000) = 32
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int howManyBits(int x) {
// 原理：从高位到低位，找第一次出现1的位置，再加上符号位，则最少需要n+1个位；
int b16, b8, b4, b2, b1, b0; // 表示0~15、16~23、24~27、28~29、30、31的位置处是否含有1，也就是每个部分的最少位数.
int sign = x >> 31; // 取符号位
// 因为是在补码的情况下，需要区分x为正负数.如果x为正则不变，x为负则取反，按理来说这里应该是取补码，负数的补码取反+1，但是这题测试时如果加1反而还错了.
x = (sign^x);
//以下类似折半查找
//先从b16(高16位)开始找是否有1，若有则继续查找高位中第一次出现1的位置
//否则从b8(低16位)开始
b16 = !!(x >> 16) << 4;// 先看高16位是否含有1，若有则表示至少需要16位
x = x >> b16; // 若有1，则原数右移16位，因为上面已经确定第一次出现1的位置在高16位中。否则在低16位
b8 = !!(x >> 8) << 3; // 看剩余位是否有1，以下同理
x = x >> b8;
b4 = !!(x >> 4) << 2;
x = x >> b4;
b2 = !!(x >> 2) << 1;
x = x >> b2;
b1 = !!(x >> 1);
x = x >> b1;
b0 = x; //最后剩余的一位
return b16+b8+b4+b2+b1+b0+1; // 别忘记加上符号位
}