目录

1、迭代法

2、二分法

3、整形形式输出

---

题目：给定一个整形（unsigned int）数字，输出其二进制数中的bit为1 的最高/低位索引。

示例：对于数据0，返回0；数据1，返回1；数据0x80000000，返回32；

本文以搜索最低位即最右侧的bit1索引为例。

1、迭代法

int search_right_one(unsigned int var) { int index = 0; while(var) { index++; if(var & 0x1) { break; } var >>= 1; } return index; }

2、二分法

先以搜索一个字节（8bit）的最右侧1的索引，利用二分法，先判断低4位是否含有1，Y：则继续判断低2位，低1位等；

如果没有则将高4位的数右移动至低4位上继续判断，同时将索引值index += 4 操作。代码如下：

int search_right_one8(unsigned char var) { int index = 1; if(!var) { return 0; } if(!(var&0x0f)) { var >>= 4; index += 4; } if(!(var&0x03)) { var >>= 2; index += 2; } if(!(var&0x01)) { var >>= 1; index += 1; } return index; }

有了8bit的索引搜索函数。判断16，32、64bit等整形函数就容易多了，继续使用二分法，判断其右侧1在左半区或是右半区。代码如下：

int search_right_one16(unsigned short var) { int index = 0; if(!var) { return 0; } if(!(var&0x00ff)) { var >>= 8; return 8 + search_right_one8((unsigned char)var); }else { return search_right_one8((unsigned char)var); } } int search_right_one32(unsigned int var) { int index = 0; if(!var) { return 0; } if(!(var&0x0000ffff)) { var >>= 16; return 16 + search_right_one16((unsigned short)var); }else { return search_right_one16((unsigned short)var); } }

3、整形形式输出

题目：给定一个整形数字，获取其二进制数中的bit为1 的最低位，并以整形数字形式输出，即除了该位上的1保留其余bit均置位0。

首先看一下，几种常见的位操作运算符： &(按位与）、|(按位或)、^(按位异或)、~(按位取反)、!(取非，即为0输出1，为非0输出0)、<<(左移符)，>>(右移符)

如何快速的定位到最低bit为1了，毫无疑问，对其进行减1操作，那么最低的1此时会被置位0，且其右侧的0被置1。

算法：

对该数 var1 进行减 1 操作，得到数字 var2 ，其高位不变，最右侧索引1被置0，且其右侧的0被置1。将 var2 和 var1 进行 与（&）操作，得到数字 var3，其变化的仅仅是最右侧1被置0，其余位均不变。将 var3 与 var1 进行 异或（^） 操作得到所需整形数字 var4。

代码如下：

int search_right_one_value(unsigned int var) { int tmp = var & (var-1); int ret = tmp ^ var; return ret; }