一个简单的想法就是每次向右移一位,然后判断是否为0,同时记录移动的次数,这个算法的复杂度与待判断的这个数n有关,是$O(log_2n)$,需要移动的次数越多。不过,可以采用二分查找的思想,比如对一个32位int型变量(正数),可以先右移16位(mid point),判断得到的数是否大于0,然后在缩小的范围里继续查找。代码如下:

int find_bits(int n){//假设n为正数,即二进制表示最高位为0,且至少有一个1
	//返回n的二进制表示的位数,leading zeros are ignored
	//采用二分的移位
	int left = 31, right = 1;//至少移1位,至多31位,左边是高位
	while (left > right) {
		int mid = (left + right) / 2;
		if ((n >> mid) > 0) {
			right = mid + 1;
		} else {
			left = mid;
		}
	}
	return left;
}

其实也可以用一行代码搞定:ceil(log2((double)(i+1))),对i从1到2^31-2都成立

对这个问题,不知道有没有使用常数个位运算的算法,如果你知道,可以告诉我~