求二进制串中最低位1的位置（末尾0的个数）方法很多，但是时间复杂度达到O（1）却很难，可以采用De Bruijn序列的方法。
概念解释：
1. De Bruijn序列：如果一个二进制串的长度为 2^n , 将其看成环形，首尾相连，从每一个字符开始进行n位截断，这样一共会产生 2^n个长度为n的二进制子串，如果这些子串全部互异，即这些二进制子串的值包含了从 0~2^n-1的所有值，那么我们称这样的二进制串为De Bruijn序列。
算法:
对于长度为 2^n 的二进制串，其末尾0的个数范围从 0~2^n-1(如果2^n位全为0则看作有0个0)，刚好可以用n位的二进制全部表示。设 k = 长度为 2^n 的二进制De Bruijn序列串，那么 对于 k<<i(i=0,1,2,3…..2^n)，随着i的不同，k << i的最高n位都不会相同，会得到从0~2^n-1的所有值，取高n位可以表示为 (k<<i)>>(2^n-n) ,设 t=(k<<i)>>(2^n-n) ,如果t=0,则表示有a0个0，如果t=1,则表示有a1个0…..,t的范围从0到 0~2^n-1，由此可以建立一个长度为 2^n 的数组,{a1,a2,…..,a2^n-1}。
eg：当n=5的时候,De Bruijn序列为 0x077CB531U,构建的表为 {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9}。
int DeBruijn(int num){int array[32] ={0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};int res = array[((unsigned int)(num & -num) * 0x077CB531U) >> 27];return res;}
代码解释：
1. 先要把给定数字num中除了最低位1以外的全部数字归0，(num & -num)意思是说：取num的从右边开始的0以及第一个1，比如:num = 101010100010101000000,num & -num = 1000000。(num & -num) * 0x077CB531U) >> 27 就是上面提到的 (k << i) >> (2^n-n).
完整版测试代码:
#include <stdio.h>#include <stdlib.h>int DeBruijn(int num){int array[32] ={0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};int res = array[((unsigned int)(num & -num) * 0x077CB531U) >> 27];return res;}int main(){printf("the res is %d\n",DeBruijn(123456));return 0;}
那么问题来了，De Bruijn序列是怎么构造出来的呢？这个问题可以转化为求一个有向图的欧拉回路问题。下列关于求De Bruijn序列的方法引用自：
如下图，构造一个包含 16 个顶点的图，顶点分别命名为 0000, 0001, 0010, …, 1111 。如果某个点的后 3 位，正好等于另一个点的前 3 位，就画一条从前者出发指向后者的箭头。也就是说，只要两个顶点上的数满足 abcd 和 bcde 的关系（ a 、 b 、 c 、 d 、 e 可能代表相同的数字），就从 abcd 出发，连一条到 bcde 的路，这条路就记作 abcde 。注意，有些点之间是可以相互到达的（比如 1010 和 0101 ），有些点甚至有一条到达自己的路（比如 0000 ）。
构造一个字符串使其包含所有可能的 5 位 01 子串，其实就相当于沿着箭头在上图中游走的过程。不妨假设字符串以 0000 开头。如果下一个数字是 1 ，那么 00001 这个子串就被包含了，同时最新的 4 位数就变成了 0001 ；但若下一个数字还是 0 ，那么 00000 就被包含了进来，最新的 4 个数仍是 0000 。
从图上看，这无非是一个从 0000 点出发走了哪条路的问题：你是选择了沿 00001 这条路走到了 0001 这个点，还是沿着 00000 这条路走回了 0000 这个点。同理，每添加一个数字，就相当于沿着某条路走到了一个新的点，路上所写的 5 位数就是刚被考虑到的 5 位数。我们的目的便是既无重复又无遗漏地遍历所有的路。显然图中的每个顶点入度和出度都是 2 ，因此这个图一定存在 Euler 回路，我们便能轻易构造出一个满足要求的 01 串了。这样的 01 串就叫做 De Bruijn 序列。
这样，就可以在O（1）时间内求出二进制串中最低位1的位置了.
