找到一个数最右边那个1很容易，就是x & -x，那么最左边那个1呢？

【1】移位，逐个check，复杂度O(n)，n是bit位数。

【2】先把二进制模式翻转，再求最右边那个1，再翻转回去。复杂度O(lg N)。

【3】得到最右边那个1，然后加到原数字上，这样可以消灭最右边的1，依次这么做，可以找到最左边的1，。这个方法比【1】快。

实现了【2】【3】：

#include<stdio.h>
#include<stdlib.h>

// 1.计算最左边的比特.倒置->最右边比特->倒置
int rev(int x)
{
	x = (x & 0xAAAAAAAA)>>1 | (x & 0x55555555)<<1;
	x = (x & 0xCCCCCCCC)>>2 | (x & 0x33333333)<<2;
	x = (x & 0xF0F0F0F0)>>4 | (x & 0x0F0F0F0F)<<4;
	x = (x & 0xFF00FF00)>>8 | (x & 0x00FF00FF)<<8;
	x = (x & 0xFFFF0000)>>16 | (x & 0x0000FFFF)<<16;
}
int rb(int x)
{
	return x & -x;
}

// 2.迭代消灭最右边比特.
int getl(int x)
{
	if(x==0)return 0;
	if ((x&(x-1)) == 0)return x; // 注意优先级
	while((x&(x-1)) != 0)
	{
		x += rb(x);
	}
	return x/2;
}

int main()
{
	int i;
	for (i=0; i<100; i++)
	{
		int t = rand()%2000000;
		printf("%8x - %8x\t", t, rev(t));
		printf("最左边的比特(方法1): %x，  \t最左边的比特(方法2): %x\n", rev(rb(rev(t))) , getl(t) );
	}
	return 0;
}

输出：
46a67 - e6562000 最左边的比特(方法1): 40000，   最左边的比特(方法2): 40000  
e3446 - 622c7000 最左边的比特(方法1): 80000，   最左边的比特(方法2): 80000  
19d469 - 962b9800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000  
   9b7f3 - cfed9000 最左边的比特(方法1): 80000，   最左边的比特(方法2): 80000  
  1aab51 - 8ad55800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000  
   3a2ff - ff45c000 最左边的比特(方法1): 20000，   最左边的比特(方法2): 20000  
  1cc4ca - 53233800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000  
  1adcec - 373b5800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000
   7e229 - 9447e000 最左边的比特(方法1): 40000，   最左边的比特(方法2): 40000
  190bcd - b3d09800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000
  1258ba - 5d1a4800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000
   77a2b - d45ee000 最左边的比特(方法1): 40000，   最左边的比特(方法2): 40000
  14e272 - 4e472800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000
   7ef7b - def7e000 最左边的比特(方法1): 40000，   最左边的比特(方法2): 40000
   db2e3 - c74db000 最左边的比特(方法1): 80000，   最左边的比特(方法2): 80000
  1719c6 - 6398e800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000
  12037c - 3ec04800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000
   5d9c2 - 439ba000 最左边的比特(方法1): 40000，   最左边的比特(方法2): 40000
   15c54 - 2a3a8000 最左边的比特(方法1): 10000，   最左边的比特(方法2): 10000
  163678 - 1e6c6800 最左边的比特(方法1): 100000，   最左边的比特(方法2): 100000
   f569b - d96af000 最左边的比特(方法1): 80000，   最左边的比特(方法2): 80000

。。。 多的就不贴了。

阅读更多

更多精彩内容