位操作 tricky

位操作 tricks

• int
• float

int

 //以下所有变量默认均为 int 类型
 !!x;  //缩位或 (x 非 0)
 !(~x);  //缩位与 (x 全 1)
    !(x^y);  //x==y
 ~x + 1;  //-x，如果 x 为 0x80000000，返回 0x80000000

 mask = x>>31;
 x = (~x+1) & mask | x & ~mask; //abs(x), mask 用法

 ~(~x & ~y); //x | y



/* 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)      //Mark
{
    //ref: https://github.com/jerrylzy/CS33/blob/master/Lab/datalab/bits.c
    /*
     * We first bit invert all negative numbers and
     * use binary search to find out the log2(n).
     * Then we add 1 to the final result since we need
     * the MSB to represent the sign.
     * Note: finding the following things are equal:
     * 1. find the most significant bit of 1 for positive numbers
     * 2. find the most significant bit of 0 for negative numbers
     */
    int mask = x>>31;
    x = (x & ~mask) | (~x & mask);

    //the algorithem get the unsigned int bit width(Most Significant One bit to LSb)
    int bit16, bit8, bit4, bit2, bit1, bit0;
    bit16 = (!!(x>>16))<<4;
    x = x >> bit16;

    bit8 = (!!(x>>8))<<3;
    x = x >> bit8;

    bit4 = (!!(x>>4))<<2;
    x = x >> bit4;

    bit2 = (!!(x>>2))<<1;
    x = x >> bit2;

    bit1 = (x>>1)&1;
    x = x >> bit1;

    bit0 = x&1;

    return bit16 + bit8 + bit4 + bit2 + bit1 + bit0 + 1; //plus 1 for 2's complement's sign bit
}

//find the one bit number in x
int count_one_8(unsigned int x){
    /*
     * Firstly, we split the 32 bits to 11 groups, 3 bits per group(except the last group), 
     * Then we can caculate the sum of 3 bits in eache group by  
     * expression: x - (x>>1) -(x>>2) = x2 + x1 + x0 (x=[x2, x1, x0])
     * Then we sum each two contiguous group by a shift-add: tmp + (tmp>>3)
     * The sum(after masked) will be (x0+x1+...x5) + (x6+x7+...x11)*(2^6)^1 + 
     * (x12+x13+...x17)*(2^6)^2+...
     * Last, we can get (x0+x1+...x63)%63 by caculate the sum mod 63.
     */
    unsigned int tmp;
    tmp = x - ((x>>1)&033333333333) - ((x>>2)&011111111111);
    return ((tmp + (tmp>>3))&030707070707)%63;
}

//same way with 4 bits per group
int count_one_16(unsigned int x){
    unsigned int tmp;
    tmp = x - ((x>>1)&0x77777777) - ((x>>2)&0x33333333) - ((x>>3)&0x11111111);
    return ((tmp + (tmp>>4))&0x0f0f0f0f)%255;
}

float

//float
/* 
 * 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 int m = uf&0x7fffff;
    unsigned int exp = (uf>>23)&0xff;
    unsigned int symbol = uf>>31;
    if(exp==255){
        return uf;
    }else if(exp==0){
        if(m&0x400000){
            exp++;
            m<<=1;
        }else{
            m<<=1;
        }
    }else{
        exp++;
    }
    return (symbol<<31) | (exp<<23) | (m&0x7fffff);
}

/* 
 * 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 m = uf&0x7fffff;
    int exp = ((uf>>23)&0xff) - 127;
    int symbol = uf>>31;
    int out = 0;

    //[-2^31, 2^31-1]
    if(exp<0){
        return 0;
    }else if(exp<=23){
        out = (0x800000|m)>>(23-exp);
    }else if(exp<=30){
        out = (0x800000|m)<<(exp-23);
    }else{
        return 0x80000000;
    }
    return symbol ? ~out + 1 : out;
}