LI@NG

bitcount & ilog2

ilog2看似比较简单,但是只用位操作符完成,并没有那么容易,同时这个题还略带“Binary Search”二叉树查询的一点思想,比较有意思,值得写一下来总结一下我做该题目的思路。

ilog2

实验要求:

/*
 * ilog2 - return floor(log base 2 of x), where x > 0
 *   Example: ilog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
 */

在位运算中,x « n 就相当于x*2^n, x » n 就相当于 x/2^n,那么该题要求给定一个x求以2位底的对数,其实就是求x/2^n中的n,那么这里的n就是向右移的位数,那么是什么向右移的位数呢,我们想一下对数的运算,就是不断除以2直到有余数或者被整除,通过分析能知道,求ilog2(n)就是看二进制的n中把“最高位”上的1,移动到最右端LSB所要经过的位数。比如:

1001  // 十进制是9,ilog(9) = 3

那么问题出现了,怎么判断最高位置的1在哪呢?基本思路就是,int是4个字节的32bits,所以我们先检测上16bits中有没有1,如果有1的话,那么右边16bits就没有存在的必要了,因为我们只关心n二进制最高位的1,然后再折半同样的思路。

int ilog2(int x) {
    int exp = 0;
    int cx = x;
    // 因为int 32bits,先二分查询
    int rx = x >> 16;
    // 结果是1如果做半部分包含1, 如果不包含则为0
    int qr = !!rx;
    // lsb = 0xffffffff if qr is 1, otherwise 0
    int lsb = (qr << 31) >> 31;
    // 如果上半部分包含1(也就是说qr === 1),那么我们需要将上半部分取出来,并且exp至少为16,所以加上16,下半部分就没用了
    // 如果上班部分不包含0(也就是说qr === 0),那么我们则需要继续对x进行进一步1/4检测
    // 这句表示,当qr为1的时候仅仅保留上半部分,当为0的时候,保留全部
    cx = (lsb & rx) | ((~lsb) & cx);
    // 接下来要对exp进行修改
    // 当上半部分包含1的时候,也就是qr === 1,那么exp至少16起步,如果qr === 0, 不用做任何事情,我们正好利用qr的lsb生成的mask来得到应该加的exp的值
    exp = exp + (lsb & 16);

    // 接下来再对half过的x再进行二分查询,这一次应该是右移8
    // 这里不需要右移24,因为如果原始值x的上半部分包含1的话,我们的hx已经自动将原始值的上半部分过滤掉了,上半部分已经移动到下半部分的16个bits上
    // 同时,如果原始值x上半部分不包含1,那么我们再对下半部分折半查询,所以,综合上面两种情况,如果被查询的上部分包含1,那么舍掉其下部分,然后将上部分移动至下部分,如果不包含1,那么继续往下部分二分查询
    rx = cx >> 8;
    qr = !!rx; //1 if left 24 contains 1;
    lsb = (qr << 31) >> 31;
    cx = (lsb & rx) | ((~lsb) & cx);
    exp = exp + (lsb & 8);

    //继续同样的思路
    rx = cx >> 4;
    qr = !!rx;
    lsb = (qr << 31) >> 31;
    cx = (lsb & rx) | ((~lsb) & cx);
    exp = exp + (lsb & 4);

    rx = cx >> 2;
    qr = !!rx;
    lsb = (qr << 31) >> 31;
    cx = (lsb & rx) | ((~lsb) & cx);
    exp = exp + (lsb & 2);

    rx = cx >> 1;
    qr = !!rx;
    lsb = (qr << 31) >> 31;
    exp = exp + (lsb & 1);


    return exp;
}

bitcount

实验要求:

/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */

这个实验涉及到的面还是比较广的,涉及到了logicalShift,怎么通过有限的数字构造出想要的二进制样式,以及还涉及到了一点“分治”的思想,用”局部二进制“来存储信息,只能用位运算符,同时使用的integer只能在0x00-0xff之间。

整体思路是,先两两分组,用2位二进制代表2位上出现1的个数,然后再四个一组,用4位二进制代表4位上出现1的个数,然后8位二进制一组,计算出8位上出现1的个数,然后16位一组,用二进制表示16位上出现1的个数,最后32位,得出的二进制结果就是1的个数。

比如我们计算如下二进制的1的个数:

0101 1011 0111 0110 0000 1010 0010 1011

我们两两分组step1:

01 01 10 11 01 11 01 10 00 00 10 10 00 10 10 11

我们的目的是能够构造出一个新的二进制表示,每两位体现了其中1的个数,我们需要把上面的二进制通过一系列操作要做成,错1位相加得step2:

01 01 01 10 01 10 01 01 00 00 01 01 00 01 01 10

上面这个二进制每两位代表了step1中的二进制每两位上1的个数,然后这样之后,我们再四个一组,通过一系列操作做成每4位二进制表示step2中每四位中1的个数,就是step2中,每两位错位相加后的结果如下:

0010 0011 0011 0010 0000 0010 0001 0011

错4位相加,做成8位表示

00000101 00000101 00000010 00000100

接着错8位相加,做成16位表示

0000000000001010 0000000000000110

接着错16位相加,做成32位表示,即为最终结果

00000000000000000000000000010000

变成10进制,上面的结果即为16

完整:

int bitCount(int x) {
  int logicalShiftX;
    int step1_base;
    int sum1;
    int step2_base;
    int sum2;
    int step3_base;
    int sum3;
    int step4_base;
    int sum4;

    int step5_base;
    int sum5;

    int mask = 1 << 31;

    step1_base = 0x55;
    step1_base = step1_base | step1_base << 8;
    step1_base = step1_base | step1_base << 16;

    logicalShiftX = ~mask & (x >> 1);
    sum1 = (x & step1_base) + (logicalShiftX & step1_base);

      step2_base = 0x33;
      step2_base = step2_base | step2_base << 8;
      step2_base = step2_base | step2_base << 16;

      sum2 = (sum1 & step2_base) + ( (sum1 >> 2) & step2_base);



    step3_base = 0x0F;
    step3_base = step3_base | step3_base << 8;
    step3_base = step3_base | step3_base << 16;

    sum3 = (sum2 & step3_base) + ( (sum2 >> 4) & step3_base);

    step4_base = 0xFF;
    step4_base = step4_base | step4_base << 16;

    sum4 = (sum3 & step4_base) + ( (sum3 >> 8) & step4_base);


    step5_base = 0xFF;
    step5_base = step5_base | step5_base << 8;

    sum5 = (sum4 & step5_base) + ( (sum4 >> 16) & step5_base);

    return sum5;
}