- Data Lab
- 位运算
- 1. bitXor
- 2.getByte
- 3.logicalShift
- 4.bitCount
- 5.conditonal
- 二进制补码运算
- 6.trim
- 7.fitsBits
- 8.dividePower2
- 9.negate
- 10.howmanyBits
- 11.isLessOrEqual
- 12.intLog2
- 浮点数计算
- 13.floatAbsVal
- 14.floatScale1d2
- 15.floatFloat2Int
| 符号 | 描 述 | 运算规则 |
|---|---|---|
| & | 与 | 两个位都为1时，结果才为1 |
| ｜ | 或 | 两个位都为0时，结果才为0 |
| ^ | 异或 | 两个位相同为0，相异为1 |
| ~ | 取反 | 0变1，1变0 |
| << | 左移 | 各二进位全部左移若干位，高位丢弃，低位补0 |
| >> | 右移 | 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移） |
题目要求：使用~和&实现异或 *** 作。
异或：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1）
a⊕b = (¬a ∧ b) ∨ (a ∧¬b)
int bitXor(int x, int y) {
return ~(~(x & ~y) & ~(~x & y));
}
题目要求：从字x中取出第n个字节
将x右移n*8位之后取出低8位的值，然后和255取交集，为了取低八位,让前面的数位归零。
详解 & 0xff 的作用
int getByte(int x, int n) {
//从整型x中取出第n个字节，只需要x往右移n个字节（即右移n*8位）之后再&上0xFF即可
return (x>>(n<<3)) & 0xFF;
}
题目要求：逻辑右移
逻辑右移和算术右移有什么区别：
“>>>” 逻辑右移
“>>” 算术右移
逻辑右移就是不考虑符号位，右移一位，左边补零即可
算术右移需要考虑符号位，右移一位，若符号位为1，就在左边补1；否则，就补0
所以算术右移也可以进行有符号位的除法，右移n位就等于除2的n次方
例如，8位二进制数11001101分别右移一位
逻辑右移就是[0]1100110
算术右移就是[1]1100110
思路是x>>n，x右移n位，然后与高n位为0的数&
(n=3)
1<<31:10000000000000000000000000000000
1<<31>>n:11110000000000000000000000000000
1<<31>>n<<1:11100000000000000000000000000000
~(1<<31>>n<<1):00011111111111111111111111111111
int logicalShift(int x, int n) {
return (x>>n)&~(1<<31>>n<<1);
}
题目要求：求出1的个数
采用分治思想：
- 将所有数分为32组，每组一个数
- 将相邻的两位合并，组中的数为原来两组数的相加
- 重复第2步，直到合成只有1组，组中的数值即为结果
可以看到最终的0x0000000F即为1的数量15
该算法能成功的关键在于一开始中每组中的数值即为每组中1的数量，然后将相邻两组中的数值相加的过程就相当于将之前一级的1的数量汇总，不断重复这个过程就可以将1的数量汇总到最后的一个数中。
有了算法我们还要考虑如何在题目的限制条件下实现这一算法。
为了实现将相邻两组中的值相加并放在合适的位置，我们采用掩码+位移的方式，例如有掩码：
`int mask1 = 0x55555555 (0101...0101)`
那么`x = x & mask1 + (x >> 1) & mask1;`实现了相加的过程，前面一部分先取出了一半的组，右移后再取出的就是后一半的组，再由按位相加的特点，它们相加后的值就存放在特定的位上（可以参照上面的图理解这一过程）。
接下来只要使用不同的掩码和不同的位移就可以一步步实现这一过程。
但是题目限制中我们只能使用0x00-0xFF的整型值，所以掩码也需要我们进行构造。
答案如下，注意到当剩下4组，每组8位的时候我们就可以直接位移相加再取出低8位得到它们的和。
分成两位一组
mask1:00000000000000000000000001010101
mask1<<8: 00000000000000000101010100000000
mask1|mask1<<8:00000000000000000101010101010101
mask1|mask1<<16:01010101010101010101010101010101
分成四位一组
mask2:00000000000000000000000000110011
mask2<<8:00000000000000000011001100000000
mask2|mask<<8:00000000000000000011001100110011
mask2|mask2<<16:00110011001100110011001100110011
分成八位一组
mask3:00000000000000000000000000001111
mask3<<8:00000000000000000000111100000000
mask3|mask3<<8:00000000000000000000111100001111
mask3|mask3<<16:00001111000011110000111100001111
int bitCount(int x) {
// referenced :
// https://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators
int mask1 = 0x55;
int mask2 = 0x33;
int mask3 = 0x0F;
int result = 0;
mask1 = mask1 | (mask1 << 8);
mask1 = mask1 | (mask1 << 16);
mask2 = mask2 | (mask2 << 8);
mask2 = mask2 | (mask2 << 16);
mask3 = mask3 | (mask3 << 8);
mask3 = mask3 | (mask3 << 16);
result = (x & mask1) + ((x >> 1) & mask1);
result = (result & mask2) + ((result >> 2) & mask2);
result = (result & mask3) + ((result >> 4) & mask3);
return (result + (result >> 8) + (result >> 16) + (result >> 24)) & 0xff;
}
题目要求：实现c语言中的x?y:z
若x的取值为0x00000000或0xFFFFFFFF。
则答案为(x&y)|(~x&z)。
若x！=0时，将x=0xFFFFFFFF。
x = (!!x)<<31>>31。
int conditional(int x, int y, int z) {
x = (!!x)<<31>>31;
return (y&x)|(z&~x);
}
题目要求：返回最小二进制补码
int tmin(void) {
return 1<<31;
}
题目要求：如果int型数据x可以表示为n位二进制补码整数（其中1 <= n <= 32）,则返回1，否则返回0。
如果x可以用n位补码表示，那么左移多余的位的个数后再右移回来的数值一定与原值相等，这个方法利用了左移后溢出的位会被丢弃，而右移回来时的是补符号位，如果丢弃了1或者右移时补的是1都会导致值的改变，而这两种情况也正说明了x不可以只用n位补码表示。
注意32-n=32+(~n+1)，a==b可以改写为!(a^b)
int fitsBits(int x, int n) {
int a = 33 + ~n;
return !((x << a >> a) ^ x);
}
题目要求：对于0 <= n <= 30，计算x /（2^n），向零舍入，返回计算结果，结果为int型
int divpwr2(int x, int n) {
//如果x为正数，则直接右移n位，即偏移量为0；如果x为负数则需要加偏移量2^n-1之后再右移n位
int signx=(x>>31);
int bias=signx & ((1<<n)+(~0)); //其中~0为-1
return (x+bias)>>n;
}
题目要求：返回int型数据x的相反数-x
int negate(int x) {
return (~x) + 1;
}
题目要求：判断x需要多少位补码表示
题目逐渐看不懂了……
int howManyBits(int x) {
int n = 0;
x ^= (x<<1);
n += ((!!(x&((~0)<<(n+16)))) << 4);
n += ((!!(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;
}
题目要求：x<=y
本题的基本思路是判断x-y得到的值是否小于等于0，但是要考虑溢出带来的影响，首先定义了两个变量xp,yp分别表示x,y是否大于等于0。
return的表达式的含义为并并非x大于等于0且y小于0的情况下（&的后半部分），如果x-y小于或等于0或x小于零且y大于等于0，则返回1
int isLessOrEqual(int x, int y) {
int sign_ = ((x&~y)>>31)&1;
int mark_ = ~((x^y)>>31);
int equl_ = !(x^y);
return sign_ | ((((mark_)&((x+~y+1))>>31)|equl_)&1);
}
题目要求：返回x求以2为底的对数的结果 向下取整
int ilog2(int x) {
int result = 0;
int b4 = !!(x >> 16);
int b3 = 0;
int b2 = 0;
int b1 = 0;
int b0 = 0;
result = b4 << 4;
b3 = !!(x >> (8 + result));
result = result | (b3 << 3);
b2 = !!(x >> (4 + result));
result = result | (b2 << 2);
b1 = !!(x >> (2 + result));
result = result | (b1 << 1);
b0 = !!(x >> (1 + result));
result = result | b0;
return result;
}
题目要求：计算f的绝对值的位级表示
判断浮点数是否为NaN，是返回，否则，将最高位（符号位）置为0返回。
判断exp段是否全为1，(uf&0x7f800000) >> 23 == 0xff。
判断frac段是否全为0，uf << 9 != 0。
unsigned floatAbsVal(unsigned uf) {
if((uf&0x7f800000)>>23 == 255 && uf<<9) return uf;
return uf & 0x7fffffff;
}
题目要求：算浮点数0.5*f
unsigned floatScale1d2(unsigned uf) {
int exp_ = (uf&0x7f800000) >> 23;
int s_ = uf&0x80000000;
if((uf&0x7fffffff) >= 0x7f800000) return uf;
if(exp_ > 1) return (uf&0x807fffff)|(--exp_)<<23;
if((uf&0x3) == 0x3) uf = uf + 0x2;
return ((uf>>1)&0x007fffff)|s_;
}
题目要求：将浮点数转换为有符号整数，float_f2i
int floatFloat2Int(unsigned uf) {
int s_ = uf>>31;
int exp_ = ((uf&0x7f800000)>>23)-127;
int frac_ = (uf&0x007fffff)|0x00800000;
if(!(uf&0x7fffffff)) return 0;
if(exp_ > 31) return 0x80000000;
if(exp_ < 0) return 0;
if(exp_ > 23) frac_ <<= (exp_-23);
else frac_ >>= (23-exp_);
if(!((frac_>>31)^s_)) return frac_;
else if(frac_>>31) return 0x80000000;
else return ~frac_+1;
}
1.详细版data lab题解
2.题目清晰版data lab题解
3.解答清晰版data lab题解
4.题目特别详细版data lab题解
5.详细版2 data lab题解
6.详细版3 data lab题解
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）