第一个ICS的lab
配好了VMWare和Linux系统
默念了两天“我要死了”之后终于写完了
不是非常满意（尤其是howManyBits…）但至少是熬出来了…?
先记录一下思路，希望能在ddl之前优化howManyBits
初次提交结果：
是的，就是81步的蛮力算法?
Datalab的int部分是不能使用循环和条件的，只能用位运算实现
很简单的两个：
bitXor&tmin
/* * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1* Legal ops: ~ &* Max ops: 14* Rating: 1*/
int bitXor(int x, int y) {
int mark=(~x)&(~y);/*identify the 0&0 occasion*/return ~(x&y)&(~mark);
}
/* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + << >>* Max ops: 4* Rating: 1*/
int tmin(void) {
return 1<<31;
}
Tmax
卡住我的Tmax来了，不知为何用int temp=x+1就报错了…
用Xcode跑过temp版本结果是正确的…助教并不能帮助我…
- 至今不明原因，待以后再理解（或许是bug??
/** 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) {
return (!(x+2+x))&(!!(x+1));
}
allOddBits
试图简化allOddBits，未果…
然而标答的操作数更少
/* * 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 temp=0xAA+(0xAA<<8)+(0xAA<<16)+(0xAA<<24);return !((temp&x)^temp);
}
negate
没问题的一个
/* * negate - return -x * Example: negate(1) = -1.* Legal ops: ! ~ & ^ | + << >>* Max ops: 5* Rating: 2*/
int negate(int x) {
return ~x+1;
}
isAsciiDigit
这个想了挺久的，但是逻辑还是很清晰的
学会了用&控制输出条件的方法（用于排除否定情况）
/* * 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 x1=!((x>>4)^0x3),x2=!(((x&0xF)+0x6)&0x10);return x1&x2;
}
conditional
这个思路一开始就有，但是操作太多了
借鉴了一下网上大佬的写法，终于简化到最少
/* * 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) {
int temp=(~0)+!x;return (temp&y)+(~temp&z);
}
isLessOrEqual
有借鉴，学会了&、| 控制结果的方法（很有用嗷
- 学习操作更少的最佳写法
/* * 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 minus=x+(~y+1);
return(((minus>>31)&1)|(!(x^y))|(((x>>31)&1)&(!((y>>31)&1))))&(!(!((x>>31)&1)&((y>>31)&1)));
}
logicalNeg
这个是修改过思路的，只有0才会x和-x的符号位都是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) {
int neg=(~x)+1,temp=1<<31;return ((~((neg&temp)|(x&temp)))>>31)&0x1;}
howManyBits
蛮力算法它来了?
只能转换为正数先算出比特位，再根据条件（负数2的幂次方-1，因为首位可以充当符号位置）进行加减
学习了大佬的思路，用x^(x-1)判断是否2的幂次方
近几天再找新思路，希望能成功～
/* 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)
{
int temp=24,judge=0,x1=0,n=0,sign=x&(1<<31),xpos=((sign>>31)&(~x+1))+((~sign>>31)&x),t=0,zero=0,m=0,x2=0;judge=!(xpos>>24);temp+=(~(judge<<3)+1);judge=!(xpos>>16);temp+=(~(judge<<3)+1);judge=!(xpos>>8);temp+=(~(judge<<3)+1);x2=x1=((0xff<<temp)&xpos)>>temp;x1^=(x1<<1);
n+=(!!x1)+(!!(x1>>1))+(!!(x1>>2))+(!!(x1>>3))+(!!(x1>>4))+(!!(x1>>5))+(!!(x1>>6))+(!!(x1>>7));t=(!((xpos+(~0))&xpos))&(sign>>31);zero=!x;m=!!((x2&0xFF)&0x80);return n+temp+(~t+1)+m+zero;
}
float部分写的还挺顺利的，用循环条件很好解决
floatScale2 & floatFloat2int & floatPower2
重点在考虑无穷和溢出情况的取舍
/* * floatScale2 - Return bit-level equivalent of expression 2*f for* floating point argument f.* Both the argument and result are passed as unsigned int's, but* they are to be interpreted as the bit-level representation of* single-precision floating point values.* When argument is NaN, return argument* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while* Max ops: 30* Rating: 4*/
unsigned floatScale2(unsigned uf) {
unsigned e=0x7F800000&uf,m=0x7FFFFF&uf;if(!e) return (m<<1)|(uf&(0x1<<31));if(e!=0x7F800000) return (0x800000+uf);return uf;
}
/* * floatFloat2Int - Return bit-level equivalent of expression (int) f* for floating point argument f.* Argument is passed as unsigned int, but* it is to be interpreted as the bit-level representation of a* single-precision floating point value.* Anything out of range (including NaN and infinity) should return* 0x80000000u.* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while* Max ops: 30* Rating: 4*/
int floatFloat2Int(unsigned uf) {
int i=1,num1=0,sum=0,exp=1;unsigned s=0x80000000&uf,e=(0x7F800000&uf)>>23,m=0x7FFFFF&uf;num1=e-127;if(e>158) return 0x80000000u;if(e<127) return 0;for(i=0;i<num1;i++)exp*=2;sum=(s?(-1):1)*exp;if(!m) return sum;else if(m&0x400000){
if(m^0x400000) return !(sum%2)?sum:sum+1;else return sum+1;}else return sum;
}
/* * floatPower2 - Return bit-level equivalent of the expression 2.0^x* (2.0 raised to the power x) for any 32-bit integer x.** The unsigned value that is returned should have the identical bit* representation as the single-precision floating-point number 2.0^x.* If the result is too small to be represented as a denorm, return* 0. If too large, return +INF.* * Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while * Max ops: 30 * Rating: 4*/
unsigned floatPower2(int x) {
int e=x+127,exp=0,result=0;exp=(e>=0)?e:(-e);if(x>127) return 0x7F800000;if(x<-256) return 0x0;if(x==-256) return 0x40000000;else{
result=(exp<<23);return result;}
}
最后附上参考过的资料：
基本操作：https://blog.csdn.net/greatljc/article/details/97194030
刚上手Linux终端是很绝望的…看了这篇准备工作会好一点?
32位编译环境的配置：
https://blog.csdn.net/gezhiwu1213/article/details/78564455
Linux配的64位，但是这个程序似乎是32位运行的
卡了很久…不配置就无法检测
若出现延时问题，可以把makefile里的-m32改成-m64
来更新了…但是班里还是有好多大佬啊～
howManyBits 2.0
int howManyBits(int x) {
int n = 0;x^=(x<<1);//to locate the 1st left 1n+=((!!(x&((~0)<<(n+16)))) << 4);//find the 1st left 1n+=((!!(x&((~0)<<(n+8)))) << 3);n+=((!!(x&((~0)<<(n+4)))) << 2);n+=((!!(x&((~0)<<(n+2)))) << 1);n+=(!!(x&((~0)<<(n+1))));
return n+1;
}