/* * bitAnd - x&y using only ~ and | * Example: bitAnd(6, 5) = 4 * Legal ops: ~ | * Max ops: 8 * Rating: 1 */ int bitAnd(int x, int y) { //~(a&b) = ~a | ~b; //a&b = ~(~a | ~b); return ~((~x) | (~y)); }
根据德摩根律~(x&y) = (~x | ~y)
/* * getByte - Extract byte n from word x * Bytes numbered from 0 (LSB) to 3 (MSB) * Examples: getByte(0x12345678,1) = 0x56 * Legal ops: ! ~ & ^ | + << >> * Max ops: 6 * Rating: 2 */ int getByte(int x, int n) { return (x>>(n<<3)) & 0xFF; }
移码后使用掩码
/* * logicalShift - shift x to the right by n, using a logical shift * Can assume that 0 <= n <= 31 * Examples: logicalShift(0x87654321,4) = 0x08765432 * Legal ops: ! ~ & ^ | + << >> * Max ops: 20 * Rating: 3 */ int logicalShift(int x, int n) { int mask = ~(((1<<31)>>n)<<1); return mask & x>>n; }
只进行x>>n，如例子，会得到0xf8765432, 所以要用0x0fffffff, 这个值不容易直接得到，但是可以通过0x1000000取反得到。
/* * bitCount - returns count of number of 1's in word * Examples: bitCount(5) = 2, bitCount(7) = 3 * Legal ops: ! ~ & ^ | + << >> * Max ops: 40 * Rating: 4 */ int bitCount(int x) { int mask1 = 0x55555555; int mask2 = 0x33333333; int mask3 = 0x0f0f0f0f; int mask4 = 0x00ff00ff; int mask5 = 0x0000ffff; x = (x&mask1)+((x>>1)&mask1); x = (x&mask2)+((x>>2)&mask2); x = (x&mask3)+((x>>4)&mask3); x = (x&mask4)+((x>>8)&mask4); x = (x&mask5)+((x>>16)&mask5); return x; }
算法来自于http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
依照http://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators中的解释是使用了分而治之的方法
/* * bang - Compute !x without using ! * Examples: bang(3) = 0, bang(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ int bang(int x) { return ~((x|(~x+1)) >> 31) & 1; }
在补码表示中，只有0可以做到原码和补码的符号位一样，其它任何数的补码和原码的符号位都是相反的。
应当注意!和~的区别。
/* * 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 */ int fitsBits(int x, int n) { int r, c; c = 33 + ~n; r = !(((x << c)>>c)^x); return r; }
判断x的范围是否在-2^(n-1) ~2^(n-1)-1之间，如果在，则x不会因为左右移动(32-n)发生溢出而改变。
/* * divpwr2 - Compute x/(2^n), for 0 <= n <= 30 * Round toward zero * Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2 * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 2 */ int divpwr2(int x, int n) { //all zeros or all ones int signx=x>>31; //int mask=(1<<n)+(-1); int mask=(1<<n)+(~0); int bias=signx&mask; return (x+bias)>>n; }
可以见中文CSAPP里的P65有推导过程。我们需要除法向零舍入，但是在负数情况下右移操作会让除法向负无穷舍入，所以需要加上一个bias。
/* * isPositive - return 1 if x > 0, return 0 otherwise * Example: isPositive(-1) = 0. * Legal ops: ! ~ & ^ | + << >> * Max ops: 8 * Rating: 3 */ int isPositive(int x) { return !((x>>31)&1); }
根据符号位不同，>>31后可以得到32个1或者32个0。
/* * 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 signx=x>>31; int signy=y>>31; int signSame=((x+(~y))>>31)&(!(signx^signy)); int signDiffer=signx&(!signy); return signDiffer|signSame; }
当符号相同时， x+(~y) = x-y-1, 如果x-y>0, 那么 x-y-1 >= 0，即符号位为0; 如果x-y<=0, 那么x-y-1<0， 即符号位为1；
当符号不相同时，若x>0且y<0，那么也符合条件
/* * ilog2 - return floor(log base 2 of x), where x > 0 * Example: ilog2(16) = 4 * Legal ops: ! ~ & ^ | + << >> * Max ops: 90 * Rating: 4 */ int ilog2(int x) { //binary search +16 +8 +4 +2 +1 int bCnt = (!!(x>>16))<<4; bCnt = bCnt +((!!(x>>(bCnt+8)))<<3); bCnt = bCnt +((!!(x>>(bCnt+4)))<<2); bCnt = bCnt +(!!(x>>(bCnt+2))<<1); bCnt = bCnt +(!!(x>>(bCnt+1))); return bCnt; }
以第一步为例，x>>16并且两次逻辑非，那么若x>>16大于零则得到1，说明对应log(x) >= 4，于是1<<4
/* * float_neg - Return bit-level equivalent of expression -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 representations of * single-precision floating point values. * When argument is NaN, return argument. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 10 * Rating: 2 */ unsigned float_neg(unsigned uf) { unsigned result; unsigned tmp; tmp=uf&(0x7fffffff); result=uf^0x80000000; if(tmp>0x7f800000) result=uf; return result; }
0x7fffffff取取除了符号位剩下的位;
对0x80000000异或可以让符号位取反;
if语句中判断0x7f800000，代表着浮点数中的exp字段全为1，即NaN的判断（exp字段全为1，frac字段不为0），当uf is NaN时返回uf，否则返回-f。
/* return 1 if x contain even 1s, 0 otherwise; assume x = 32w */ int even_ones(unsigned x) { int temp = x >> 16 ^ x; temp = temp >> 8 ^ temp; temp = temp >> 4 ^ temp; temp = temp >> 2 ^ temp; temp = temp >> 1 ^ temp; return !(temp & 1); }
每次将伪码对半比较，判断其中1的个数
以1100 0110为例，第一次对半比较 1100^0110 = 1010，第二次对半比较 10^10 = 00， 第三次对半比较 0^0=0， 也就是说最后一次比较后得到的数的最后一位为0，则最初的数中含偶数个1，否则含奇数个1；为了取得这个数，我们使用 &1单独拿出，并取！符合题目条件。
/* * float_i2f - Return bit-level equivalent of expression (float) x * Result is returned as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point values. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsigned float_i2f(int i) { if(i == 0) return 0; unsigned x = i>0?i:-i; int sign = i>0?0:1; int w = sizeof(int)<<3; int j; for(j=w-1; j>=0; j--){ //ÕÒµ½×î¸ßλ if( (x>>j) & 1) break; } unsigned bias = 127; unsigned exp, frac; exp = bias + j; if(j <= 23) frac = x<<(23-j); else { frac = x>>(j-23); unsigned mask = (1<<(j-23)) - 1; if( (x&mask) > (1<<(j-24)) ) frac++; //ÐèÒªÉáÈëµ½´óÖµ else if( (x&mask) == 1<<(j-24) && (frac&1)) frac++; //ÉáÈ뵽żÊý if(frac == (1<<24)) exp++; //ÉáÈ뵽żÊý³¬¹ý(1<<24) - 1£¬Ö¸ÊýÐèÒªÔÙ¼Ó1 } return sign<<31 | exp<<23 | frac&0x7FFFFF; }
参考中文书P74一个将12345转为12345.0的实例
/* * 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(float_bits f){ unsigned sign = f>>31; unsigned exp = (f>>23) & 0xFF; unsigned frac = f&0x7FFFFF; if(exp == 0) return sign<<31 | frac<<1; else if(exp < 254) return sign<<31 | (exp+1)<<23 | frac; else if(exp == 254) return sign<<31 | 0xFF<<23; else return f; }
了解规范化与非规范化的差别