常用位运算
image.png
只用~和&完成异或
~(p & q)= ~p | ~q
~(p | q) = ~p & ~ q
p ^ q = (p | q ) & (~p | ~q)
= ~(~p & ~q) & ~(p & q)
// 1
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y)
{
return ~(~x & ~y) & ~(x & y);
}
Tmin
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void)
{
return 1 << 31;
}
isTmax
对于Tmax 0111 有
0111 + 1 = 1000
~(0111 + 1) = 01111
所以
(0111 + 1) ^ 0111 = 0000
特例 -1也满足
~(1111 + 1) = 1111
所以要特判
// 2
/*
* 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 ^ ~(x + 1)) & !!(x + 1);
}
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
*/
用1010(A)去遮盖原数
int allOddBits(int x)
{
int y = 0xAAAAAAAA;
return !(y & ~(y & x));
}
negate
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x)
{
return ~x + 1;
}
isAsciiDigit
// 3
/*
* 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
*/
-x = ~x + 1
x >= 0
相当于
!(x >> 31 & 1)
int isAsciiDigit(int x)
{
int y = !(((0x39 + (~x + 1)) >> 31) & 1);
int z = !(((x + ~0x30 + 1) >> 31) & 1);
return y & z;
}
第二种解法
//x的必定为0101xxxx的形式
int a = !(x >> 4 ^ 0x3);
//x的最末4位
int b = x & 0xF;
int c = ~0xA + 1;
int e = 0x80 << 4;
//b > 0 必定
//b =< 9 则 b < 10
//b - A(10) < 0
//e = 0x800
int d = !!((b + c) & e);
return a & d;
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 = 1 的时候得到0xFFFF,然后用这个去&y返回
int conditional(int x, int y, int z)
{
int a = !!x;
// 1111 if x = 1
int b = ~a + 1;
int c = ~(y & ~b) + 1;
int d = ~(z & b) + 1;
return y + z + c + d;
}
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)
不能用x - y <=0 这样的思路去做,因为可能会溢出,比如
Tmax - Tmin = -1 <= 0 => Tmax <= Tmin 显然是错误的
int isLessOrEqual(int x, int y)
{
int a = x >> 31 & 1;
int b = y >> 31 & 1;
int c1 = (a & ~b); // x 为 - ,y 为 +
int c2 = (~a & b); // x 为 + ,y 为 -
int e = y + (~x + 1);
int flag = e >> 31;
return c1 | (!c2 & !flag);
}
首先取得x和y的符号位
如果x < 0,y > 0 那么必然返回1,所以有 c1 |
之后再看y - x >= 0 是否成立
这里要考虑溢出的情况,比如对于int4
x = 7,y = -7
y - x = -14 = 10010
截取后四位得到0010 > 0
所以要同时考虑flag和c2的值
对于y - x >= 0 即 flag = 0
如果c2 = 0则表示没有溢出,必然返回 1
如果c2 = 1则表示有溢出,必然返回0
logicalNeg
// 4
/*
* 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)
c语言中的右移
c使用算数右移
int logicalNeg(int x)
{
return ((x | (~x +1)) >> 31) + 1;
}
对于非0的数返回1,对于0返回1
先考虑~x + 1的情况x > 0的时候为 -1 (1111)
x为0或负数的情况~x + 1都为0
为了区分这两种,所以要加上x一起运算,如果是负数就会得到-1(1111)
howManyBits
/* 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)
思路,把32位的数字分成按照16,8,4,2,1这样来分割,如果对应的部分不为0,那么就加上对应的值,否则就看下一个位置,不停的右移
int howManyBits(int x)
{
int b16, b8, b4, b2, b1, b0;
int flag = x >> 31;
//如果x小于0那么就按位取反
x = (flag & ~x) | (~flag & x);
b16 = !!(x >> 16) << 4;
x >>= b16;
b8 = !!(x >> 8) << 3;
x >>= b8;
b4 = !!(x >> 4) << 2;
x >>= b4;
b2 = !!(x >> 2) << 1;
x >>= b2;
b1 = !!(x >> 1);
x >>= b1;
b0 = x;
return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}
floatScale2
unsigned floatScale2(unsigned uf)
{
//指数位
int exp = (uf & 0x7f800000) >> 23;
int sign = uf & (1 << 31);
if (exp == 0)
//frac * 2
return uf << 1 | sign;
if (exp == 255)
return uf;
//2^exp * 2 = 2^(exp + 1)
exp++;
if (exp == 255)
//正负无穷
return 0x7f800000 | sign;
//还原指数位
return (exp << 23) | (uf & 0x807fffff);
}
floatFloat2Int
int floatFloat2Int(unsigned uf)
{
unsigned exp = (uf & 0x7f800000) >> 23;
int sign = uf >> 31 & 0x1;
unsigned frac = uf & 0x7FFFFFFF;
int E = exp - 127;
if (E < 0)
return 0;
else if (E >= 31)
{
return 0x80000000u;
}
else
{
frac = frac | 1 << 23;
if (E < 23)//需要舍入
{
frac >>= (23 - E);
}
else
{
frac <<= (E - 23);
}
}
if (sign)
{
return -frac;
}
else
{
return frac;
}
}
浮点数的部分还是有点懵,回头再看看
