Lab1
bit0r
/*
* bitOr - x|y using only ~ and &
* Example: bitOr(6, 5) = 7
* Legal ops: ~ &
* Max ops: 8
* Rating: 1
*/
用~和&实现|的功能
取反和与
与
int bitOr(int x, int y) {
return ~(~x & ~y);
}
离散数学问题
fitsShorts
/*
* fitsShort - return 1 if x can be represented as a
* 16-bit, two's complement integer.
* Examples: fitsShort(33000) = 0, fitsShort(-32768) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 1
* 十六位可以表示不可以就拜拜
*/
功能：32的补码是否可以被16位的机器数表示
32位的机器数对于正数来说就是
16*0+16有效位
对于负数而言，16*1+16位有效位
(x>>15)>>16 = x>>15这个没什么问题
借用亦或来判断相等，如果相等那么两个数亦或还是0，如果两数不等这时候是1
int y = x >> 15;
return !( (y >> 16) ^ y);
右移十五位清楚有效位，再右移十六位此时按道理清理的位数是没什么用的
这里还是有个类=雷区的
1、~：位运算符将数字视为二进制值,并按位进行相应运算,运算完成后再重新转换为数字。
2、!：使用逻辑运算符的表达式,返回0表示”假”,返回1表示 ”“真” 。
isTmin
/*
* isTmin - returns 1 if x is the minimum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
* 是不是三十二位补码中最小的那个数，1后面32个0
*/
32位补码中最小的那位数应该是32位数除了第一位符号位为1，其余为0
int isTmin(int x) {
return !(x+x)&!!(x);
}
首先，要判断是最小补码的数，可以尝试与这个数亦或，或者就是左移一位就变成全0了，这时候又要排除另一种情况就是全0的时候其实也会左移全0
！这里是逻辑运算符，上面一个函数下面的注解也备注了！~两者之间的关系，这边假设x是一个全0的数然后！x是先强制把x转换成为了bool类型。！x表示为真再次！然后会为假，这里目的就达成了，后面为假整个就不可能返回成真。(x+x)这里起到的其实是一个左移<<1的作用，但题目给出的运算符中并没有。如果左移后全都是0，这时候可以强制转为bool类型，判断出是不是32位补码中最小的那个数。
allEvenBits
/*
* allEvenBits - return 1 if all even-numbered bits in word set to 1
* Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
* 如果所有偶数位为1，返回1
*/
偶数亦或0x55555555
奇数亦或0xAAAAAAAA
int allEvenBits(int x) {
int a = 0x55;
int b = (a << 8) + a;
int c = (b << 8) + a;
int d = (c << 8) + a;
return !((x & d)^d);
}
上面是搜的
int allEvenBits(int x) {
int d = 0x55555555;
return !((x & d)^d);
}
下面这个自己改的，其实差不多,如果前面（x&d）存在0，0^1==1,然后强制!,返回0，反之返回1
negate
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
* 取负
*/
取反+1，没什么毛病
byteNot
/*
* byteNot - bit-inversion to byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByteNot(0x12345678,1) = 0x1234A978
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
* 对某字节取反，取反第n个字节到x个字节
*/
一个字节是8比特A^0=A , A^1 = 非A。将x的第n个字节的每位都与1异或，实现取反
int byteNot(int x, int n) {
int y = 0xff;
n = n<<3;
y = y<<n;
x = (x^y);
return x;
}
从字x到字节n的位反转,n~x位是前n~x位所以左移n<<3位，y这时候剩下的是前面n~x的1跟x的前n位亦或，就成功了
byteSwap
/*
* byteSwap - swaps the nth byte and the mth byte
* Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
* byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
* You may assume that 0 <= n <= 3, 0 <= m <= 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 25
* Rating: 2
* 字节交换
*/
int byteSwap(int x, int n, int m){
int n_shift = n << 3;//化为字节数
int m_shift = m << 3;
int p = ( ( x >> m_shift ) ^ ( x >> n_shift) ) & 0xFF;//x整体右移m字节亦或上x整体亦或n字节之后的结果&0xFF
return x ^ ( ( p << m_shift ) | ( p << n_shift ) );
}
将需要交换的2个byte分别扣（与运算）出来，再错位放入（或运算)(原话出自https://www.jianshu.com/p/50d1bfd5bab7)
fitsBits
/*
* fitsBits - return 1 if x can be represented as an
* n-bit, two's complement integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
* x是否可以表示为n位的补码
* -2^(n-1)~2^(n-1)-1
*/
int fitsBits(int x, int n)
{
int shiftnumber=32+~n+1;//32-n要转移的位数
int x2=x<<shiftnumber>>shiftnumber;//先左移x位再右移x位
return !(x2^x);//是否与原数相等
}
addOK
/*
* addOK - Determine if can compute x+y without overflow
* Example: addOK(0x80000000,0x80000000) = 0,
* addOK(0x80000000,0x70000000) = 1,
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
* 做加法时是否溢出
*/
int addOK(int x, int y) {
int ans = x + y;
return !( ( ( x ^ ans ) & ( y ^ ans ) ) >> 0x1F );
}
右移十六位
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) {
x = !!x; // 0x01 or 0x00，其实就是一个强行把数字类型转化成bool类型的过程
x = ~x + 1; // 0xff or 0x00
return (x & y) | (~x & z);//如果x正确，x为0xff可以和y的每一位亦或，如果x为0，~x==-1那么z就可以被返回出去(这边python手动不知道为什么鬼-1&1==1)
}
假设x是真
bitMask
/*
* bitMask - Generate a mask consisting of all 1's
* lowbit and highbit
* Examples: bitMask(5,3) = 0x38
* Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
* If lowbit > highbit, then mask should be all 0's
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
* 返回一定的位模式
* 3~5位为1由low to high
*/
int bitMask(int highbit, int lowbit) {
int i = ~0; //-1
return (((i << highbit) << 1) ^ (i << lowbit)) & (i << lowbit);
}
它的lowbit到highbit位之间为1,其余都是0
lowbit低m位，highbit高n位
i<<(highbit+1)会得到highbit+2位为1其余为0
i<<lowbit会得到lowbit+1位为1其余为0
&之后变成类似
def bitMask(highbit, lowbit):
i = ~0
print(bin((i << highbit) << 1))
k=(i << highbit) << 1
print(bin(i<<lowbit))
print(k^(i << lowbit))
j=k^(i << lowbit)
#print(j&(i<<lowbit))
#print(bin(60))
return (((i << highbit) << 1) ^ (i << lowbit)) & (i << lowbit)
m=int(input())
l=int(input())
ans=bitMask(m,l)
print(bin(ans))
isLessOrEqual
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
* 小于等于返回1，否则返回0
*/
int isLessOrEqual(int x, int y)
{
int signx = (x >> 31) &0x1;//返回符号位，如果是正数那么是0，负数返回1
int signy = (y >> 31) &0x1;//负数为0
int isSameSign =! (signx ^ signy) ;//如果两者符号位相同返回1
int p=! ( ( (~x)+1+y ) >> 31);//这里相当于y-x的符号位在取反，如果y大返回1
int ans = ( isSameSign & p ) | ( ( !isSameSign ) & signx);//y大同号|异号且x小于0
return ans ;
}
rotateLeft
/*
* rotateLeft - Rotate x to the left by n
* Can assume that 0 <= n <= 31
* Examples: rotateLeft(0x87654321,4) = 0x76543218
* Legal ops: ~ & ^ | + << >> !
* Max ops: 25
* Rating: 3
*循环左移
*/
int rotateLeft(int x, int n) {
int y;
y=~((~0)<<n);//左移n位
x=(x<<n)+((x>>(32+(~n+1)))&y);//x先向左循环了n位然后又要把因为左移丢失的高位右移到最右边右移32-n位记得与上高位y(32-n高位为0)
return x;
}
isPower2
/*
* isPower2 - returns 1 if x is a power of 2, and 0 otherwise
* Examples: isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
* Note that no negative number is a power of 2.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 4
* 判断是否是2的幂次 ,32位
*/
int isPower2(int x) {
int y =x>>31;
return (!!x)&!(1&y)&!(x&(x-1));
}
y是x的符号位
！！x将x强行转化为bool类型，排除是0的情况
！1&y 如果x是正数就是0这时候！1&y==1,就排除了负数
我们发现若x==2^n则x-1的特征为[n-1,0]位均为1，所以x&(x-1)=0
float_f2i
/*
* float_f2i - 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，溢出返回0
*/
float_twice
/*
* float_twice - 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 float_twice(unsigned uf) {
unsigned s=uf&(1<<31); //取符号位
int exp=(uf>>23)&0xff; //取阶码
int frac=uf&((1<<23)-1); //取尾数
if((exp!=0xff)) //如果阶码值为255，且尾数部分不为0，则该数为非数值数
{
if(!exp) //如果阶码为0，则将尾数左移一位，在这种情况下如果尾数的最高位为1，则也可以移到阶码处，从而使得阶码值价一，这样就进入了规范化数的表示范围
{
if(frac&0x00400000)
exp++; //尾数最高位为1，阶码+1
frac = (frac << 1) & 0x007fffff;
//否则，尾数左移
}
else //如果阶码不为0
{
exp++;
if(exp==255)
frac=0; //如果所得阶码为255，将尾数设置为0，表示无穷大
}
} //省略else情况，即uf为NaN和无穷大数，在这种情况下，阶码已经全1，无论如何都不能改变了。
return s|(exp<<23)|frac;
}
sm2tc
int sign = x >> 31;
return (x ^ sign) + (((1 << 31) + 1) & sign);
/*
正数的补码是本身
符号位是0^x还是本身
绝绝子
正数亦或符号位是本身，
复数亦或符号位正好取反，
后面的2^31+1整个亦或符号位
亦或0是1，亦或1是0
(((1 << 31) + 1) & sign)
后面这半部分其实只要能跟着符号位是相反的就行
*/
原理：
函数实现的功能是将有符号数转化为二进制补码
首先有符号数本身是原码，转化成补码需要
正数原码是本身
负数按位取反末尾加1